Malbolge で AtCoder 精選過去問10問の2問目を解く、そしてその先の世界を見る

この記事は 株式会社ゆめみ Advent Calendar 2023 23日目の記事です。
なお、業務に関わる話は一切出てきません。（は？）

前置き

難解言語 Malbolge

みなさんは 難解言語 Malbolge をご存知でしょうか？
Malbolge は 難解プログラミング言語 (esolang) の1つであり、esolang の中でも 最も扱いにくくなるように設計された 言語になります。

今年は reika727 氏の [1] 難解言語 Malbolge は HelloWorld に「2 年」かかった や、angel_p_57 氏の [2] 難解言語 Malbolge でラクして FizzBuzz などの記事が上がり、Malbolge が少し世に知られた年なのかな、と思います。

Malbolge の詳しい説明はこれらの記事を参照していただければと思います（というか説明するのが面倒）。

存在する仕様のどれもが 面倒になるように設計されている ので、触っていくと、まー嫌いになっていきます。この記事を書くにあたって触れましたが、ぼくは嫌いになりましたこの言語。

この記事でやること

AtCoder の A問題 の1つである Placing Marbles を Malbolge で解きます。

この問題は、[3] AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ の2問目にあたります。

なぜこの問題かというと、[3] 中の問題を esolang で解くにあたり一番簡単だからです。1問目は数値入力のできない言語には難しい。

問題設定

Placing Marbles

問題（要約）

$s_i$ は $0$ か $1$ である。
$s_1s_2s_3$ の文字列に $1$ がいくつあるか求めよ。

AtCoder で Malbolge を提出するには

さて、この問題を Malbolge で解いていく上で、AtCoder 上で提出しなくてはなりません。
しかしながら、というか当然、AtCoder のサポート言語に Malbolge は存在しません。
よって、C++ で実装されたインタプリタに Malbolge にコードを載せる ことで提出したことにします。

具体的に Hello, world! の例で説明すると、以下のような提出をすればOKとします。

こちらの提出では、Malbolge のインタプリタとともに、 std::string code = ... とある行に Malbolge のコードを埋め込んでいます。 この行のコードを Malbolge として実行すれば Hello, world! が実現できますし、実際これでACしています。

なお、このコードのインタプリタは [1] から借りており、Hello, world! の探索コードも [1] のコードを利用しています。

また細かいレギュレーションで言えば、 < は出力、 / は入力 とします。
オリジナル実装だと逆、という話がありますが、ややこしいので利用したインタプリタの定義に合わせておきます。

Malbolge における Placing Marbles の実装

おことわり

飯澤らによる論文 [4] 難読プログラミング言語 Malbolge におけるプログラム構成手法 をもとに、各命令を以下のように呼ぶことがあります。

• BRANCH: (XLAT1 変換後の i) 分岐命令。 C = [D]
• LOAD_D: (XLAT1 変換後の j) データレジスタ変更命令。 D = [D]
• ROTATE: (XLAT1 変換後の *) 右ローテート命令。 A, D = rot([D])
• OPR: (XLAT1 変換後の p) 演算命令。 A, D = crazy(A, [D])
• NOOP: (XLAT1 変換後の o) 無操作命令。
• HALT: (XLAT1 変換後の v) 停止命令。
• INPUT: (XLAT1 変換後の /) 入力命令。標準入力から ASCII コードを受け取り、 A に代入。 EOF なら 2222222222t を代入
• OUTPUT: (XLAT1 変換後の <) 出力命令。A % 256 を ASCII コードに変換して標準出力に出力

また、この記事中には以下のような表現が登場します。

• 0000000000t ~ 2222222222t: 3進数表現。 Malbolge ではトリットという3進数の10桁を1ワードとして扱います
• A C D: Aレジスタ、Cレジスタ、 Dレジスタの値を指します。 特に C D に関しては位置を指します
• [C] [D]: Cレジスタ、 Dレジスタの指す値を指します

方針

さて、ここからは実際に Placing Marbles を Malbolge で解く上での手法や考え方について述べていきます。ここからは Malbolge の仕様については（解説するものの）知っているものとして扱うのでご注意ください。

C と D を分ける

Malbolge において、初手で Cレジスタ と Dレジスタ は指す場所を変えるようにしましょう。
Malbolge は OPR や ROTATE によって演算を行いますが、C と D の指す位置が同じであると、これらの演算結果を C の位置によって暗号化しようとし、失敗して落ちます。

そのため初手で Cレジスタ と Dレジスタ の位置を分けざるを得ません。

