ICFP Programming Contest 2007
終わったあとの脱力感で文章を書く気力をチャージするのに幾分時間がかかってしまいましたが。
-
-
-
- -
-
-
ICFP Programming Contestに今年も参加しました。今年はPFIからということで、
http://kzk9.net/blog/2007/07/icfp_2007.html
こちらの太田さんのページに書いてあるようなメンバーで参加していました。チーム名はPurelyFunctionalInfrastuructre です。
http://www.icfpcontest.org/submits/scoreboard
ここにあるとおりまだ結果はわかりませんが、とりあえず15位までには入れました。成果物は
http://fxp.infoseek.ne.jp/icfp2007/materials.zip
に置いてあります。
BEFORE
AFTER!
問題については、
http://www.icfpcontest.org/
こちらのTaskのところから参照できます。
とてもおおざっぱに要約すると、endo.dnaというバイナリと、それを実行するための方法が与えられるので、そのバイナリにprefixをつけてtarget.pngにできるだけ近い画像を生成しなさい、というもの。
-
-
-
- -
-
-
いつもどおり、私の視点からの参加記を書こうと思います。今回は三日間オフィスに泊り込みだったので、最後のほう頭が痒くて仕方がなかったよ。
一日目
18:00
開始一時間前。皆でなか卯に行って英気を養う。スコアボードなるものがあったので、今年もAIじゃないっぽいなあとか思っていたり。
19:00
ついに開始。私が英語を読むとほかの人の10倍ぐらい時間がかかるので、しばしほうける。DNAとかいう言葉が耳に入る。塩基がICFPなのが面白い。
19:30ごろ
DNAを実行するには擬似コードをそのまま実装すればいいのかと問うたら、そうだということなので、何もわからないままDNA2RNAを書き始める。DNAファイルが7MBほどあったので、去年のことが頭をよぎって言語の選択に暫し迷うも、別に遅かったらCで書き直せばいいよね、二回目だとそもそもすぐ書けるだろうし。ということで、いつもどおりHaskellで書くことにする。DNAのデータ構造は、このときは深く考えてなかったけど、なんだかマニュアルに載っている演算子の記号と、Data.Sequenceの記号が似ていたので、これを使うといいのかなと思ってData.Sequenceを用いた。Data.SequenceというのはFinger TreeのHaskellにおける実装で、結果的にこれを選んだのは大正解なのであったが、このときはまだそのことに気づいていない。並行してRNA2PPMの開発がスタート。これは足を引っ張るわけにはいかない。
21:00ごろ
ひとまず完成してデバッグが終わる。しかし遅くてどうにも我慢できなかったのでC++でも実装してみることにする。RNA2PPMもできつつあったのでかなりあせる。このときは、DNAの操作は前から削除して前に突っ込むだけだと思っていたので、DNAのデータ構造としてstackを採用する。
23:00ごろ
C++版が完成。なんとHaskell版よりもはるかに遅い。マニュアルに、DNAの連結が線形時間より高速にできないとつらいと書いてあったらしい。よく考えると、DNAは任意の場所から任意の長さ切り出せるのだった。そんなのstackじゃ無理ではないか。ropeを使うとよいということであったが、#include
24:00ごろ
自分でropeもどきを実装した。しかし、あまりにも適当な実装だったので、それでも十分に遅い。これだったらちゃんとまともに実装されててオーダーが保障されてるHaskellのFinger Treeのほうがいいやん、ということでHaskellの実装のほうを改良することにする。
1:00ごろ
実装の手抜きでところどころStringに変換して操作していた部分をすべてSequenceで処理するように直して再実行。速い速い。文字列サーチをブルートフォースな上に毎回Sequenceを切り出して==で比較という超馬鹿な実装にしていたところだけが心残りであったが、大体毎秒10000イテレーションできるようになったのでこれでよしとする。というわけで、ここまでかかってようやくDNA2RNAが完成。ちょっと前ぐらいにRNA2PPMも完成した模様。
3:00ごろ
いろいろバグなんだかがあって、このあたりでようやくsource.pngと同じ画像が生成されたような気がする。
しばし感慨にふけるとともに、今年は敷居が高いなあと思う。効率的なデータ構造が必要って。門前払いをくらう人も多そうであるなあ。
アドバイスに書いてあるプリフィックスを打ち込むとシステムチェックみたいなページが出てきた。
これは、実装があっているということでよいのだろうか。
眠くなってきたので、寝る。
9:00ごろ
起床。状況は特に変わっておらず。何も出せないとつらいので、とりあえず青空を書くプログラムがサブミットされた模様。はじめて得点が取れた。アドバイスのプリフィックスは、DNA中のどこか1バイトを書き換えるという命令だったので、フラグでの分岐があるとにらんでDNAの解析に入る。まずは、DNA2RNAを実装したけど、その動作原理がまだよくわかっていなかったので、トレースログを見ながらその動作を完全に掌握できるようになるまで学習する。
14:00ごろ
スコアボードの21位が長さ28ですごい高得点を出していたので、全体を昼にするフラグの存在を確信する。そこまで提示されたらもう解けなきゃおかしいでしょ、ということで、ひたすら解析。分岐を無理やりいじると、
空の色だけ変わったものが出てきた。
これは同じフラグでいくつも分岐しているな、とにらんで、パターンが条件分岐の体をなしているとき、その分岐が参照しているメモリの前後を出してみることにして、そこのパターンによって置換することにした。そうすると、めでたく
画面全体が昼になった。とてもうれしかった。
このとき、私が見つけたプリフィックスの長さは27で、スコアは28の人と1違う。ほかの人たちがなぜ28なのか大変悩みながらもそんなことを気にしていても仕方がないので、解析を継続する。
並行してこのあたりで、RNAを逐次的に描画してどのあたりのDNAでどの描画命令が発行されたか追跡できるビジュアライザの開発が進んでいたもよう。
16:00ごろ
いろいろいじっていると、
よくわからないのが出た。
19:00
いろいろいじったりするも、結局ほかに有効なフラグを見つけるまもなく、長さ27のやつでLightning Divisionが終了。24時間というのはあまりにも早すぎる。
二日目
20:00ごろ
昼ごはんを食べ過ぎたからか、眠さを極めたので、眠りに落ちる。
2:00ごろ
目が覚める。起きたら誰もいなかった。
眠っている間に、
マニュアルページのようなものが表示されるフラグ、
画面全体が青白透明になるフラグ、
アヒルが出るフラグ、
ドイツ語みたいなのが出るフラグ、
などが解明されていた。
アヒルは得点に結びつきそうだったので、prefix化してSubmitしてみるも、スコアがぜんぜんあがらない。よく見るとアヒルを表示したときはアヒル以降に描画したものが2ドット右にずれている。どうしたものかよくわからない。
5:00ごろ
右下のダンボールの色を正しくすると相当得点が入りそうだったので、修正すべくがんばる。DNAの実行を追っかけるのが、パターンとテンプレートだけではつらい。DNAは前に伸びるので、絶対的な位置がわからないのがあまりにもつらすぎたのだが、よく考えると、DNAの各要素に対して、もともとのDNA上での位置を記録しておけば、ある命令がもともとどこにあったかわかるし、命令に参照されるメモリがどこにあったものなのかわかる。そんなわけで、実行トレースを出力するプログラムを改造して、絶対アドレスを表示できるようにした。
すべてのもともとのDNA中の値に依存する（BOOLの）条件分岐が洗い出された。全部で9個ほど。全体がドイツになるフラグ、青白透明になるフラグ、アヒルが出るフラグ、など、昨晩見つかっていたフラグのアドレスが判明した形だ。ここでわかったことは、ダンボールの色は、条件分岐で分岐しないということ。つまり、フラグを追っていても色は変えられない。ということは、色を作っている部分の命令自体を変えるしかないなと思って、RGB値を調べると、sourceとtargetではRGBのうち2つを入れ替えたものになっている。しめた、これは紫を黄色に変えるだけでいい！
7:00ごろ
そこまでわかればあとはすぐで、トレースとビジュアライザでダンボールの色を作っている部分を突き止めて、色のコードを強制的に書き換えて、完了。サブミット。生存率が3%にUP。相当うれしい。でも、オフィスに誰もいなかったから、喜びを分かち合う人がいなくてさびしかった。
あんまり進んでいるようには見えないけど、この時点で日程の半分を消耗してしまった。もうあせるあせる。しかし、スコアボードを見ても、まだ21位に長さ28のしか見えない。いったいどうなっているのだろうか。知っているチームもずっと沈んだままとかで、もう投げちゃったのかなとか思ったり思わなかったり。
8:00ごろ
青白フラグを立てたとき、山がうっすらと書かれているのに気づいたので、これはもしや本当は山を書くというフラグで、副作用として青白くなってしまうのではないのだろうか、と思って、このあたりでオフィスに来たぬっしーと一緒に調査を開始する。トレースを眺めていると、山を描画した後に、バケツをクリアする命令が一切ないことが発覚。山を描画する命令を眺めていると、山を描画する前に、DNA全体をあるパターンでなめてすべて置換している部分を発見。そのパターンをマニュアルで調べると、バケツのクリアであることが判明。要するに山を描画する部分は、山を描画する前にいらないことをやってくれているということがわかった。わかったらこれまた後は簡単で、バケツをクリアする命令をバケツをクリアする命令に置換する命令に置換して、コードを無害化。見事山が表示された。
まったく意味のない"OCaml"も発見される。
巨大アヒルも見つかる。
なんだかDNAの列が最初に一瞬書かれることがビジュアライザによって見つかるが、カレイにスルー。
14:00ごろ
ビジュアライザとトレースログを見ていると、なんとこのDNAは関数呼び出しをしているっぽいことがわかった。コードを取り出して、それを先頭にくっつけて実行している。それならばコードの構造がもっとよくわかるかもしれないぞ、と、ここからコードをひたすら追っていく作業を開始。ビジュアライザが役に立つこと役に立つこと。main関数らしきものとその全貌が、多大な労力の末についに解明される。やはりオブジェクトを描画するという関数が各個あったようだ。さらに興味深いことに、描画を行う前に整数2つを引数にして座標セットらしき関数を読んでいることもわかった。これでオブジェクトを任意の位置に書くことができるだろう。
三日目
19:00ごろ
mainが解析されたといえ、すでにあるものをないことにするのは簡単だけど、ないものを呼ぶのは関数の先頭のアドレスがわからないからとても難しい。ちょっと手詰まり感あふれる状態であった。残り一日しかない。
西川さんが、最初に一瞬現れる文字をプリフィックスにして実行すればいいのではないかということで、それを実行すると、
こんなものが出てきてしまった。三日目にして。ようやく長さ28の解のなぞが解ける。なんということか、これが正道であったのか。私はすっかり邪道を極めてしまっていたようだ。しかし、ここまできたらもう引っ込みがつかないので、私はDNA解析を引き続き行い続けることにした。ほかの人は正当な道の検証に入る。
20:00
こんなものが出てきた。
昼間に星を出すパッチ。ほかにも雷が出たり雨が降ったりするものを見つけたり。意味のないものばかり出てくる。
20:00
DNA実行に関する重要な文書が発掘される。グリーンゾーンとかいう名前は知らなかったけど、そういう仕組みで実行されていることなど、今までの解析でわかっていましたから。出てくるの遅すぎだ…。
23:00ごろ
グローバル関数・変数テーブルが発掘される。これ、これだよ、欲しかったもの。14ページ中1ページ目と書いてあるが、2ページ目以降がなかなか見つからない。
2:00ごろ
AAA_geneTablePageNrにページ番号を突っ込んで実行することにより、ついに2ページ目以降が発見された。これで大幅に作業が効率化される。
5:00ごろ
ふとした思い付きで、逆アセンブラが完成する。その時間15分。なんでいままで作ろうと思わなかったのか。これにより以降の作業効率が飛躍的に上昇。
関数テーブルを元に、関数の挿げ替えに成功。
なんか見てる。
ついに遠藤カウ出現。しかし、なんかおかしいぞ。
sunとかcloudとかsunflowerとかcaravanとか、いかにもな関数を呼び出そうとするも、どうもこれらの関数は破損しているらしく、うまく動いてくれない。ほとんどの関数にトラップが仕込まれている。これは大変だ。
7:00ごろ
endoさんはふくわらいしないといけないんだなと理解する。とりあえず後回し。
あと12時間。ICPC2回分強か。もはやこれがとても短く感じる。
9:00ごろ
アヒルを描画すると画面がずれる原因は、ポリゴンデータの不正であるとあたりをつけて、その修復作業を太田さんに託す。程なく修正完了。
12:00ごろ
エラーチェック機能つき関数テーブルが発見される。
13:00ごろ
花を直した。
14:00ごろ
キャラバンの本体は破損していなかったので、とりあえず配置してみた。
順調に点が伸びてゆく。
残り時間が少なくなってきたので、残りの作業を各人に割り当てる。私は雲と太陽を調査することにした。
16:00ごろ
西川さんぬっしーチームが風車を回す。得点が超大幅にUP。風車の描画は（角度,長さ)のリストでポリゴンデータが与えられるので、角度をすべて+5すればよいとのこと。
雲と太陽、さっぱりわからんよ。雲はduolcという関数があやしいけど、太陽はどうやって破損しているコード修正したらいいのか見当もつかないよ。あんまり進まないので、ほかの事をすることにした。
18:00ごろ
ふくわらい完成。ぶちの表現が芸術的過ぎる…。
草むしり完了。
18:30ごろ
ああ、もう時間がない。やることはまだまだあるのに。
ひよこ移動、くじら移動、おかだいさんの雲パッチをマージ。
などなどなど。
19:00
あわただしく時間がすぎる中、ついに、コンテスト終了。お疲れ様でした。
最終結果はスコアがわかるような表現はまずいとのことなので、控えておきます。
-
-
-
- -
-
-
最後のほう40時間ほどはノンストップで作業していたので、すがすがしい達成感をあじわうことができました。しかし、もうちょっといろいろと簡単にできることはのこっていたので、そこが少し心残りです。たとえば、下に書いてあるMorph Endo!はEndo has moぐらいまでは簡単に変えることができたし、川の魚は表示しなかったほうがたぶん点がよかったし、牛の尻尾はポリゴンデータを引っこ抜いてこればたぶん表示できてた。雲は、duolcという関数の中身をreverseしたらcloudのなかみとほとんど一致して、cloudは命令が壊れているのだけど、duolcは壊れてなくて、だからたぶんこれはduolcをちょっといじれば雲がでるようになるんだろうなあとか思ったりして、まだまだやり残したことは多いです。ちなみに、謎解きはまったくやっていません。なんだか、ブログとかを見て回っても、なぞが解けたからといってスコアにつながっているわけではないようですし、DNAに埋め込まれていたというMP3とかは釣りだったみたいだしで、結局のところ、主催者に遊ばれるなかれということです。今回の問題は、なぞを解け、というものではなくて、指定された画像を出力せよとのことなので、無理やりにでもバイナリをいじり始めたうちの方針はある意味で正しかったといえるでしょう。逆に、最初に自力である程度解析しておいたおかげで、関数テーブルの使い方とか、実行の仕組みとか、すんなり理解することもできました。
今年の問題は去年と似ているようで、いろいろとやりようがあるという点において、今年のほうが大分懐が深い問題だったと思うし、面白かったと思います。とりあえずshinhさんの方法には度肝を抜かれました。
さて、今年はもう終わってしまいましたが、願わくば、また来年も出られませんことを。
