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 で定義されます。
特に if (cond) { e1 } else { e2 } は cond e1 e2 で表現されます。重要事項として、式は遅延して評価されます。
Cons/List
Cons cell も Church encoding のものが使われます。
また List は Cons cell を用いて type list = nil | cons (_, list) の形であらわされます。
この仕様では List は要素の型を持っているわけではないので、いろいろな型の要素が混ざった List も可能です(実際に galaxy.txt の中で使われています)。
末端の nil およびその判定関数 is_nil は以下で表現されます。
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 マークをクリックすると、対戦履歴モードになります。
またエイリアンをクリックすると、大きなエイリアンが表示され、いくつかのエイリアンは右肩に別なアイコンが表示されており、
クリックすると対戦ゲームのチートコードが手に入るミニゲームモードにはいったり、武器のダメージ解説ページが開いたりします。
まとめ
ここまで、ICFPC 2020 で galaxy.txt を読むのに必要なものをざっと復習しました。
次は実際に galaxy.txt を眺めます。