メモリの 33 ~ 126 番地を大切に扱う

Malbolge において若い番地は大切に扱うべきで、特に 33 ~ 126 番地は大切に扱うべきです。宝 です。
この 33 ~ 126 は D に扱わせるべき番地 となります。 Malbolge において、 33 ~ 126 という値はあらゆる番地のメモリに設置 できるため、LOAD_D 命令をすれば 33 ~ 126 番地に D を持ってこれるためです。

具体的に何が嬉しいかというと、D がループし、同じ値に複数回アクセスする ことができるようになります。
今回でいえば、65 ~ 69 番地に重要なデータを入れ、70 番地 は 64 を入れました。 D が 70番地を指しているときに LOAD_D をすることで、 D は再び 65 ~ 70 番地 を指すことができるようになります。これによって 65 ~ 70 番地 には何回もアクセスできるようになりました。

このアイデアは、飯澤らによる論文 [4] の データモジュール の考えから得ています。

入力が8通りしかないので、8通りの分岐をする

前述のアイデアにより、D は扱いやすくなりました。
しかしながら、C は扱いやすくなりません。（ちなみに、理論が進んでもずっと扱いやすくなることはありません）
なぜなら、C は命令を実行するたびに該当の番地を暗号化し、別の文字へ変換してしまうからです。
基本的に C で扱った番地は使い捨てとなる と考えるとよいでしょう。

ところで、今回の問題は 入力が8通りしかありません。
であれば、8通りの分岐を書くまでです。

D が扱いやすくなったことにより、各入力によって C をどこへ分岐させるか？ を表現しやすくなります。
そこで、 「1文字目が0 なら xxx 番地、1 なら yyy 番地 に C を移動する」 「1文字目が 0 である場合に限り、2文字目が0 なら vvv 番地、1 なら www 番地に C を移動する」 といった表現をすることを考えます。
これを、各番地が被らないように（近いとNG、例えば xxx番地から数十番地は C 用に命令を置くため）配置すればよくなります。これは、D が扱いやすくなり、入力した値に何度もアクセスできるようになり、うまく番地をバラけさせやすくなったため可能です。

具体的な構成

さて、ここからは実際のコードの構成に移ります。

実際に構成したもの

提出したコードがこちらになります。

Malbolge のコードは170行目にあたり、実際にACしていることが確認できると思います。

まずは変換機を作る

こんな言語直で書いてられないので、まずは変換機を書きましょう。

こちらが使用した変換機になります。
https://gist.github.com/ten986/1b2cfb72c3776ac52ddd8b0f9324ff36

変換機に入れる前のコードがこちらです。
https://gist.github.com/ten986/fd6b459f08f322291eaf66fdfa437593

変換機の機能としては、[2] から取り入れたものが多いです。
Malbolge の制約として、最初のコード上の文字は、XLAT1変換後に命令として解釈できなければならない というものがあります。なので、変換前のコードとして用意すべきは Malbolge の命令として解釈できる文字のみ と言えます。
また、「特定の文字が連続して出現する」「ある番地まで特定の文字で埋める」機能もあると便利です。今回の変換機はこれらを導入しています。
さらに、コメントを挿入できるとコーディング中に便利なので、その機能も入れてあります。

以下、これらの数字を見たら、それぞれ以下のもののXLAT1変換後の文字を記述しているのだな、と思ってください。（変換機の機能そのままです）

• 11: 文字列をそのまま
• 12: その文字を N 個
• 13: その文字を、番地が N になるまで

ついでに、インタプリタにもデバッグ出力を仕込んでおきます。

C と D をいい感じの初期値に配置する

前述の通り、初手でやるべきことです。
コード上で言うと、このあたりです。

11
ip

...

11
joo

このあたりの記述で、よくわかりませんが C=100, D=62 の状況が作れます。

入力を受け取る

C は、以下の命令をたどります。

11
/p/p/pj

また、対応する D (65番地 ~ 70番地)は以下のものになります。

11
oo<opj

組み合わせると、入力を受け取り、crazy(入力1文字目, [65]) を 65番地に代入する形になります。 crazy(入力2文字目, [67]) と crazy(入力3文字目, [69]) も同様です。
65番地、67番地、69番地の初期値が違うのは、crazy による情報落ちを防ぐためです。 入力は '0' = 0000001210t か '1' = 0000001211t ですが、この下一桁が crazy 演算により一致してしまう場合があります。 それを避けられるような値にしています。
また、crazy 演算後の値を ROTATE や OPR によりいじった値を C の飛び先として使うので、微妙にずらしているという側面もあります。

