Hatena::ブログ(Diary)

www.kotha.netの裏

2010-06-21

ICFP Programming Contest 2010

00:12

出た。

今年の課題は、車と燃料を設計/販売して金儲けというもの。といってもリアルな設計ではなく、車は特定の形の連立不等式で、燃料はその解で、それぞれ表現される。車と燃料をセットで提出するのが基本で、さらに他人の設計した車に適合する燃料を作ることができればその利益の一部を奪えるというルール。

追加要素として、車と燃料は三進数で符号化して提出しなければならないが、そのエンコード方式は非公開。さらに燃料については三進コードを直接送るのではなくコードを生成する回路(これも詳しい仕様は非公開)を送るというものだった。非公開仕様についてはサーバからのエラーメッセージをもとに試行錯誤で把握することが要求された。

経過

開始直後。課題を読む。本題に到達するまでのハードルの高さに驚く。キー回路を読もうと紙の上で試行錯誤していたら構文は比較的すぐに分かった。

回路を組むためのコードをHaskellで書く。深く考えずにStateモナドを使ったが良い選択だったらしい。回路内のループがちょうどControl.Monad.Fix.mfixで表現できた。再帰的do記法をこんなに多用したのは初めて。

一番簡単な回路として左入力と左出力を短絡した一個のゲート"右ブロック"と、その逆の"左ブロック"をそれぞれ走らせてみて、ゲートが左右非対称であることが分かる。また、グラフとして同じ回路でもゲート番号の順番によって挙動が違うことが分かる。具体的には、ゲートaからゲートbへの信号はa>=bのときのみ1クロック遅れる。だから二つの回路を直列接続する際に"順接続"と"逆接続"の二つの方法を用意すれば良い。これは普通に関数として表現できた。

時刻0での遅延入力はどうせ0固定だろうという推測から、右ブロックをn個逆接続した回路は、最初の(n-1)クロックの間、入力に関わらず一定の数列を出力すると予測する。試したところ22110を繰り返すようだった。同様のことを左ブロックについて行うと01210を繰り返した。これで固定の数列が生成できるようになったので、二つの数列を一つのゲートに入力して出力を調べることでゲートの真理値表が完成した。この時点で開始+3時間。

これをもとに回路のシミュレータを実装。開始+4時間でkey回路が動く。

次に、任意のtrit(三進数字)列を生成する回路を設計する問題にとりかかる。nクロックの間一定の数列を出力する回路は既にあるので、これのコピーを二つ使って出力の差を取ることでnクロックの間0を出力し続ける回路ができる。同じ発想で1と2を出力し続ける回路を作成し、逆接続で一個ずつ遅延を挟むようにすることで長さnのtrit列を出力するものができた。これでkey prefixを生成する回路を作成。開始+5時間で最初の燃料を提出する。サーバの表示を信じるなら一番乗りだった。

このロジックでは長さnのtrit列を生成する回路のゲート数がO(n^2)になって嫌なので、最悪ゲート数を2*n+1に抑えたエンコードに切り替える。開始+10.5時間。

車と燃料の構文の推測に移る。燃料については、不完全な入力でもサーバがタンクの数と行列の次数をエラーメッセージで教えてくれるので、それをもとに整数エンコードを推測する。しかし燃料に関して試行錯誤してもdimension mismatchばかりで一向に進まないので車を先に考えることにする。かなり試行錯誤したあげく開始+14.5時間で車記述のパーサが完成。

残るのは燃料だが、データの先頭にヘッダとして「タンク数」と「行列次数」があると思い込んだために苦戦した。大量のdimension mismatchにめげそうになったところで燃料記述の構造が分かる。開始+17時間。分かってみれば簡単なことで自然数のリストのリストのリストに過ぎなかった。

この時点でようやく他人の車に対して燃料を供給できることになる。主催者の用意したと思われる簡単な車いくつかについて燃料を求めてみる。また、自分でも車を作ってみる。まず2x2行列を二つランダムに生成して燃料とし、長さ10の不等式を10本やはりランダムに生成して車とした。

投稿した車に他のチームが燃料を付けてこないので、適合する燃料を見つけるのはかなり難しいのではないかと考える。それならば素早く車を量産することが最適なので、易しい車を見つけて解いては車を投稿する大量生産の方針を決める。車の生成を自動化した。開始+19時間。

易しい車が大量に追加されていたので、ひたすら解をコピペしては新しい車を投稿する単純作業。車の作成が燃料の探索より圧倒的に簡単なら、先に車を作った者勝ちのクソゲーではないかと思い始める。それでも、仮に突破法が見つかれば大量生産した車は全滅、という恐怖に駆られて、生成法を少しずつ複雑にする。

25ほど車を提出したところで雲行きが怪しくなってくる。初期の車がいくつか破られたのを確認する。これを見ても強気で行列数を6個に増やして生産を続行した。しかしどうやら見通しが致命的に甘かったらしく、時間が経つごとに被突破数は加速度的に増加した。あらためてテストしたところ自分の車のかなりの部分が単なる乱数攻撃に耐えられないことが分かったが後の祭で、24時間終了時点で、出した65種ほどの車のほとんど全てが破られる結果になった。

この時点までずっと上位五チームに入っていたが、24時間経過前にほとんど破られずに車を量産したチームがあったように見えるので、Lightning Divisionでも良くて二位だろうと思う。

既に車の提出可能枠のほとんどを使い果たしているのでやる気を失う。残された勝ち手段は強力な燃料探索手段を見つけることだと考えたが、探るべき方向すら分からない。行列を少しずつ変形して不等式に反する部分を減らすという方針の局所探索器を作るのがやっとで、それも満足な性能ではなかった。三日目に入ると車の数が爆発的に増えて、勝ちを目指すならHTTPクライアントを書いて全自動燃料提出が必要になるだろうと思った。しかし良い探索器を作る目処がまったく立たないのでここで試合放棄。最終順位は26位だった。

結局、本題である車と燃料の生産については大したことができなかった。おまけの謎解き要素のおかげで一日目によい成績が残せたのが幸運だろう。

トラックバック - http://d.hatena.ne.jp/mkotha/20100621/1277133120