読者です 読者をやめる 読者になる 読者になる

ICFP Programming Contest 2010 終わり

全体

チーム名: yarunee
使用言語:Ruby、C
メンバ:@、 @、 @、 @、 @
MLで誘ってはみたが、メンバは結局去年と変わらず。会社の新人さんを誘惑するも、乗ってこず。
「一度くらいはやってみるべき」とちょっぴり残念思うけれど、ま、個人の自由だからな。
 

1日目

夜の9時まで会社に残り、みんなで問題を読んだ。@さんの圧倒的な英語力のお陰でスラスラ読んでもらえた読めた。
とりあえず、例題の19Lのやつは「大体こんな文法だろうなぁ」と推測。帰宅した。
(思えば、我がチームの絶頂期はココであった)
 
次の日の朝、昼前に会社に来たが誰もいない。
しょうがないのでシミュレータの雛型をぼちぼち作ってみたりしていた。
 
昼過ぎにメンバがぼちぼち来た。@さんから回路の構文を説明してもらうなど。
以下の回路の出力がきっとサーバ側の入力なのではないかと「推測」。これが大きな誤算となった。

0L:
X0R0#X0R:
0L

 
さくっとMechanizeで回路をポストするスクリプト作成。
 
上記の回路の入力をもとに最小の回路を組んで、出力から素子の動きを予想。
ここは穴埋め的に「人力」でやってしまった。入力が違うので、案の定2素子くらいで矛盾がでる。
バックワードのワイヤを0と考えていたから、ここが1なんじゃないか、とか、2なんじゃないか、とか。
そっちの方の計算もやりだして、完全に詰んだ。
 
しばらく時間がたって。海外のircチャンネルを見ていると。

hints: 4 characters

というヒント発見。なんぞ。と思っていると、@さんが以下の回路を通してくれた。
 

X::X

 
これにより、正しい入力が得られて、また「人力」で、全ての穴埋めをして以下の表が完成した。

L:         
 L\R| 0 1 2 
 ---+-------
  0 | 0 2 1
  1 | 1 0 2
  2 | 2 1 0

R:
 L\R| 0 1 2
 ---+-------
  0 | 2 2 2
  1 | 2 0 1
  2 | 2 1 0

 
@さんと「バックワードワイヤってなんだろうね」と言う話をした。
単純に素子のIDの大きいものから、小さいものへのワイヤじゃないか、という話もしたが、それだと回路っぽくなくね、という話になる。
 
そこで、入力から出力への流れで素子のランク付けをし、ランクが低いものから、高いものへのワイヤをバックワードと定義してしまった(後日談有り)。
 
そして、@さんがシミュレータ作成。私は幅優先のランク付け処理作成。
19Lのやつも通ったよ。わーい(後日談有り)。
 
(1日目終了)
 

振り返り

まず、穴埋めを「人力」でやったことが駄目な感じ。
また入力は不明なものとして、kinabaさんのような解き方をするのがよかったなぁ。
 
凄い人たちのチームは我々の1日目の作業を開始4時間くらいでこなしているらしく、本当に凄い人凄いなと思う。
 

2日目

朝は家でkeyprefixを出力する回路について考えていた。が、全然駄目。
 
昼過ぎ頃に会社に向かう。
@さんと会話で回路を総当たりで作成して目的のものを作ろう、という話になる。
ケースを考えてみると19素子で2億ケースくらいだったから、まーいけるかなぁとこのときは思った。
 
私は「シミュレータが早いことが絶対条件だ!」と何故か頑なに信じ込み、幅優先ランク付けのC化に着手。
1時間くらいでRubyのC拡張ライブラリができるが「あ、これそんなに計算量ないや」ということが判明。
(参考:「早すぎる最適化」)
 
@さんのシミュレータバグ取りのお手伝い。
前日に通っていたと思っていた19Lのテストが実は通っていないことが分かったからだ。
 
私が最小のテストケースを作成、以下で転けてしまうことがわかった。

 ---+
 |  | +--+
 | ++-++ |
 | | 0 | |
 | ++-++ |
 +--+ |  |
      |  |
 ---+ |  |
    | |  |
   ++-++ |
   | 1 | |
   ++-++ |
    | +--+
    |

 
上の回路には「2-Lloop-DoubleX」と名付けた。ここで空前のDoubleXブーム。
(1素子にXが二つ繋がってるから「DoubleX」だ!)
あれーおかしいなー。と思い、みんなでいろんなDoubleXを作って、手計算をみんなでした。
 
そこで以下の回路が完成。

 ->-+ +--+
    | |  |
   ++-++ |
   | 0 | |
   ++-++ |
 -<-+ |  |
      |  |
 +--+ |  |
 |  | |  |
 | ++-++ |
 | | 1 | |
 | ++-++ |
 |  | +--+
 |  |
 |  | +--+
 | ++-++ |
 | | 2 | |
 | ++-++ |
 |  | +--+
 +--+

 
@さんがこれを「3-Infinity-DoubleX-0-1-2」と名付け。Infinityだとっ? やるねー(yarunee)。
と思っているさなか、ふと「もしかして、ランクなんて関係ないじゃ?」と思いつき、
ランク => IDに置き換えてシミュレータを動かすと全てのテストが通ってしまった。
そして、ようやく正しいkeyprefixを得ることができたのだった…。
 
そう、私のランク付けコード、そして作成したRubyのC拡張ライブラリは「rm -f」!!
南無三…。ここで夜の10時くらい。Bad end.
 
@さん、@さん、@さんで回路ジェネレータを作ってもらっていたので、
素子3、素子4と生成していく。ここで素子4のケースが「80万」くらいになってお茶を吹く。
誰かね。19素子で2億くらいって言った奴は(私)。
 
そうか、考えてみればシミュレータはそれほど早い必要はない。
keyprefixの先頭とシミュレータの1発目の値が違えば、その場ではじけるからだ。
OMG。回路ジェネレータが爆速である必要があったなんて!
 
そんなこんなで、素子5のケースが軽く億を突破しそうで、そんなにディスク容量ないよねーという話になり。回路の枝狩りを考えることに。
「外に出るXが繋がっている素子(A)の入力が、(A)のIDよりも大きな素子からである場合、この回路はkeyprefixを生まない」
と定義できたが、一部しかコーディングできず。

(2日目終了)
 

3日目

夕方6時頃から9時まで最後のあがき。
素子5の回路を生成しながら、シミュレータに通し、偶然合っているものがないか確かめた。
 
私は20:50に会社を後にして、ICFPC2010が終了。
 

蛇足

とりあえず、駄目な感じだったのですが、日記として残しておくことで来年の足しになったり、
駄目だったチームってこんな感じなんだへーと思ってもらえたりするといいなと思います。
 
あと、駄目だったからと言って楽しくないわけじゃない!という事だけは念を押しておこう。