70番地にはちょうど 64 を示す値を入れています。 これは D がちょうど 70番地を指している際に LOAD_D をすることで、D=64 となり、 65 ~ 70 番地にアクセスし続けられるようにするためです。

それぞれ分岐していく

ここで、1文字目による分岐をします。
コード的には、以下のあたりの説明です。

11
*ooooj
11
i

0
ここまでで、入力受取と1個目の分岐
-> 29519, 9836
#

65番地に対して ROTATE をすると、入力1文字目が 0 の場合は 29519、 1 の場合は 9836 になるようです。
入力を受け取る際に、0 と 1 とで下1桁が変わるような工夫をしました。そのため、右ローテートにより異なるトリットを上位の桁に移してやることで、大きく異なる値の生成ができます。（どうしてこの値になるのかは知りません）

この生成した値に対して BRANCH をしてやれば、晴れて分岐が実現できます。分岐先でそれぞれ 0 と 1 により分岐をさせていくと、入力8パターンを処理できます。

今回の方針では、入力がそれぞれ ??? 0?? 1?? 00? 01? 10? 11? 000 001 010 011 100 101 110 111 の場合（? は処理前）の15箇所でそれぞれ処理を挟んでやる必要が出てきます。
分岐させる番地はそれぞれ異なる必要があります（差が20未満くらいだと、命令列が重なる可能性が出る）。 この番地の生成は、BRANCH と OPR をうまいことしながら、デバッグ出力を見て「この値なら今までの処理には出ていないな・・・」と思ったらその値にする、といった方法で決めていきます。 気合いです。

出力する

さて、8パターンの分岐ができたので、それぞれ出力をします。

出力用に、 D のために用意しているメモリは以下のようになっています。

0
↓出力用
#
11
o
13
o 83
11
jjjjo

この jjjjo の部分が重要で、 この位置での jjjj のXLAT1変換前は 3210 であるため、対応する数値をそのまま Aレジスタ にロードし OUTPUT をすれば、計算が完了します。
o は LOAD_D によってループするための値です。

具体的な出力を見るために、入力が 110 である場合の処理を見ましょう。

0
3279: 1個目が1、2個目が1、3個目が0
#
13
o 3279
12
o 7
11
//oooooopooj
11
//oooooopoo<v

ここで、論文 [5] Malbolge の高級アセンブリ言語への加算命令の追加 を参照すれば、2222222222t を用意し、 crazy(2222222222t, 対象のメモリ) により対象のメモリを変換後、 crazy(2222222222t, 対象のメモリ) をすれば、対象のメモリを Aレジスタにロードすることができます！

2222222222t はどこから用意するのでしょうか？ 入力はすでにEOFを迎えているため、INPUT 命令にをすれば Aレジスタには 2222222222t が代入されます。

入力が 110 の場合は 2 を出力したいので、ちょうど D が 2 を指しているときに OPR をするとよくなります。
これにより、望んだ値を Aレジスタ にロードし、OUTPUT をすることで、無事問題を解くことができました。

おまけ

おまけ、というかこの記事で本当に語りたかった部分です。

この記事を書くに至った経緯

この記事を書くきっかけですが、1ヶ月ほど前に Malbolge で Quine をやったら面白いのでは？ と思いつきましたが、なんと前例がありました（[6] Malbolge Quine）！
今思えば Quine を実装するのは大変だったと思うので、あってよかったと思いますが・・・。

ですが、Malbolge でネタにしてみたいので、むしろ実用的なコードを書けばいいのでは？ となり、AtCoder過去問精選10問を解けばいいのでは？ と思いつきました。
この過去問精選10問で解きやすい問題といえば、2問目の Placing Marbles になります。

1問目の Product は高級言語であれば解きやすいのですが、esolang あるあるの 「任意桁数の数値入力がしづらい」 ことが1つのネックになります。esolang の入力として数値をサポートせず、文字列をASCIIコードで受け付ける形式はよくあり、Malbolgeもその1つです。 さらに、Malbolgeは命令列のループが 非常に 難しく、この問題の解きづらさが出てきます。

さて、Malbolge について調べみると、[4] にたどり着きます。 この論文では、Malbolge によるプログラムの構成手法が示されています。 であれば、Placing Marbles をこの手法で解けば面白いのでは？ となりました。
実際に構成してみると、論文に示されていない部分で苦しむ部分が出てきました。これは後述します。

