ICFP Programming Contest 2010

contest

http://icfpcontest.org/2010/
年に一度のお祭り、今年も参加しました。1人チームです。

score: 102.991
others' cars solved: 178
cars submitted: 0

で70位くらい？　1台くらいは車を出荷したかったなぁ。次から次に現れてくる謎を解くのに夢中であっという間の週末でした。プログラミングはあまりやらなかったけれども、論理パズル好きとしてはこういう展開は面白い。
1人チームに不利な条件で、月曜に休み取ってなくてラスト20時間なにもできなかったという割には頑張った。去年は下から数えた方が早かったくらいだし。


以下時系列に

  • 18日21:00 問題を読み始める、短くていい感じ
  • 18日22:00 やることは把握したので回路の文法を推測すべく適当な文字列をサーバーに投げる
  • 18日23:00 回路の文法はけっこう単純だった。gateのtypeは常に0なのは後の拡張のため空けておかれてるのだろうか。引き続きgateの仕様を探るべく単純な回路を投げる
  • 19日01:00 gateの出力は入力のみから決まるものと仮定して推測していたら矛盾が出てきてしまった。これは内部で状態を持っているのか…！　と早くも絶望しかける
  • 19日02:00 問題文にあった"backward"なwireが何をさすのかを勘違いしてますねこれ。直接自分に戻すwireのことだけを指していると思っていたのだけど、それでは大きな回路でつじつまが合わなくなってしまう。gate番号が小さいやつに向かうwire全部のことか
  • 19日03:00 gateの真理値表が完成。サンプル回路を実行してkey prefixを得るべく回路のパーサとシミュレータを書き始める
  • 19日05:00 回路シミュレータができてkey prefix判明。きりが良くなったので寝る
  • 19日16:00 活動開始。うっかり11時間睡眠
  • 19日16:30 オウム返し回路を作ってサーバー入力の先頭17bitを得る
  • 19日18:00 とりあえず回路を組み上げるための部品を揃えようと、0を入力され続けると常に0を返す（1,2を返すバージョンも）回路とか、何を入力されても0を返す回路とか、1と2を反転させる回路とか、そんなのを作ってた
  • 19日19:30 任意の出力を生成する回路の方針が立つ。backwardなwireでは1サイクルの遅延がかかることを活かして、オウム返し回路をbackwardにN-1個つなげることで「はじめ0を出力してNサイクル目以降はiを出力する回路(i=0,1,2)」が作れる。そしてそれらをN=0〜M-1までAdder（のようなもの）で連結することでM文字の出力が作れる、という感じ。gate数が文字数の2乗オーダーになってしまうが、それを縮めるためにかけられる時間はないし、スコア的にも最小と最大ではせいぜい2倍しか違わないし、早く先に進みたいしということで、回路の小型化はしないことにした
  • 19日24:00 望みのビット列を与えたら、それを出力する回路をはき出す回路ジェネレータができた。しかし動かしてみたらバグっている…。この辺でTopCoder Openの予選のため小休止
  • 20日03:30 バグはたいしたものではなくてすぐ取れた。というわけで最初の車に対して燃料を供給できた！ 60番目くらい
  • 20日05:00 スコアボードで得点が入ったのを確認して就寝
  • 20日13:00 起床。最終的な目標を「carやfuelの仕様をそれなりに解読し、いくつかの車に対してfuelを供給する」というあたりに置く
  • 20日14:00 とりあえず、提出されているcarのビット列を見て規則を推測しようとする。似たようなcarをサイズ順に並べてみたら、明らかにビット列がインクリメントされていっている様子が見えるものの正確なフォーマットがなかなかわからない…。あと平行してサーバーの17ビット目以降の入力を推測する作業も。どうやら"2"は偶数個連続してないと怒られるみたいなので（※後でわかったことだが必ずしもそうではない）、それを手がかりに1ビットずつ
  • 20日15:30 テキトーに投げてたら2台目の車に対して「1111」というfuelが通った。どうやらtank1個の車は同じfuelでいけるみたいというのも把握。そして大量の車を前にして、上位の人たちが「提出状況管理をどうするか」みたいな話をしていた意味を知る…、まあそこにかけられる手間もないのでベタにテキストファイルに書いていた。提出するのも、ちまちまURL直打ちで。この日いったい何百回「/solve/form」をアドレスバーに入力したことだろうか。プログラマ失格ですね
  • 20日21:00 ternary streamのシンタクスは依然わからないままだが、何となく100くらいまでの数値は調べられたので、さしあたってはこれで問題なさそう。リストのサイズを表しているところとそれ以外とでフォーマットが違うみたい？
  • 20日23:30 車のフォーマットが完全に見えた。「Auxiliaryなchamberでは、上のpipeと下のpipeの間に挟まっているのは0ではなく10」というのが最後の1ピースだった
  • 20日24:00 簡単そうな車を片っ端から給油していく。手作業で。これはつらい…
  • 21日01:00 複数のingredientを使うfuelのフォーマットを見つけたかったが、"dimension mismatch"地獄にはまってしまって進展せず
  • 21日02:00 まだまだクソゲーな感じの大衆車が湧いてきていたので、解けるやつに適当に給油しておしまい
  • 21日21:00 提出状況の詳細が出ていたので見てみる。おい僕の回路でかすぎだろこれ…。最初の車を提出している220チームくらいのうちワースト8番目だった。ははは


あとはfuelのフォーマットを完全に解析して、carのパーサとfuelのフォーマッタ書いて、とまでやったら後は数学の問題で、ここでやっと本当のスタートにたどり着いた…、という感じでしょうか。月曜も丸1日使えてたらその辺まではいけたかな。
回路は、ちょっと考えれば少なくとも文字数にリニアなgate数にはなりそうですね。
順位を狙うのならば、小さい回路の設計を最初にもっと頑張っておくとか、提出を自動化するとかやるべきなのでしょうけれど、この大会にあまりそういう動機はないので好きにやりました。
ほかのチームの人たちの参加記を見ると、複数人でわいわい参加するのすごく楽しそうだ。特に今年の問題は役割を分担して進められるものでしたし。来年は周囲の人を誘ってみよう。


結局書いたコードの量は、回路のパーサ・シミュレータ150行 + 回路ジェネレータ550行（全部Java）というくらいでした。回路ジェネレータは無駄に大きいに違いない。
しかし去年より倍以上の時間取り組んだのにコード量は少なくなっている。入り口のところでかなり論理パズル的おもむきが強い問題でした。


期間中の3日間で体重が2kg落ちました。楽しかったけれども体には悪いと思います。