ICFPC 2024 参加記
2024年6月28日から7月1日にかけて開催された ICFPC 2024 に参加した。
チーム
例年通り Gon The Fox (総計7名) で出場した。当チームは2019年頃からメンバーを多少変えつつ参加しており、私自身は2020年から毎年参加している。
問題概要
ICFP Language という関数型言語の仕様が与えられる。 ICFP の式を送ると ICFP の式が返ってくるような HTTP endpoint が提供されており、それを使って以下の5カテゴリに分かれた問題を解く。
- hello
- ICFP を使用した基礎的な通信を行う
- lambdaman
- 2次元グリッド上の全空きマスを通る経路を求める
- spaceship
- 加速・減速できる宇宙船を使った2次元 TSP
- 3d
- 競プロ (algorithm) のような問題を、 Befunge に時間遡行を足したような言語で解く
- efficiency
- 与えられた ICFP 式を評価した結果の整数を求める
実際には最初からすべての問題が公開されている訳ではなく、ある程度提出が進むと新たなカテゴリが解放される。
コンテスト参加記録
コンテスト開始前から終了までに取り組んだ様子を記録しておく。
開始前
チームで使う Discord server と GitHub repository を作成した。
例年弊チームでは特に作戦などを決めておらず、各メンバーが個別のディレクトリをもって自由な言語でプログラムを書いていたが、
今年はせめて Rust だけでもコードベースを統一しようと思い 職権を濫用し repository に Cargo の設定ファイルと Rust の CI をセットアップしておいた。
1日目
ICFP Language の仕様が公開された。 まず文字列のやり取りができないと問題文すら取得できないので、文字列の encode / decode 関数、 次いで shell (ユーザーが入力した文字列を encode して POST し、レスポンスを decode して表示するプログラム) を実装した。
この時点では lambdaman と spaceship が解放されていた。 問題の入力はいずれも文字列なのだが、サーバーから取得できるのは ICFP の式である。 式が単に文字列リテラルである場合は decode すれば良いが、「評価すると文字列になるプログラム」である場合もあった。 そのため (比較的 interpreter 実装経験のあった) 私が ICFP interpreter を実装することになった。
ICFP Language 概要
ICFP Language は簡単に言うと型無し Lambda 計算であり、以下のような特徴を持つ。
interpreter 実装
Rust で call-by-need 評価戦略の interpreter を実装しようとした (後から考えれば、call-by-need はおそらく過剰であった)。 数時間粘ったが再帰 (Y combinator) が動かず、一旦就寝した。
2日目
起床後改めて interpreter に取り組み、昼過ぎに再帰が動くようになった。 ほとんどの問題は decode できるようになったが、実行すると再帰が深く stack overflow になる問題が1つだけ存在した。 これについては ICFP のプログラムを読解し、ループを使った Rust のプログラムに書き換えることで decode することができた。
チームメイトが lambdaman と spaceship および解放された 3d のソルバーを着々と実装していたのでしばし休憩を取る。
夕方頃に efficiency が解放され、言語の問題のようだったので取り組むことにする。
efficiency
概要
評価すると整数になるような ICFP Language のプログラムが与えられる。評価結果の整数を求めて提出する。 判定は正答と誤答だけで、最適化などの目標は無い。全13問。
やったこと
問題1は入力を intrepreter に与えるだけで解答が得られたが、それ以外の問題はすべて stack overflow になった。 interpreter の実装ついでに ICFP を Lisp のような言語に変換するプログラムを書いていたので、それを使って他の問題を解読していく。
問題2・3
無駄な再帰と加減乗除があるだけなので、再帰を除いて計算する。 もしかして interpreter に定数畳み込みなどを実装しないといけないのか？という疑念に駆られる。
問題4
再帰で40番目のフィボナッチ数を求めるプログラムなので、フィボナッチ数を検索して提出した。
問題5
以下の条件を全て満たす整数 x を線形探索で求めるプログラムになっている。
- x > 1000000
- x は素数
- x+1 は2の冪乗
(定義は異なるが) メルセンヌ素数 を調べて提出する。
このあたりで機械的な最適化では解けないことを悟り、全て人力で解読する方針を固めた。
問題6
問題5と類似した構造で、以下の条件を満たす x を求める。
- x > 30
- x 番目のフィボナッチ数は素数
条件を Discord に書いたらチームメイトが答えを求めてくれた。
問題12
2重の再帰を行っていて複雑だが、あまり典型的な処理には見えない。愚直に Rust に移植して解こうとする。 素朴な実装 では再帰が多く実行が終了しないが、 再帰の引数がほとんど変化しないことに着目して 書き換える と解が得られる。
問題13
再帰で長い文字列を作ってその長さを求める。チームメイトが解いた。
問題7・8・9・10・11
急激にプログラムが大きくなり、変数も増えるが、類似した構造の繰り返しになっている。 多数の条件式が論理積で接続されているので、SATっぽいという直観を得る。
改めて問題7・8を読むと、SAT の解を二進数で encode したものを求めるプログラムであることが分かる。
一方の9・10・11は v11 ～ v99 の変数と v11 != v12 のような制約が多数あり、数独の解を九進数で encode したものを求めている。
解けそうなことが分かったところで、上記の考察を Discord に書き残して就寝した。寝ている間にチームメイトが全て解を求めてくれて efficiency の完答を達成した。
3日目
相対的に順位の低かった lambdaman に取り組むことにした。
lambdaman 問題概要
2次元のグリッドが与えられる。各マスは壁 (#)、空きマス (.)、スタート地点 (L) のいずれかである。
プレイヤーをスタート地点から上下左右に移動させ、全ての空きマスを通過するような経路を求めよ。
提出
「U R D L からなる文字列」に評価されるような ICFP 式を提出する。
ICFP 式の長さ (バイト長) が短いほど上位となる。
lambdaman 提出状況
この時点でチームとして提出していた解答は大きく分けて以下の3種類だった。
1 と 2 についてはソルバーで短い経路を探すことが解答の短さにつながるが、この時点からソルバーに関わるのは難しそうなので 3 で解けそうな問題に取り組むことにした。
lambdaman の問題の中には規則的なグリッドのものがあり、例えば問題6 では
R を199個連結した文字列で正答することができる。
また、競技中は、問題ごとに順位と全チーム間のベストスコアが閲覧できるようになっていた。
lambdaman ゴルフ
規則的な経路で解けそうな問題6・8・9に取り組んだ。 当初は何らかの言語から ICFP へのトランスパイラを実装しようかと思ったが、efficiency の解読などをしている間に ICFP を普通に読み書きできるようになっていたので直接 ICFP を手書きすることにした (とは言え文字列や整数のエンコードは辛かったので途中で簡単なアセンブラだけは実装した)。
問題6
まずは前述の問題6を 92 bytes から 79 bytes まで削減したが、1位の 73 bytes まで削減する見通しが立たず苦戦する。
するとここで、問題文に「壁に当たるような移動は無視される」という旨の記述があることに気付いた。
3日目に至るまで「壁に当たるような移動をしてはいけない」という誤解をしていたのは本当に致命的だったのだが、
ともあれ問題6については R を216個連結した文字列を生成するコードで1位タイを獲得した。
問題9
問題9は開けた長方形のグリッドであり、 RR...RRDLL...LLD を繰り返して蛇腹状に降りていくことで正答できる。
114 bytes まで短縮して限界を感じていたところ、チームメイトが 110 bytes の解を提出し2位タイを獲得した。
問題8
問題8は螺旋状の細い道になっており、 DD...DDLL...LLUU...UURR...RR を繰り返すことで正答できる。
色々試した結果、 DLDL...DLDLURUR...URUR を繰り返すと、処理する文字列が4種類 (D, L, U, R) から2種類 (DL, UR) に削減されてコードを単純化することができた。
この方法で9位タイを獲得した。
その他の問題
壁にぶつかっても良いことを利用して、「何らかのパターンを十分な回数繰り返す」方法で小さな問題が解けるのではないかと考えた。 しかしながら、試した範囲では同じところでループに陥ってしまい、正答には至らなかった。
lambdaman 全体を通した短縮テクニックとしては Y combinator による再帰や church 数による繰り返しを試みたが、結局文字列を繰り返すだけならダブリングのような手法が最も効率的であった。
この方法では、例えば受け取った文字列を3回繰り返す関数を f として、 f(f(f(f(s)))) と呼び出すことで s を81回連結した文字列を得ることができる。
より複雑な関数を使うと効率的に解ける問題もあったとは思うが、この辺りでコンテスト終了時刻になってしまった。
振り返り
個人として
言語処理系実装
24時間以内に処理系を実装できたので ICFPC 2020 の時よりはある程度成長したと実感したが、call-by-need に囚われなければもう少し速く実装は可能だったと思う。 Rust の module を適切に分けて設計した結果、チームメイトも処理系の一部 (演算子のパースなど) を実装してくれたり、提出ツールにもコードを再利用できたりした点は良かった。
efficiency
コンテスト内に完答できたので満足している。問題も取り組んだ中で一番面白かった。 強いて言えば、処理系に最適化を実装するか悩んだ時間が無駄だったので、問題をよく分析することを優先すべきだった。
lambdaman
コードゴルフは普段そんなにやらない (特に関数型言語ではやったことない) が楽しかった。 いつの間にか ICFP を普通に書けるようになっていたことは自分でも驚いたが、最終的にはもっとコードを書きたかったという感想を抱くほどであった。
終盤までルールを誤解していたことが本当に悔やまれる。
チームとして
3d のうちの1問を除いて全ての問題で正答を得た。
最終順位 16位
- hello 1位タイ
- lambdaman 25位
- spaceship 10位
- 3d 22位
- efficiency 1位タイ
ということで私が参加した中では最高順位を獲得できた。 spaceship や 3d についてはほぼ関与しなかったのだが、それぞれビジュアライザなどが実装されていて優秀だった。
チームワークの面でも今までで一番連携が取れていたように感じた (コンテスト開始前の下準備が功を奏したかもしれない)。 来年以降も是非とも出場したい。
