ICFPC 2020 galaxy.txt を読む (その 2)

その 1 ではざっと decompile して、基本的な算術関数を読み解きました。
その 2 では、まだ小さめの関数群が残っているので、これを読み解いてみます。

:1124 = ap ap s ap ap b b ap ap c isnil ap s t ap ap c b ap ap s ap ap b c ap ap b ap b b ap ap b ap b ap ap s i i ap c eq ap c :1124
 {\x2.{\x8.(((isnil x2) f) (x2 {\x29.{\x38.(({\x47.(x47 x47)} ((== x29) x8)) ((:1124 x38) x8))}}))}}

ここで isnil が登場するので、これに着目してみます。(isnil x2) とあるので、x2 は List であることがわかります。一方で後半に着目すると、適宜改行いれて多少見やすくすると

(x2 {\x29.{\x38.
    (({\x47.(x47 x47)}
      ((== x29) x8))
      ((:1124 x38) x8))}})

となっています。その 1 あったとおり ((== x29) x8) は boolean なので、 {\x47.(x47 x47)} は logical or と解釈できます。実際、この後ろの ((:1124 x38) x8) は isnil の分岐で false を返していることからも :1124 自体は 2 引数かつ bool を返す関数とすると全体で辻褄があうので、これを採用することにします。
更に、最初の (x2 {\x29.{\x38. ... }}) に注目すると、List が cons cell でできていたこと、及び cons cell の定義から、これは x29 に car(x2), x38 に cdr(x2) を束縛する decompose と読むことができます。ここも見た目を良くするために let hd::tl = e1 in e2 の形の式を持ち込むことにします。すると

fun(x2, x8) -> if isnil(x2) { false } else { let x29::x38 = x2 in x29 == x8 || :1124(x38, x8) }

と、かけることがわかります。特に isnil + let decompose は頻出するので、関数型言語っぽく match も導入してしまうことにします。

fun(x2, x8) -> match x2 { [] => false, x29::x38 => x29 == x8 || :1124(x38, x8) }

さて、中をもう少し追いかけてみます。空 List が与えられると false. そうでなければ car(x2) が x8 と一致すると true, しなければ、cdr(x2) を第一引数に持ってきて再帰、となっていて、これは List に (正確には == で比較しているところから int の List に限られます) 整数 x8 が含まれるかどうか、という関数です。IntList.mem 的に名前をつけておきましょう。

次は 1126 と 1127 です。

