sshi.Continualsshi.Continual読者になるsshi.Continualこの広告は、90日以上更新していないブログに表示しています。読者になる広告を非表示にするもっと読むコメントを書く2010-06-27ICFPのコンテストに参加しましたhttp://icfpcontest.org/2010/一週間遅れですが、簡単なレポートを。ここに書くのほぼ一年ぶりか...今年は流れで某Mくんと2人でチームを組んで参加。チーム名tokorobashi。名前の由来は近いうちに明らかになるかもならないかも。今年は特にサーバへのsubmitとかを便利にしてくれるインフラ整備をがんばる余地がいっぱいあったので、もうちょっと人数多くないと戦えてなかったかもしれない。結局、「本番」に到達できなかったのであんまり関係なかった。大会の詳細はどっか他のサイトを見てください。最初はサーバが重くてチーム登録ができなかったので、とりあえず英文よむよむよむ。結局、サーバの調子をみてチーム登録をやりながら、気分を落ち着けるために和訳文作成をはじめてしまって日付が変わるくらいまでその作業をしてた。Mくんはそんな僕をしりめに最初の回路構造を考えてたぽい。0:00〜日付が変わったころに、だいたいの問題を理解してなにはなくとも「回路」を生成しないと話にならないことに気がつく。問題にのっているサンプル回路を眺めてフォーマットを想像する。一つのゲートが二入力二出力なので、1行が1ゲートをあらわしていて、入出力の先が書いてあるんだろうなあ、くらいの想像はついた。最初の行と最後の行の意味がわからず1ゲートの回路(と思われるもの)をいくつかsubmitしてテスト。最初はエラーばっかし。ログを見返してみたらもうこの時点で「これ入力も推測せなあかんのか?それとも定数を出力するような回路が組めるのか?」と結構本質的なことをしゃべってる。早い時点で後者だと信じて突き進むべきだったよ。1:00〜1時間くらい試したところでM君の「最初と最後はXの場所っぽいよな」という発言で回路記法をようやく理解。この時点では、遅延する線としない線の法則がわかっていなかった。記法がわかったので、1ゲートのいろんなバリエーションを入力して出力を収集。1ゲートは4パターンしかないので、それぞれに名前をつけて共有したりしてた。してるうちに、ゲートを通過させなければサーバの入力が取れるなと気がついて、全部の出力が自分自身の入力になっているゲート一個だけの回路を入れてみる。X:0R0L0#0R0L:X無事にとおってサーバ入力がとれた。これがとおってから「X::X」で充分だったことに気がつく。実はここでゲートの入出力表を作成するのには充分な情報が得られているらしいのだが、「遅延」のセマンティクスがまったくわかっていなかったので、そこでつまづいてしばし悩むことになる。あとで聞いてみたら、会社の先輩も同じところでつまっていた。2:00〜どういう線が「遅延」されるのかさっぱり理解できていなかったので延々悩む。「右出力は常に遅延されるのでは?」などという頓珍漢な仮定を僕がだしてしまったので余計迷宮入り。このへん良く覚えてないが、4:00くらいまで悩んで、わからないなりにも回路シミュレータをrubyで実装したりしていた。気がついたら次の日の昼頃になってた気がするが良く覚えていない。19:00〜悩みながらなかなか寝られなかったりしたので、起きたら夜だった。寝てる間に、M君がゲートが2つの回路を自動生成して出力を収集してくれていた。同じ出力をする回路とかでてきて、なかなかおもしろい結果に。遅延のセマンティクスに気がつく。21:00〜単純に、「自分より前かあるいは自分のゲートに出力されている線が遅延される」ということにやっと気がついた。配線のトポロジは同じでもゲートの順番が違う回路をちゃんと試していたらもっと早く気がついていたかもしれない。なんにせよここで、配線の初期値(後ろのゲートの出力が入力になっている場合の、初回の値)の推定を含めて入出力表を求める作業にはいれることになった。回路シミュレータを改造して、いままでの回路と既知の出力値をぶちこんで入出力表を埋めていくプログラムを組んだ。人間が解くように、「確定できるところだけ表を埋めていく」ようなコードにしてしまったので、1ゲートの回路だけじゃ求まらなかった。M君が収集してくれた2ゲートの回路の結果もいれたら動いた。2、3バグを直したらすぱーんとそれっぽい表ができて喜ぶ。初期値も0以外では成立しないという結果もでた。「ありうる表を全て試して、まずいことが起こった表は捨てる」という方法だと1ゲートの回路だけで表がでたみたい。僕は全探索への苦手意識がありすぎる。全探索でいける計算量を見積って探索できるようにならなきゃだめだな。