ICFPC の BALANCE を説明

BLNCE を IRC で簡単に説明しようとしてうまく説明できなかったので、これに一番萌えた以上、ちゃんと説明したい、と思い筆を取りました。ドキュメントの翻訳…でもいいかと思ったんですが、ライセンスわからないし、詳説したいわけでもないし自分ふうに。

プログラムは 1Byte に 1命令入ります。それと、 256Byte のメモリと、ソースレジスタが4つ(以下 S0 S1 S2 S3と記述)、デスティネーションレジスタが2つ(以下 D0 D1)あります。毎クロック、インストラクションポインタ(以下IP)の位置の命令を読んで実行します。ここまでは普通ですが、 IP の移動速度を示すレジスタがあるのが早くも少し不審な感じです。この速度は IS と呼ばれ、初期値は 1 なので、まぁ普通に動きます。

そんな割と普通なマシンをイカれた 4つの命令セットで記述します。命令は最初の 3bit が opcode で、残り 5bit が引数です。最後の PHYSICS が最もイカレてると思います。

あ、以下のような内容は自分で考えて気付いた方が絶対面白いので、あんまりいないでしょうけど、自分で考える気がある人は続きを読まないようにお願いします。つか書いてみるとえらい長文になったのでどうせ誰も読まないよ、と思います。というか文の長さから、私が今回の ICFPC をとても楽しめたことを察して下さい。

MATH (001)

001xyyzz と指定します。 x はデスティネーションレジスタ(2つしか無いので1bitで表現)で、 yy と zz がソースレジスタです。この計算はレジスタ内で行われるわけではなく、レジスタの指し示すメモリの内容を加算します。 add [%eax], [%ebx], [%ecx] みたいな印象でしょうか。ドキュメントによると、以下の加算減算の2命令を同時に実行します。

M[ dR[D]   ] <- M[ sR[S1]   ]  +  M[ sR[S2]   ]
M[ dR[D+1] ] <- M[ sR[S1+1] ]  -  M[ sR[S2+1] ]

これはつまり例えば 00110110 を実行させると(引数は 1 01 10 です)、 D1 で指定されるメモリ位置(以下 M[D1])に M[S1]+M[S2] を代入しつつ、 M[D0]=M[S2]-M[S3] が実行されることになります。 D0 に破壊されてはいけないメモリが入っている場合にこの命令を実行させると、とても悲しいことになります。レジスタに自由な値を入れられるならこんな制約は全然問題無いのですが、後で見るようにレジスタの操作が一番終わっています。

LOGIC (010)

上記とほぼ同じく、 010xyyzz で指定して、 + のかわりに AND を、 - のかわりに XOR を同時実行します。

SCIENCE (000)

000xxxxx と指定します。 xxxxx は -16 から 15 までの整数として扱われます。

まず、 S0 が指し示すメモリ内容、 M[S0] が 0 であるかをチェックします。 0 ならば何もしません。

次に、 IP の移動速度であるところの IS に xxxxx の値を代入します。 IS が 0 になった場合は、つまり動かないということですから、プログラム実行の正常終了を意味します。 0x00 が正常終了命令になるのはなんとなくわかりやすくて良いです。

これを使うと分岐命令を作ることができます。 00000001 (...15バイトの命令...) 00011111 とかすると、ちょうど brainfuck の [] のようなことになります。つまり、最初の 00000001 で IP の速度を 1 にし、 15Byte 実行したあとに、 S0 が指しているメモリが 0 以外であれば速度を -16 にするので、つまり 00000001 のところに戻って速度 1 になります。

PHYSICS (011)

さて、一番イカれたレジスタ操作命令です。 011xxxxx と指定します。 xxxxx は -16 から 15 までの整数です。

まず、普通に xxxxx を S[0] に加算します。

次にレジスタを特定のルールに従って「左回転」させます。回転のルールがなかなか大変で、まず 1xxxxx の 1 になっている bit に着目します。先頭 bit は常に 1 です。これらはちょうど 6bit になっていて、それぞれがレジスタに対応しています。レジスタは S0 S1 S2 S3 D0 D1 と対応していて、 1 の立っている bit を対象に「左回転」を行います。文ではどう考えても説明しにくいため、例を示します。

01100000 の場合、 S0 に 0 を足して、 100000 で bit の立っているレジスタを対象に回転をします。この場合は、 S0 のみが対象ですので、回転は起こりません。結局、これは NOP ですね。レジスタの初期状態を (a b c d e f) とすると、終了状態は (a b c d e f) です。