ここに至ったときにはすでに 12/24 です。ちなみにこれは 23日目の記事です。 Placing Marbles については記事や論文を読んだ今までの知見を合わせればすんなり構成できるやろ！ と思い至ったため、論文の構成手法は考えずに普通に構成することにしました。ここで今に至ります。実際コードの構成は3時間ほどで終えています。

その先の世界を見る

さて、AtCoder 精選過去問10問の他を見ていきましょう。
2問目以外の問題は、命令列のループ がどうしても必要になります。
こうなると、[4]中の構成手法を利用するほかなくなっていきます。

実際、2問目を解くのに[4]中の構成手法を利用しようとしたのですが、いくつかの点で心が折れてしまいました。実際に挙げていきます。

限定的ループ耐性を持たせた命令列と、データモジュールの扱いが非常に困難

命令列には 限定的ループ耐性を持たせる 必要があります。 C による XLAT2変換後 の文字を見てみると 周期 があり、周期2 で元の文字に戻る (命令, 番地) の組が 番地の $mod 94$ ごとに存在します。
これらを BRANCH で繋ぎ合わせるというのが論文の主張ですが、飛び先のアドレスはデータモジュールにうまく格納する 必要があります。

うまいこと D が C の飛び先のアドレスに移ったタイミングで BRANCH をする必要があるため、実は命令の前は NOOP で埋める必要があります。 しかも、変換後も NOOP であり続ける必要があり、そのような文字は存在しますが、コード上で表現するのではなく定数を生成して埋めていく必要があります。
命令のあといつ BRANCH するかも場合によっては変わります。 これもいくつかパターンを用意しなくてはなりません。

また、命令には LOAD_D を含みます。 データモジュールの先頭へ戻るには LOAD_D の命令を増やす必要が出るため、なるべく データモジュールの先頭へ戻らないように データジュール内のメモリや定数を配置する必要があります。

定数の生成、コピーについて

先ほど「コード上で表現するのではなく定数を生成して埋めていく」と述べたのと、メインルーチンの引数生成には、定数を実行時に生成し、指定のアドレスにコピーする必要があります。 これがまた面倒になります。

まずは定数生成用のモジュールを作ります。 これは 33~126 番地にあるとアクセスしやすそうです。 他のモジュールは命令列ありきですが、定数生成用のモジュールはあくまで D を飼い慣らすための場所であり、C は使い捨てていく前提で設計します。
このモジュール内には、0000000000t 1111111111t 2222222222t 2222222221t の定数を用意しておくと、おそらくは定数が生成しやすくなると思います。 構成できてないので分かりませんが。

生成した値は各アドレスにコピーしたいです。 定数生成用のモジュールの近くに PC (= Program Counter) を用意しておくとよいでしょう。 定数を生成 -> PC の示す番地に D を移動 -> 該当の番地に定数を配置 という操作が考えられます。
次のアドレスに埋めたい定数を・・・と考えると、PC をインクリメントしたくなります。 インクリメントについては [4] 中で示されていますが、桁上げが考慮された命令列ではありません。 しかも、これは限定的ループ耐性を持たせた命令列を用意する必要があります。

気合いで用意する定数が多すぎない? 大丈夫かこれ? となります。

足し算が困難

[5] 中に示されています。すごいなー。

ちなみに

[7] Malbolge, Malbolge20 において、Malbolge20 が提案されています。 たしか、Malbolgeが10桁だったものを20桁に拡張したものだったと思います。
おまけ内でここまで書いた通り、定数生成や命令列の配置は非常に苦労し、相当な命令数を要すると思われるため、番地が20桁になる必要性は過去問精選10問を解くにしても必要そうです。

また、[7] 中には C言語のサブセット（？） から Malbolge20 に変換するソース もあるそうです。 これがあるならこれ以上頑張らなくてもよいのでは・・・？ 実際に使用した記事として [8] 難解言語Malbolgeで湯婆婆を実装してみた もあります。

あとがき

というわけで、この記事では Malbolge により Placing Marbles を解く方法を示しました。
[4] 中の手法により Placing Marbles を解く方法や他の問題を解く方法については、途中までは理論を立てたということで、いずれ他の記事として出すかもしれません。気が向いたらということで。

参考文献

• [1] 難解言語 Malbolge は HelloWorld に「2 年」かかった
• [2] 難解言語 Malbolge でラクして FizzBuzz
• [3] AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
• [4] 難読プログラミング言語 Malbolge におけるプログラム構成手法
• [5] Malbolge の高級アセンブリ言語への加算命令の追加
• [6] Malbolge Quine
• [7] Malbolge, Malbolge20
• [8] 難解言語Malbolgeで湯婆婆を実装してみた