Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2007年07月25日(水) The 10th ICFP Programming Contest

[]ICFP Programming Contest 2007 ICFP Programming Contest 2007を含むブックマーク 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 <rope> とかしても使えなかったのであっさり断念。

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つを引数にして座標セットらしき関数を読んでいることもわかった。これでオブジェクトを任意の位置に書くことができるだろう。

18:00ごろ

その成果をもちいて、UFOを消した。

λx.x も消した。

λの吹き出しも消した。

三日目

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さんの方法には度肝を抜かれました。

さて、今年はもう終わってしまいましたが、願わくば、また来年も出られませんことを。

2007年07月10日(火) ICPC国内予選2007

[]ICPC国内予選2007 ICPC国内予選2007を含むブックマーク ICPC国内予選2007のブックマークコメント

国内予選

去る7月6日に国内予選があったのですが、ありがたいことに今年もMakegumiのコーチをやらせていただいておりました。

コーチとして戦いを見守るのももう公式戦だけでももう4度目になりますので、気分的には慣れたものですが、やはりもどかしいものです。まあ、もう私なんか鈍りきってしまって、何も言えることはないのですが。

結果は http://www.logos.ic.i.u-tokyo.ac.jp/~chik/icpc2007/jp/domestic/result.html こちらから見れるとおり、Makegumiは2位でした。1位のUnknownの皆さんはおめでとうございました。去年のことを考えると若干残念ではありますが、別にどこが勝ってもおかしくはない状況だったし、時間差勝負で、しかもここまで競っているとなると、改めて勝負は水物であるなあと思う次第であります。

問題は今年は易化したと思います。きっと今年は去年の1.5倍ほどに予選突破チームを増やすことになったからなのだとは思うのですが、ちょっとこれはバランスが悪かったと思います。それに加えて作業色が強くなったのも個人的にはあまり面白くない。どっちかというとMakegumiは難しい問題をぽこっと通すイメージがあるので、ちょっとその辺でもつらかったと思います。


考察

ときに、私も裏でコーチとして観戦・応援しながら問題をぼちぼち解いていたので、この辺で問題の考察でもしてみようと思います。問題は現時点では http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2007/common/guest_top_en.php ここから見られるようですね。

問題A

ついにリハーサルレベルまで落ちた問題A。なめながら和と最大、最小値を調べるのがお手ごろでリーズナブルだろうけど、ソートしてもとくにペナルティーはなさそうであるなあ。

問題B

やけにややこしいけど、PCの番号が何も意味を持たないことに気づけば、問題は意外なほど単純になる。時刻も昇順に入ってくるし。

問題C

問題の記述がかなりわかりにくい。Inputのところに問題の続きを書くのはどうかと。ピースカットが行われると、元のピースはなくなってまったく新しいピースが2つ出現するという理解でよいのだろうか。各カットはおそらくO(logn)でできるのだけど、問題のサイズが小さいので、O(n)でも、O(nlogn)でもなんでもよさそうな感じ。

問題D

どう見ても最短路ですね。

問題E

は、おいといて。

問題F

多分、国語の問題。私は30分ぐらい問題を読んだ挙句に、結局問題を正しく把握できずに時間内にバグが取れなかったのでありました。要は書いてあるとおりに実装しろということなのですが。ちなみに、とてもHaskell向きの問題なのでHaskellでも解いてみました。よろしければ後ろのソースをご参照ください。

問題E

おそらく一番難しい問題でしょうね。方針によってコーディングの難易度は大きく変動すると思われるのでいろいろ考えてみましたが、いまいち書きたくなるほどシンプルな方法が思いつかないので保留しています。1.棒が何度回転できるかを二分探索で求めて、それを繰り返す。つまり、ある扇形が与えられたときに、それが多角形に包含されるかが求められればそれだけで解けるのですが、これが微妙に簡単ではない。どうしたものか。2.支点から回転させて棒が突っかかる可能性のある角度をすべて求めて、そのminだけ棒を回転させ続ける。min=0なら終了。これは図形の内部と外部を判別するスマートな方法が思いつかない。3.精度が結構粗くてもよいので、長さ*角度<10^-3になるような角度ずつ棒を少しずつ回転させていく。長さは500以下だから、10^-6ぐらいずつで回転させると、トータルで最大20πほど回転させればよいので、気長に待てば計算が終わるような気がする。でもまあなんというか、誤差が累積するような気がするなあ…。

とか、考えているうちに気力がなえてしまった…。

後記

やはり現役はうらやましいですね。私もあと2歳若ければ。終わったあと今年も白木屋で祝勝会をしていました。PFI密度が濃すぎたといわざるを得ない。なんでコーチの私が飲まされるの。Unknownの三人の表情は晴れやかであった。やはり勝者はそうでなくては。Makegumiは次は名前のとおりにならぬようにがんばってください。もう今年は最後なので、本当に世界大会舞台を経験してもらいたいと思っていますよ。

おまけ

1分おきにスコアボードを取得してみたので、よろしければどうぞ。

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/guest_standings_en.php.zip

ソース

一部Haskellソースつき。

Dはグラフライブラリを使ってみたけど、あんまりすっきりはしなかった。なんでNodeがIxじゃなくてIntなのだろう?Shortest Passがなかったときにパターンマッチで落ちるのもどうかと。Fはかなりすっきり。EqOrd関係がまったくないのはご愛嬌。map (show . norm . read) と書けるのは相当気持ちいい。

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/a2.cpp

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/b2.cpp

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/c2.cpp

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/d2.cpp

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/f2.cpp

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/d2.hs

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/f2.hs