ICFP Archive

Marco氏のblogに結果が掲載されている。

Place 	 Score 	Survival chance 	Team name
1 	178246 	90.22% 	Team Smartass
2 	224623 	84.92% 	United Coding Team
3 	293898 	75.59% 	Celestial Dire Badger
4 	321617 	71.52% 	ryba
5 	358246 	65.98% 	PurelyFunctionalInfrastructure
6 	453744 	51.32% 	jabber-ru
7 	498781 	44.66% 	Begot
8 	514121 	42.47% 	Basically Awesome
9 	543163 	38.45% 	SwtPl
10 	608964 	30.07% 	shinh
11 	682894 	22.07% 	SzM
12 	819614 	11.34% 	kuma-
13 	862213 	8.99% 	Unknown?
14 	865556 	8.83% 	voyo
15 	872788 	8.47% 	kokorush

PurelyFunctionalInfrastructureは5位で負けますた。むきぃぃ。

糸色望した！世界の壁は高すぎる！
おき神によって6.8秒で終わるdna2rna(C++)が作れる事が示された。速すぎ。「でも本番はHaskellでしょう」という有り難いお言葉を頂きました。

終了。「Purely Functional Infrastuructre」というチーム名で出場しました。tanakh, nushio, hillbig, oxy, nvaca, nuc, christopher, kzk。PFIメンバーのチームです。869チーム中Top15には入れました。SmartassやAwesome辺りに勝ってるとうれしいなぁ。
以下は僕の作業内容。ネタバレあり。問題概要等は説明してないので、kinaba先生のエントリを先に読まれた方が良いと思います。

1日目

rna評価器をごりごり書いてた。言語は迷わずC++を選択。色の作り方を工夫しないと遅いのにえぬさんが気づいてくれたのと、tryfill命令が再帰だとStackOverFlowする(画像は600px*600px)のをBFSに変えたぐらいで、夜1時ぐらいにはたなかさんのdna2rnaと組み合わせてCheck OK画像が出てた 。終わってからStackOverFlowはすぐ気づかないとかｵﾜﾃﾙﾖ-とにゃーさんに言われた・・・確かにｵﾜﾃﾙorz。

その後は何をしたらいいか分からんので、とりあえず絵を描いてみる事に。endo.dnaを完全にスルーしてprefixだけで絵が書けるツールをoxyさんが作ってくれたので、それを使って空だけ書いてみた。初得点ゲット(笑) おかだいさんも似た色の長方形をぺたぺた貼り付けて点数を上げるプログラムを書いてたけど、移動やsetColorのコストが大きくて結局あまり上手く行かなかった。また、えぬさんがSDLでrnaの描画過程を見れるようなツールを書いてくれていた。

その間たなかさんとぬっしーがひたすらdna2rnaのトレースを眺めて遠藤の動作を解析。辛そう。この辺りでスコアボードから16位のチームがたった28byteのprefixでとんでもない点を取っている事が発覚する。これを元にたなかさんが同じ効果を持つ27byteのprefixを自力で編み出してsubmit。画像が夜から昼になった！

煮詰まったのでブログなどを見ていると、うちのdna2rnaが非常に高速である事がwebからの情報で分かってきた。Haskellすげー。FingerTreeとか聞いた事無かった。ext/ropeに逃げずに迷わずHaskellを使ったたなかさんがかっこよかった。ropeはバグバグだったらしい。怖い怖い。

2日目

「あなたは何も(ry」を見て作業開始。

たなかさんとぬっしーがあまりに辛そうだったけど、僕とえぬさんは別件でごにょごにょ。終わった頃にはなんかmain関数みたいなの見つけた！とか横で騒いでいらっしゃった。えぇぇぇ。これ計算してるんだ・・・。てか関数とか呼べるんだ・・・。で、気づいたらDNA書き換え技術を一部手に入れたたなかさんが山を出したり、箱の色を変えたり。そして遠藤内の関数をひたすら解析していらっしゃった。この時点で生存率5 - 6%はいってたと思う。

3日目

そういえば皆がsubmitしてる28byteってなんだろうと思い、endo.dnaを実行した時に最初に描画されるものをprefixとして入れてみるとなにやら変な画面が出てきた。あぁ、ここに28byteの答えが書いてあったのかと遅まきながら気づく。

ページ1337とか書いてあるけど、なんだろこれーと思って、3章の内容を教えてもらいながら手元色々と試していたら、”Steganography”というページと”Fuun Field Repair Guide”というものを発見！そこにたなかさんが一番欲しがっていた関数&変数アドレス表が載ってた。

でも1 out of 14 pagesとか書いてある。うーん。しばらく悩んでるとAAA_geneTablePageNrとかいう文字が目に入った。これ、ページ数なんじゃね？と思って、この番地の値を書き換えて実行してみると2 - 14ページが出現。この辺で初めてチームに役立てた気がした。朝の５時ぐらいだった気がする。

ちょっと仮眠してたら、たなかさんがさっきの情報を元にDisassemblerを作成していた。なんでそんなものが作れるのか動作原理は今も分からないけれど、遠藤解析技術がここに確立された。たなかさん凄すぎる。

その後はプログラム内の関数呼び出しを書き換えたり、変数を書き換えたりする事で絵の正解率をひたすら上げていった。あぁこれが主催者の意図なんだとこの辺で気づくと共に、スコアボードを見る限り他のチームはこの事にほとんど気づいてないというのが実感できた。

えぬさんとぬっしーがプログラムを書き換えて風車を回すのに成功したときは、ちょっぴり感動した。プログラム２００箇所ぐらい書き換えてるし。僕はあひるを出してみた。あひるは実はポリゴンデータの最後のデータが一個壊れていて、2pxずれている。だから単純にあひるを出すと、その後の描画が全部2px
ずれてしまう。これにパッチを当てて、直した。

その後はひたすら絵を書き換えて終了。ここに結果がありましたが、なんかまずい?らしいので消去。

それにしても、shinhさんがこのアプローチで30%の生存率を叩き出したのは凄すぎ。出題者の意図を汲まずに突っ走ってるのがカコヨスギ ☆☆☆☆。まさかあのノイズをクリアするとは…。

UnknownのチームメイトのにゃーさんとうっしゅさんチームもTop15入り。C++でdna2rnaをropeもつかわずに書いたというから凄すぎる・・・。

さて、７月の残り日数よりも数の多い学科レポートを片付けますかね・・・。鬱。

P.S
ちょっとUnited Coding Teamの構成員がやばい・・・。このブログ書いてる人はインターンでGoogleCodeSearch作った人みたいですね。僕と同い年みたい。まぁ僕はインターンは落ち(ry こういう人たちと戦えるのが楽しすぎるわー。しかしこんだけの人材19人のチームって、ちょっと待てよと(笑)

今日の日本時間午後7時からICFP Contest 2007が始まります。
コンテストページ
カウントダウンページ
ルールは、72時間で与えられた問題を解くだけ。それだけ。言語は問われません。むしろ勝つことで自分の一番好きな言語の優位性を示す事ができます。これに参加したことのない人はプログラマとは呼べません(僕の中でw)。今年はPFIで出ますよー。
参考:
去年の様子 by kinaba先生