ICFP Programming Contest 2013
https://research.microsoft.com/en-us/events/icfpcontest2013/
今年も楽しくソロ参加でした。ソースコードはこちら。
http://irorin.org/icfpc2013_irori.tar.gz
問題
BV という単純な言語で書かれた 64bit 整数上の関数があります。入力となる数を好きに選んでコンテストのサーバーに送ると結果が返ってくるので、この関数の式を推定してください。ただし、
- 式の大きさと使われている演算の種類はあらかじめ与えられる。
- 推定した式が間違っていたら、反例となる入出力の値が返される。
- いちど問題に挑戦し始めると、5分以内に正解しなければ得点できない。
問題が 1000 問以上あって（途中で増えたりした）、72時間以内に何問解けるかな、という問題でした。
使用言語
ソルバ本体は Haskell で、フロントエンドを Ruby で書きました。
Haskell は数年ぶりに触ったけど意外に忘れてませんでした。Haskell 98 が最新規格じゃなくなっててびっくりしたのは秘密です。
あと、BV の S 式を Haskell の read で読めるように変換するためだけに Scheme もちょっとだけ使いました。
残念ながら Unlambda は今年も出番がありませんでした。
マシン
自宅の PC 2 台 + ラップトップ 1 台。手元の計算資源だけで頑張りました。無課金プレイです。(?)
複数台使ったのは時間内に全問終わらせるためで、同じ問題を並列で解かせたりはしていません。
戦略
4種類の問題 (simple, fold, tfold, bonus) について、それぞれ専用のソルバーを作りました。といってもやってることはほとんど同じで、
- 数十個の入力/出力の値のペアを用意します。
- Spec にある演算を使って、小さい順に式を生成していきます。式を最適化して重複を取り除きます。
- 生成された式を 1 で用意した入力値で評価して、すべて出力値が一致すればその式をサーバーに送信します。mismatch が帰ってきたら 1 のペアに追加して 2 に戻ります。
で、問題のクラスごとに細かい枝狩りなどを入れていきます。細かい工夫などはソースを見てください（めんどくさくなった）。
結果
感想
ICFPC にしては珍しく、関数型言語が活躍しそうな問題でした。難易度調整も絶妙で 3 日間フルに楽しめました。
あと個人的には、今回みたいに手元で実行して結果だけ送信する方式のほうが好みです。AIを提出する方式だと、いろんな状況に対応できるように作りこむのって一人じゃモチベーション的にも時間的にもつらいんですよね。他方この方式だと計算資源を豊富に使える人が有利になっちゃうというのもありそうですが。