01100001 の場合、 S0 に 1 を足して、 100001 を考えると、 S0 と D1 を対象にして回転が起きます。つまり、「 S0 に 1 を足して、 S0 と D1 を swap する命令」と考えることができます。終了状態は (f b c d e a+1) となります。

01111111 の場合、 S0 から 1 を引いて、 111111 を対象に回転を起こします。この場合は全レジスタが左回転することになりますから、終了状態は (b c d e f a-1) となります。

私は上の 2 命令はわかりやすく、重宝すると思います。 01100001 を 2回行うことで S0 と D1 を、他に影響を与えることなくインクリメントすることができます(レジスタ位置は2回交換するので元に戻る)。 D1 がどうでもいいレジスタである場合は、実質インクリメントが手に入ることになります。また、 01111111 を 6回行うことによって、全レジスタをデクリメントすることができます(レジスタ6つを6回回転すると元に戻る)。このデクリメントの最中に、デクリメントしたくないレジスタがある場合は、 01100001 を実行してやればうまく値を調整することができます。

同じように、 01100010 を 2回実行すれば S0 と D1 の両方を 2 足すことができますし、 01111110 を 5回実行すれば D1 以外のレジスタを -2 することができます。これも -2 でぐるぐる回しながら大事なものは 2 を足してやれば、狙ったレジスタを -2 したりできるわけです。

最後に制御の難しい例を見てみます。 01101011 の場合、 S0 に 10 を足した後、 101011 のビットパターンに従うので、結果は (c b e d f a+10) となります。ああ無茶苦茶になったな、という感じです。

実際の例として、 SCIENCE 命令は S0 のメモリしかチェックできないのですが、例えば S1 で上記 SCIENCE 命令を実行して、その後に S2 で SCIENCE したい場合を考えてみます。 SCIENCE に反応しなかった場合は、全レジスタの内容は保存したいとします。

まず、 S1 を S0 に入れたいのですが、ここで安易に 01110000 すると、 S0-16 の値が S1 に入ってしまいます。足し算は 15 までしかできませんし、どうせ S2 も次で必要なので、 S2 も巻き込んで回してやります。つまり 01111000 をしてやります。

すると (b c a-8 d e f) という状態になるので、ここで SCIENCE を実行してやれば S1 での SCIENCE はできます。次は S2 が欲しいのですが、次にもう一度 01111000 を実行してやると、 (c a-8 b-8 d e f) となるため、ここで SCIENCE でミッションコンプリートです。しかしこれ、レジスタを破壊してしまっています。ダメじゃん、というわけで…

ああめんどくなってきた、色々方法は考えられますが、 4 つずつ回して、順次戻すのが簡単な気がします。 01111100 SCIENCE 01111100 SCIENCE 01100100 01100100 01111100 01111100 01100100 01100100 、です。わけわかりませんが、以下のように変化していきます。 01100100 を 2回実行すると S0 と S3 を 4足すことができるわけで、 -4 してしまった値を元に戻すわけです。

(a b c d e f) => (b c d a-4 e f) => (c d a-4 b-4 e f) => (b d a-4 c+4 e f) => (c+4 b d a-4 b e f) => (d a-4 b c e f) => (a-4 b c d-4 e f) => (d-4 b c a e f) => (a b c d e f)

えーと、ここまででたぶん想像していただけると思うんですが、「 S1 と S2 を順番に SCIENCE したい」なんて状況は比較的簡単な状況です。これが S2 の次に S1 、だと上記を 2度回すのはダサいですし、2つの制約からイヤなのです。1つ目の制約は、短いコードの方が高得点であること。2つ目の制約は、この処理をループ内でやってる場合、 SCIENCE で変更できる IS は -16 から 15 までなので、16命令に収まりにくくなってくるから、です。実際上記を2回回すと、2つSCIENCE入れて18命令になって、厳しいことになります。まぁ SCIENCE -9 とかして戻る最中に都合の悪くない命令が入るように、典型的には NOP を入れてやればなんとかなるでしょうが…とにかく2周回すとか、ダサいのがダメなんです。 "a professional programmer knows that shorter code is better code!"

結局、それまでのレジスタの扱いで、うまく「 S1 と S2 を順番に SCIENCE したい」という状況になるよう、調整することになる感じで、まぁ割と大変で、どう考えてもパズルとなるわけでした。