2010-05 << 2010-06 >> 2010-07

2010-06-21 (月)

*ICFP Programming Contest 2010

http://icfpcontest.org/

終わりました．

無残な結果．気力とか色々足りなかった．そしてサーバが重すぎた．というか，真面目な解析プログラムより，自動submitプログラムの方が重要で，高得点の人はみんな使ってたんじゃないだろうか．簡単な車作ると一瞬で燃料がsubmitされてくるので．

問題は面白かったけど，サーバが重いのと，真面目にsubmitするインターフェイスをどうにかしてほしかった．自動的にやる前提だったのかもしれないですが．

以下ネタばれ注意


以下ネタばれ注意

だいたい，時系列順に説明します．

―0日目

開始時間より少し遅れて eldesh のところに行くが，無線LANつながらない…．とりあえず夕食でも食べることに．結局，22時頃に開始．まだ点を取っている人いないみたい．

回路

まずは，回路(燃料を生成する工場)の仕組みを解析します．何か意味ありそうなリストが問題に載っているので解析が簡単そう．

各ノードが扱うのは，0,1,2の３値論理．回路を動かしてみると，片方の出力が比較で，もう片方がNAND演算かなくらいは予想できる．実際には，差(L-R)と積(L*R-1)でしたが．

問題読んだ後，入出力ノードは何も演算をしないと勘違いしていたが，実際にやったら何かやっていることに気づいた．さらに，他のノードと違うことをやっていたらどうしようという疑心暗鬼に．

入出力を表すXを２つのゲートにまたがってかけることに気づくと小さい回路を手で作るのが楽になる．初日は気づかずに，少し苦労して回路を作っていた．

ノードの種類らしい数字が付いていたけど，最後まで何ができるのか分からなかった．(0以外を色々入れてみたけど，エラーになる)

この時点で，prefixの生成に成功している人が出てきた．少し焦るが寝る．

―ここで0日目終了

細かい回路を何パターンも試して，ノードの動作を調べる．

ノードの動作が分かると，問題に書かれている回路をローカルでシミュレートできて燃料の正しいprefixが得られる．

ただし，サーバ上では入力不明なので正しいプレフィックスを出力できない．

まず，入力をそのまま出力する回路を作ってサーバ上のストリームを調べる．

あとは，がんばって好きな回路を生成する．

Carの解析はeldeshとkmuroiに任せて，今後必要になりそうな回路モジュールと，生成プログラムや複数回路を接続するツール等を作る．

将来的に，無限長の任意のストリームを生成する必要が出てくると予測して，まずは効率悪いが何でもできる生成プログラムを作っていたが，そんな必要なくて，燃料とか有限長で短かった．結局，このとき作ったものはほとんど無駄だった．

というわけで，そのツールで生成した500行もあるprefix出力回路をsubmitして最初の点を得た．2030頃．

ぎりぎり24時間以内にここまできた．

その後は，ご飯食べたり，色々考えたり．

―ここで1日目終了

家に帰って寝る．

起きて洗濯したりアニメみたりして，夕方eldesh家に．

夕食は，寿司を食べたかったけど，品川で焼肉食べた．

kmuroiは帰った．

CarとFuelの解析が進んでいないようだったので，エラーメッセージ見ながら，簡単そうな車にsubmitしたら通った．他のも通りそうだけど，放置して寝る．

―ここで2日目終了

ストリーム

すべてのデータは3進数のストリームで扱われます．

朝起きて，ふとストリームの構造を調べ始める．Carのsubmitフォームで何度も試行して解析．今まで悩まされていたけど，真面目に調べると意外とあっけなく構造が見えてきた．

「22」というのが，その後の桁数を調節しています．

10進の0,1,2,3,4,5,6… は 0,1,220,2210,2211,2212,2222000…になります．

22の後の1桁はその後に続く桁数．2222の後の2桁も，その後に続く桁数．というわけで，22で桁数を調整しているのか．再帰的．

もうひとつ，数値の表現形式があって，

0,10,12,22000,22001,22002…

こちらは，桁数(これは上の規則で記述)＋数値という形になっていて，リスト形式のデータに使われています．

本当は綺麗規則があると思うし，なんとなく考えたけど，実用上は問題ないのでこれで．

で，まだ眠いので寝る．再び起きたのは14時くらい忘れないうちに色々確認．やっぱり合ってた．

最初のと同じ燃料で走る車があるみたいなので，eldeshがsubmitしてくれていた．ついでに，今まで1000行くらいあった回路を35行くらいで作るプログラムを作成．最初作ったものより，こっちの方がとても単純．

Carのストリーム内の数値やリストやフラグの構造を把握したのが1740頃．

時間がない．

残ったフラグがmain camberを表すと気付いてCarの解析が終わったのが1845頃．

Fuelもそっくりだなと思って，数回試して意味が分かったのが，1855頃．

とりあえず，手作業で車と燃料を作ってみることに．2000頃？

最初の車をsubmit．2031．

そしてサーバが重い．

どうせ30分しかないし，自動化は難しそうだったので，似たような車を数台作ることに．そして，簡単な車だと，submitしてもすぐに他の人が燃料を供給し始めるので，点が上がらない．

というわけで，3台作った．

―ここで3日目終了

なんとか，全容を把握するところまでたどり着いたけど，得点に反映させる間も無く終わってしまった．

２日目がネックになっていた気がしないでもない．真面目にストリームを解析するしかなかったが，最初やりたくなかった．

車

燃焼室の数，upper pipeの情報, main chamberフラグ，lower pipeの情報…

例：

220100220101022011111022111010011

  • 220 燃焼室の数(2)
    • 1 upper pipeにつながるタンクリスト長(1)
      • 0 tunk0
    • 0 main chamber flag(?) false
    • 220 lower pipeにつながるタンクリスト長(2)
      • 10 tunk1
      • 10 tunk1
    • 220 tunk list len:2
      • 11 tunk2
      • 11 tunk2
    • 10 flag true
    • 2211 tunk list len:4
      • 10 tunk1
      • 10 tunk1
      • 0 tunk0
      • 11 tunk2

燃料

タンク１，成分１の燃料は，エラーメッセージ見れば簡単に作れる．これをサブミットし続けるだけで，そこそこ点が取れたかもしれない．

最初の数字が，タンクの数，その後に成分数．タンクはc(i,k)が入っている二次元のリストが，タンク数分だけある．

感想

問題はとても面白かった．

個人的に，いまいちだった点は

  • ビジュアライザとかツール作るの好きだけど，必要無かった
  • 本格的にコードを書くまでが長すぎる(全容を把握するまでの手順が多い…)
  • 大量にsubmitしないと高得点取れない(submitまで自動化する問題だったのかも？)
  • サーバが重いのでローカルでやることを増やして欲しかった
2010-05 << 2010-06 >> 2010-07