:1126 = ap ap s ap ap b b ap ap c isnil nil ap ap c b ap ap s ap ap b c ap ap b ap b b ap b :1115 ap c :1126
fun(x2, x8) -> match x2 { [] => [], x26::x35 => :1115(x8(x26), :1126(x35, x8)) }
:1127 = ap ap s ap ap b b ap ap b b ap ap c isnil nil ap ap c ap ap b b b ap ap s ap ap b s ap ap b ap b c ap ap b ap b ap b b ap ap b ap b ap b :1115 c ap ap c ap ap b b ap ap b c ap c :1127 ap ap c add 1
fun(x2, x8, x14) -> match x2 { [] => [], x47::x59 => :1115(x8(x47, x14), :1127(x59, x8, x14 + 1))

:1115 を見てみると

:1115 = cons

となっているので、これをそのまま代入します。

fun(x2, x8) -> match x2 { [] => [], x26::x35 => cons(x8(x26), :1126(x35, x8)) }
fun(x2, x8, x14) -> match x2 { [] => [], x47::x59 => cons(x8(x47, x14), :1127(x59, x8, x14 + 1))

２つを比べると、非常に似た形であることがわかります。 1126 は List x2 の全要素に x8 を適用する関数です。 List.map と名前をつけておきましょう。
1127 は 1126 に加えて、もうひとつ引数 x14 をとり、これが x8 にも渡されています。再帰で呼ぶときに x14 + 1 となっていることから、これが List の index であることが予想されます。実際 :1127 を呼んでいる他の関数をみると、0 を第3引数に渡しています。こちらは List.mapi と名前をつけておきましょう。

ここから先は少々 List に関する操作が並びます。素直な定義が並ぶので、ここでは単に列挙することにします。

:1128 = ap ap s ap ap c isnil 0 ap ap b ap add 1 ap ap b :1128 cdr
fun(x2) -> if isnil(x2) { 0 } else { 1 + :1128(cdr(x2)) }
:1128 = List.len

:1131 = ap ap s ap ap b s isnil ap ap c b ap ap b ap c ap ap b b :1115 ap c :1131
fun(x2, x8) -> match x2 { [] => x8, x20::x26 => :1115(x20, :1131(x26, x8)) }
:1131 = List.concat

:1132 = ap ap s ap ap b s ap ap b ap b b isnil ap ap c ap ap b b b ap ap c ap ap b s ap ap b ap b c ap ap b ap b ap b c ap ap b ap b ap b ap c :1132 ap ap c ap ap b c ap ap b ap b b ap c i i i
fun(x2, x8, x17) -> match x2 { [] => x8, x47::x59 => :1132(x59, x17(x8, x47), x17) }
:1132 = LIst.foldl

:1133 = ap ap s ap ap b s ap ap b ap b b isnil ap ap c ap ap b b b ap ap c ap ap b c ap ap b ap b b ap ap b ap b c ap ap b ap s b ap ap b c ap c :1133 i
fun(x2, x8, x17) -> match x2 { [] => x8, x47::x56 => x17(:1133(x56, x8, x17), x47) }
:1133 = List.foldr

:1134 = ap ap c ap ap c :1133 nil ap c :1131
fun(x2) -> :1133(x2, [], fun(x7, x8) -> :1131(x8, x7))
fun(x2) -> List.foldr(x2, [], fun(x7, x8) -> List.concat(x8, x7))
:1134 = List.flatten

:1135 = ap ap c ap ap b b ap ap c :1133 nil ap ap c ap ap b s ap ap b ap b c ap ap c ap ap b b s ap c :1115 i
fun(x2, x8) -> :1133(x2, [], fun(x20, x29) -> x8(x29, :1115(x29, x20), x20))
fun(x2, x8) -> List.foldr(x2, [], fun(x20, x29) -> x8(x29, cons(x29, x20), x20))

ここはちょっと心の目が必要で、x8 が 3 引数関数であるかのように書かれていますが、天下りですがこれは実は bool を返す 1 引数関数と思い直すことにします(実際は次の 1136 での 1135 の使われ方をみると第2引数が1引数関数であることがわかります)。すると

fun(x2, x8) -> List.foldr(x2, [], fun(x20, x29) -> if x8(x29) { cons(x29, x20) } else { x20 })
:1135 = List.filter

ということがわかります。

:1136 = ap ap c ap ap b c ap ap b ap b :1126 ap ap c ap ap b b ap ap b :1135 ap ap c ap ap c :1127 cons 0 ap ap c ap ap b s ap ap c b car cdr car
fun(x2, x8) -> :1126(:1135(:1127(x2, cons, 0), fun(x41) -> x8(car(x41), cdr(x41))), car)
fun(x2, x8) -> List.map(List.filter(List.mapi(x2, cons, 0), fun(x41) -> x8(car(x41), cdr(x41))), car)

ちょっと複雑になってきました。まず List.mapi(x2, cons, 0) は、x2 = [e1, e2, e3, ...] という List を [(e1, 0), (e2, 1), (e3, 2), ...] と index との pair の List にします。
これに filter 関数をかけますが、x41 は今作った index との pair の List の各要素で、この car と cdr を x8 の第1,2引数として渡します。結果 x8 には x2 の各要素とその index が渡され、bool を返すことを期待します。最後に filter された List に対して List.map(..., car) として、index を外します。結局 filter 関数 x8 に追加で index を渡す関数ということになります。 List.filteri と名前をつけておきましょう。

:1137 = ap ap b ap b c ap ap b ap b isnil :1135
{\x2.{\x5.{\x7.{\x8.(((isnil ((:1135 x2) x5)) x8) x7)}}}}

内側の構造に着目すると {\x7.{\x8.(((...) x8) x7)}} となっていて、かつここで (...) = (isnil *1 と bool を返す式になっています。このパターンは logical not で、その 1 同様 true = \x.\y.x, false = \x.\y.y を思い出すと

{\x7.{\x8.((true x8) x7)}} => {\x7.{\x8.x8}} = false
{\x7.{\x8.((false x8) x7)}} => {\x7.{\x8.x7}} = true

となっています(Note: 本来関数の内部は引数が与えられるまで計算しませんが、今回は同値のものが得られます)。! 単項演算子を導入して、簡潔にかけるようにします。

fun(x2, x5) -> !isnil(:1135(x2, x5))

この logical not の置き換えは多少注意が必要で、特に中の bool 式が x7, x8 を含んでいないことを確認する必要があります(仮に含んでいると、書き換え後にその変数が浮いてしまうため)。
:1135 は List.filter であったので、

fun(x2, x5) -> !isnil(List.filter(x2, x5))

filter した結果が nil にならないためには、x5 が true を返すような要素が List x2 に含まれている必要があります。 List.exist と名前をつけておきます。

まとめ

List の操作に関する関数を読み解きました。
次回予告: まだ続く utility 関数を見てみます。

*1::1135 x2) x5

ICFPC 2020 galaxy.txt を読む (その 1: decompile)

その 0 で ICFPC 2020 をざっと復習しました。では実際に galaxy.txt を見てみます。

galaxy.txt

開いてみると、以下のようになっています

:1029 = ap ap cons 7 ap ap cons 123229502148636 nil
:1030 = ap ap cons 2 ap ap cons 7 nil
...
:1107 = ap ap c ap c ap ap b :1183 ap ap c ap ap c :1221 0 ap ap cons 2 ap ap cons 2 ap ap cons 0 ap ap cons 0 ap ap cons 0 nil ap ap cons ap :1225 :1040 ap ap cons ap ap cons ap ap cons 0 0 ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 2 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 0 2 ap ap cons ap ap cons 1 2 ap ap cons ap ap cons 2 2 nil ap ap cons ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 1 1 nil ap ap cons ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 2 1 ap ap cons ap ap cons 4 1 ap ap cons ap ap cons 6 1 nil ap ap cons ap :1214 2 nil
:1108 = ap ap c ap c ap ap b :1183 ap ap c ap ap c :1221 0 ap ap cons 2 ap ap cons 2 ap ap cons 0 ap ap cons 0 ap ap cons 0 nil ap ap cons ap :1225 :1101 ap ap cons ap ap cons ap ap cons 0 0 ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 2 0 ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 0 2 ap ap cons ap ap cons 1 2 ap ap cons ap ap cons 2 2 nil ap ap cons ap ap cons ap ap cons 1 0 ap ap cons ap ap cons 0 1 nil ap ap cons ap ap cons ap ap cons 0 1 ap ap cons ap ap cons 2 1 ap ap cons ap ap cons 4 1 ap ap cons ap ap cons 6 1 nil ap ap cons ap :1214 64 nil
...
:1494 = ap ap c ap ap b c ap ap b ap b c ap ap b ap b ap b s ap ap b ap b ap b ap b c ap ap c ap ap b b ap ap b c ap ap b ap b c ap ap b ap b ap b c ap ap b ap b ap b ap b b ap ap b ap b ap b ap b ap s i ap ap s ap ap b c ap ap b ap b s ap ap b ap b ap b s ap ap b ap b ap b ap b s ap ap b ap b ap b ap b ap b b ap ap b ap b ap b ap b ap b b ap ap b ap c ap ap b b ap ap b b ap ap b b ap eq 1 ap ap b ap b ap c ap ap b c ap c ap ap c :1490 ap :1199 1 ap c ap ap b add ap ap b neg :1117 ap ap b ap b ap c ap ap b c ap ap b ap b c ap ap b ap b ap b c ap ap b ap c ap ap b b ap ap b b ap ap b b ap ap b ap c ap ap b cons ap ap c cons nil ap ap c ap ap b cons ap ap c ap ap b cons ap ap c cons nil nil nil ap ap b ap c ap ap b c ap ap b ap b b ap ap b ap b cons ap ap c ap ap b c ap ap c ap ap b c ap ap c ap ap b b ap ap b :1166 ap add -1 ap add -1 3 3 ap ap c ap ap b b cons ap ap c cons nil ap ap c ap ap b b add :1117 :1172 ap ap s ap ap b :1162 ap ap b ap mul 3 ap ap c ap ap s ap ap b b ap ap c ap ap b b add neg ap ap b ap s mul div 8 ap ap b ap mul 3 ap ap c div 8
galaxy = :1338

さて、このままでは私にはさすがにちょっと厳しいので、もう少し読みやすくするところから始めます。

Decompile

簡単な decompile をします。が、以下の理由で完璧にやるのは結構大変です。

  • true と K コンビネータが同じものを使っている
  • cons cell 等が関数で定義されているので、全部展開すると再構築するのは大変

なので、多少条件を緩くして、現実的にプログラムが読めればよい、というところを目標にします。

まずは最初の :1029 を見ましょう

:1029 = ap ap cons 7 ap ap cons 123229502148636 nil

まずは処理しやすいように AST を組み上げます。galaxy.txt は 1 行 1 定義なので、行ごとに処理します。今回与えられるプログラムは、単に whitespace で切り分けることで tokenize できます。構文解析は単純な LL(1) parse です。 AST は、

enum Value {
  Apply(Box<Value>, Box<Value>),

  Int(isize),
  Symbol(String),
  ... // 以下 builtin の関数が並ぶ
}

として、ap が出てきたら２つ分後続を読んで、Applyを作る。それ以外は単純な mapping をとります。

Definition { name: ":1029", value: Apply(Apply(CONS, INT(7)), Apply(Apply(CONS, INT(123229502148636)), NIL)) }

このままだとまだちょっと読みづらいので、List を導入します。変換は Value を traverse し、

  • NIL => 空 List
  • Apply(Apply(Cons, x), y) => x, y に変換を適用。加えて y の変換結果が List であれば、x の変換結果を prepend する
  • 上記以外の Apply(x, y) => x, y に変換を適用して Apply(x', y') をつくる
  • それ以外 => そのまま

とすれば List を構築できます。結果

[7, 123229502148636]

と List に変換できました。何かのデータのようですが、とりあえず保留します。

さて、この変換を適用した上でざっと galaxy.txt を眺めると、最初に何かのデータが埋め込んであるようです。中身はまだわからないので、一旦保留して次を見ましょう。

次は :1122 を追いかけてみます。

:1122 = ap ap c ap ap b s ap ap s ap ap b c lt i i
Definition { name: ":1122", value: Apply(Apply(C, Apply(Apply(B, S), Apply(Apply(S, Apply(Apply(B, C), LT)), I))), I) }

コンビネーター を lambda 式で書き換えます。コンビネータは以下のとおりでした。

S = \x \y \z . (x z) (y z)
C = \x \y \z . (x z) y
B = \x \y \z . x (y z)
I = \x . x

単純にこれらで置き換えるだけですが、後の処理を単純にするため、展開するごとに変数名がかぶらないようにしておきます。

(({\x0.{\x1.{\x2.((x0 x2) x1)}}} (({\x3.{\x4.{\x5.(x3 (x4 x5))}}} {\x6.{\x7.{\x8.((x6 x8) (x7 x8))}}}) (({\x9.{\x10.{\x11.((x9 x11) (x10 x11))}}} (({\x12.{\x13.{\x14.(x12 (x13 x14))}}} {\x15.{\x16.{\x17.((x15 x17) x16)}}}) <)) {\x18.x18}))) {\x19.x19})

流石にまだちょっと読むには辛いので、これを強引に簡約(もどき)、つまり仮引数の変数を実引数で置き換えます。この式の評価では外部とやりとりすることはなく、また全て遅延評価であることを考慮し、最終的な計算順序は人間の心の目に委ねることにして可能な場所はすべて計算してしまいます。ただし、無限に式が膨れ上がるのはまずいので、「変数が式中で1度しか使われないもの、もしくは引数で与えられるものが単一の変数であるもの」に限って展開することにします。

{\x2.{\x8.((((< x2) x8) x2) x8)}}

この式はこのくらいまで来るとなんとか理解できるようになります。まず最初の ((< x2) x8) は、x2 と x8 の比較結果を bool で返します。ここを cond と置くことにすると、残りは ((cond x2) x8) なので、真の場合 (i.e. x2 < x8 の場合) x2 を、偽の場合 (i.e. x2 >= x8 の場合) x8 を返します。つまりこれは、引数を２つとって、その小さい方を返す、という関数になっています。適当に Int.min(x, y) 的に名前をつけておきましょう。

一歩戻って、この条件分岐は galaxy.txt 全般にわたって頻出するのですが、この形だと分岐なのか関数適用なのかをひと目で分別するのは難しいため、ヒューリスティックを用いて if 文のような構造を構築することにします。つまり

((a b) c)

の形で、a が bool である場合、if a then b else c と置き換えます。ここで a が bool であるかどうかの判断が必要になりますが、とりあえず保守的に以下のとおりにすることとします

  • true/false
  • lt または eq に引数が 2 つ与えられたもの
  • is_nil に引数が 1 つ与えられたもの

(あとで、もう少し追加します)

加えて \x.e の形を多少プログラムっぽく fun(x) -> e と書き換えてみます。

fun(x2, x8) -> if x2 < x8 { x2 } else { x8 }

最後に、変数名を x0 から振り直すことにして、多少読みやすくしようと試みます。ここまでで

Int.min = fun(_x0, _x1) -> if _x0 < _x1 { _x0 } else { _x1 }

とすることができました。

このくらいまでの変換を galaxy.txt に含まれるすべての関数に適用すると、多少様子が見えてきます。まず先頭に何かデータの埋め込みのようなもの。ついで小さな関数群、最後に複雑な関数群、と並んでいるようです。最初に埋め込まれたデータの意味は使われ方を見てみないとわからないので保留しておき、小さな関数群をまずは見ていきましょう。

先頭の方から :1117 を選び見てみましょう。上記の decompile をすると

:1117 = ap ap s ap ap c ap eq 0 1 ap ap b ap mul 2 ap ap b :1117 ap add -1
{\x2.((((== 0) x2) 1) ((mul 2) (:1117 ((add -1) x2))))}

というところまでできます。もう少し人間に優しくするために、add, mul, div, neg, ==, < 等の関数は+, *, /, -(単項), ==, < という馴染みの演算子を導入して置き換えることにします。ただし format の際には演算子の強さに留意する必要があります。

fun(x2) -> if 0 == x2 { 1 } else { 2 * :1117(-1 + x2) }

また、特に add と neg が組で出てきた場合には、(適当に順序を入れ替えて) 二項演算子の - を導入して置き換えることにします。

fun(x2) -> if 0 == x2 { 1 } else { 2 * :1117(x2 - 1) }

と、この関数は引数 x が 0 の時 1, それ以外の時は 2 * :1117(x - 1) を返す、つまり 2^x を返します。Int.pow2 的に名前をつけましょう。

同様に :1118, :1119 を見てみると

:1118 = ap ap s ap ap c ap ap c lt 2 0 ap ap b ap add 1 ap ap b :1118 ap ap c div 2
fun(x2) -> if x2 < 2 { 0 } else { 1 + :1118(x2 / 2) }

:1119 = ap ap s ap ap b s ap ap c ap ap b c lt 0 ap ap b ap b ap add 1 ap ap c ap ap b s ap ap b ap b :1119 div i
fun(x2, x8) -> if x2 < x8 { 0 } else { 1 + :1119(x2 / x8, x8) }

と変換され、:1118 は log_2, :1119 は log_x_y であることがわかります。

続いて :1120 を見てみましょう

:1120 = ap ap s ap ap s ap ap c ap c ap ap s ap ap b s ap ap b ap b ap ap s i i lt eq 0 i neg
{\x2.(((({\x29.(x29 x29)} ((< 0) x2)) ((== 0) x2)) x2) (~- x2))}

\x.(x x) の式が出てきました。これは logical or で、true = \x.\y.x, false = \x.\y.y に留意して実際に計算してみると

({\x.(x x)} true) c => (true true) c => (\x.\y.x true) c => (\y.true) c => true
({\x.(x x)} false) c => (false false) c => (\x.\y.y false) c => (\y.y) c => c

となります。ここで再びヒューリスティックを持ち出し、(\x.x x) の形が出てきて、かつ続く引数２つが bool であった場合は logical or として扱うことにします。
また、logical or は先の "bool かどうかの判断" に含めることとします。これを適用すると

fun(x2) -> if 0 < x2 || 0 == x2 { x2 } else { -x2 }

となり、絶対値を返す関数であることがわかります。Int.abs 的に名前をつけておきましょう。

次の :1121 は

:1121 = ap ap s ap ap b c ap ap c ap ap b s lt i i
fun(x2, x8) -> if x2 < x8 { x8 } else { x2 }

から、引数のうち大きい方を返す関数とわかります。Int.max と名前をつけておきましょう。

まとめ

ここまで、簡単な decompile と、整数を扱う基本的な関数を読み解きました。
次回予告: 残りの小さな関数群たちを見ていきます。

ICFPC 2020 galaxy.txt を読む (その 0: ICFPC 2020 振り返り)

一月ほど前の 2020/07/17-20 に ICFPC 2020 がありました。今年はここ最近多い対ゲーム的なものに加えて、ちょっと凝ったストーリーとちょっとした interpreter (Garaxy Pad) を作る必要がありました。

この Garaxy Pad に、開始数時間後に与えられる galaxy.txt を実行させると、対戦ゲームのチュートリアル的なことができたわけですが、多分コンテスト期間中に galaxy.txt を読もうとした人はほとんどいないと踏んで、解説を書いてみました。

ストーリー/仕様振り返り

まず galaxy.txt を読むのに必要な範囲でストーリーと Galaxy Pad の仕様を振り返りましょう。

ストーリー

宇宙から信号を受け取るところから始まります。これを、周波数で描画したあと、適当な間隔で改行してやると白黒ビットマップが得られます(こんな感じ)。この画像を心の目で見ると、Galaxy Pad の仕様がわかります。この解読はコンテスト本番中公式 discord でみんなでワイワイやっていて、大体全部解読が終わったタイミング(=全チームに仕様が公開されたタイミング)で運営が galaxy.txt を投下しました。参加者は仕様通りの Galaxy Pad を実装して、galaxy.txt を渡して実行する、というのが次のステップでした。

Galaxy Pad の仕様

galaxy.txt は Galaxy Pad で実行するプログラムが含まれているので、これを読むには Galaxy Pad の仕様を理解する必要があります。以下簡単に紹介します。

数字

数字は整数が与えられます。桁数は指定されていないのですが、現実的には 64 bit 符号付整数があれば多分大丈夫かと思います。正の整数は、2進表記でLSBから順に正方形に並べ、上と左にマーカーが付きます。

負の整数は、まず絶対値を正の整数と同様に表記し追加で 1 dot 左下に加えます。

整数演算

以下のものが提供されました。

inc (インクリメント), dec (デクリメント), add (2項加算), mul (2項乗算), div (2項除算), neg (単項符号反転), eq (2項等値比較), lt (2項小なり比較)

真偽値

Church encoding で定義されます。 

\texttt{true} = \lambda x \lambda y .x 
\texttt{false} = \lambda x \lambda y .y 

特に if (cond) { e1 } else { e2 } は cond e1 e2 で表現されます。重要事項として、式は遅延して評価されます。

コンビネータ

S, B, C, I コンビネータが与えられます。加えて true を K コンビネータとしても使います。

\texttt{S} = \lambda a \lambda b \lambda c . (a\,c)\,(b\,c)
\texttt{B} = \lambda a \lambda b \lambda c . a\,(b\,c)
\texttt{C} = \lambda a \lambda b \lambda c . (a\,c)\,b
\texttt{I} = \lambda a . a

Cons/List

Cons cell も Church encoding のものが使われます。

\texttt{cons} = \lambda a \lambda b \lambda f . (f\,a\,b)
\texttt{car} = \lambda c. c\, (\lambda a \lambda b . a)
\texttt{cdr} = \lambda c. c\, (\lambda a \lambda b . b)

また List は Cons cell を用いて type list = nil | cons (_, list) の形であらわされます。
この仕様では List は要素の型を持っているわけではないので、いろいろな型の要素が混ざった List も可能です(実際に galaxy.txt の中で使われています)。
末端の nil およびその判定関数 is_nil は以下で表現されます。

\texttt{nil} = \lambda c . \texttt{true}
\texttt{is_nil} = \lambda l . l (\lambda x \lambda y . \texttt{false})

Drawing

Galaxy Pad の仕様には描画命令もあります。描画結果はビットマップで、1 になる座標(x, y cons cell) のリストで表現されます。

Send, modulate, demodulate

galaxy.txt を読む分には関係ないので省略します。

Interact

galaxy.txt は描画されたビットマップを出力、(その画像上のクリックイベントを想定して)二次元座標を入力として、UI を提供します。
また、上で省略した send 命令をつかって、運営のサーバと通信をします。
仕様上は以下。

// list function call notation
f38 protocol (flag, newState, data) = if flag == 0
                then (modem newState, multipledraw data)
                else interact protocol (modem newState) (send data)
interact protocol state vector = f38 protocol (protocol state vector)

ap ap ap interact x0 nil ap ap vec 0 0 = ( x16 , ap multipledraw x64 )
ap ap ap interact x0 x16 ap ap vec x1 x2 = ( x17 , ap multipledraw x65 )
ap ap ap interact x0 x17 ap ap vec x3 x4 = ( x18 , ap multipledraw x66 )
ap ap ap interact x0 x18 ap ap vec x5 x6 = ( x19 , ap multipledraw x67 )

ap interact galaxy = ...

要約すると、以下の通り

  • galaxy 関数に state (初期値 nil) と、座標を渡し計算する。返り値は 3 要素 tuple で、flag, 次の state, data
  • flag が 0 の場合は data はビットマップリスト。描画して、ユーザの次のクリックを待つ。次のクリックが得られたら、galaxy 関数に、上で評価した返ってきた state とクリック座標を渡して、再度計算する。
  • flag が 1 の場合 data は運営サーバに送るデータ。結果を読んだあと、galaxy 関数に、上で評価した state とサーバから返ってきたデータを渡して、再度計算する。

Galaxy の中身

galaxy.txt を読み解くうえで、どういう挙動をしたかを理解しておく必要もあります。
さらっと振り返ることにすると、Galaxyはいくつかのステージからなっていました。

オープニング

最初は Galaxy マークをクリックすると、カウントが進みます。
次いで、十字が出てくるので、交点をクリックしていくと進みます。

メインページ

宇宙を背景に、エイリアンのアイコンが散らばっています。
中央の Galaxy マークをクリックすると、対戦履歴モードになります。
またエイリアンをクリックすると、大きなエイリアンが表示され、いくつかのエイリアンは右肩に別なアイコンが表示されており、
クリックすると対戦ゲームのチートコードが手に入るミニゲームモードにはいったり、武器のダメージ解説ページが開いたりします。

対戦履歴モード

まずは対戦ゲームの過去履歴が表示されるモードになります。
ここもギャラクシーマークをクリックしていくと対戦履歴が増えていき、さらにクリックするとチュートリアルモードに進みます。

チュートリアルモード

UIを使って自機をコントロールしつつ、ミニ課題(=相手を倒す)をクリアします。
自爆する、加速する、レーザーを撃つ、分裂する、引力に逆らう、などを体験します。

ミニゲーム

チートコードが入手できるミニゲームが二つありました。一つは回転/反転を許した神経衰弱で、もう一つは〇×ゲームでした。
神経衰弱はペアになっているものをクリックすると消えるので、消えうるものを全部消せればクリアです。
〇×ゲームは、負けない(勝っていなくてよい)形が12パターンあるので、対戦AIの挙動を多少誘導しつつ全パターン出せばクリアです。

まとめ

ここまで、ICFPC 2020 で galaxy.txt を読むのに必要なものをざっと復習しました。
次は実際に galaxy.txt を眺めます。

ICFPC 2014.

でした。 with @kinaba @fuqinho
完全に、年一の日記になっている。。。
まぁ、いつものごとく、自分やったことだけ。

初日

出張中のため早朝（っつーか夜明け前）開始。
すでに脳みそが死んでいる。

問題読む。ひたすら長い。
1.5h くらいは余裕でかかった。英語つらい。
まー、VM書く。振り返ると、いきなりAIから書き始めればよかったかなぁ。
VM最後まで bug ってたっぽい。細かいところの挙動が明らかにおかしい。

実装してると、明らかに spec に穴が。まぁ、例年通り。
適当に書ききって動かし始める。
Visualizer 御用達：http://en.wikipedia.org/wiki/ANSI_escape_code

並行して C++ で書いてもらってた AI を動かしてみると、それっぽい。
夕方(夜) kinaba さんが合流。
夕食食いながら、まぁ LISP ですかね、ということで、
VM、LISP compiler、AI 考える、と task を割り振る。

深夜（lightning division終了前）、寝落ちしたと踏んで、AI を C++ -> GCC に hand compile/assemble。
ラベルの解決するくらいの asm は書いておくべきだった。（毎年恒例の反省）
DBUGはさめないのつらい。
結局、bug とれず。 lightning division は放棄。
就寝。

二日目

まぁ、LISP compiler できてたので、LISP で AI を書き直す。
以降、基本的に AI を C++ から LISP に書く下請けプログラマをひたすらやる。

さくっと LISP compiler 動いてすごいなぁ、さすが kinaba 先生。
ただ、括弧の数一個間違えると、一瞬でメモリを食い尽くして、virtual box を抹殺する凶器であった。
あと、変数 typo すると SEGV で死ぬので、compile 時には gdb が必須。

ゴーストさんは、お任せして、ひたすら lisp と格闘。
Mapをassoc list で実装してたけど、遅くて使い物にならない。

  • > AVLを実装。12年ぶりくらいである。一発で動く。多分ここで今回のコンテストの運をすべて使い果たした。

このころから PC が熱暴走して亡くなりまくる。
コンテスト中、別なものと闘うのも例年の恒例。。。

三日目

とりあえず、fuqinho さんが動かしてた AI を聞いて、LISP で再実装。
なんか、人手があれば C++ compiler 書けばよかったんだがなぁ、と思ったりした。
とにかく LISP つらい。

関数つくって、0 で上書きする、という謎のテクニックが作成され、ようやくグローバル変数が導入される。
あと、時刻の計算とか。
この辺から LISP compiler がいろいろ直って、普通にプログラム書けるようになる。
型チェック欲しい。

らむだまんさん食われまくるので、いろいろ細かい修正。
とりあえず、全力で逃げるのと、Power pill を追いかけにいく、フルーツ待機。
敵がよってくると、うっかりクリアしてしまうので、高得点がとれない。
配列に O(1) で触れないのが、大変ストレスフル。

あと、胃痛で死に始める。やはり出張中はだめだ。。。
巨大マップ用に枝狩りをあちこち入れる。

一応 LISP なんだけど、どう見ても手続き型にしか見えないソースを書きまくる。
関数の最後の行だけ閉じ括弧が多い謎コード。最大 18 個だった(数えた）。

胃痛がやばくて、ちょっと仮眠。仮眠すばらしい。あと、三共胃腸薬。

チーム名が決まらない。コードネームにつかったFOOを、何か意味あるものにしよう、という話に。
いくつかあげたけど、全却下された orz。
チーム名も決まって submit 。
のこり 5 分、なんか、たまに AI が死ぬケースが見つかる。
見つかるんだが、謎過ぎる。そのまま終了。

なんかできた AI

とりあえず、pill 幅優先探索。近くになかったら、適当にありそうなほうに向かう。
ゴーストよってきたら、逃げる。power pill あったらそっちに向かう。
フルーツは最優先。２個出てなかったら待つ。うっかりゴール避け。
power pillの隣でまつ。ゴーストがよってきたら食いに行く。
power pill chain つなげまくる AI とか書いてみたけど、いまいちだったので、没。

くらいかな。簡単なマップだとそこそこ動く。
けど、ゴースト次第で運ゲー。
ところで、world-1って、spec 違反じゃないんかね。2x2あるし。。。

反省

腕力にたよるのは、いい加減やめてみるべき。
C++は人間がコンパイルするもんじゃないな。
LLVM BE とか覚えておけば来年は役に立つ気がする。
IFPとそろったので C をどこかから調達()できればよかったなぁ。

compiler とか asm とかがもりもり作られていくのを眺めていた。
let が導入されたときに、refactoring して書き直したんだけど、
compile 結果が同一であったので、compiler の気持ちはわかっていたらしい。

まとめ

結局、あんまりちゃんと動けてなかったなぁ、という感じ。
出張しんどい。

いつも思うんだけど、VM 書く系の部分は、なんか validator あるとうれしいよなぁ、と思う。
コレとおっておけばいいよ、的な。
どうせ、Judge も spec にミス埋め込むし。人間だもの（みつを）。

今年は、心躍る感が若干弱かったなぁ。
AI の年はだいたいそうなんだけども・・・。

さて、寝よう。

雑感

今年のは結構いい感じのサイズだなぁ、と。「もう1日欲しい」というところで終わるあたりが、ちょうどいい。
主催のみなさまありがとうございました（と日本語で書いてもダメか・・・）
こういうの書いてるとやっぱり pattern match が欲しくなりますね。というか、matcher 書くべきだったかなぁ・・・。
くわえて、あちこち相互再帰してるので、変な無限ループに入るケースがなくなるように気をつけるのは、
だいぶ面倒だなぁ、と思ったり。
今回はC++だったんですが、メモリ管理やっぱりちょっと気を使いますね。まぁでもGCよりはマシかな。
チーム funny quotes はきっとメンバーの誰かがなんとかしてくれるハズ。
チームでわいわいやるの楽しいですね、やっぱり。ありがとうございました。
来年も出たいなぁー。