moratorium

Firmware, Utilityがアップデートされていた。

これでたまに起こるBlue Screenが直るといいけど。USb Modemの奴はバグバグらしいね。頑張れイーモバイルの中の人。

7月の課題ラッシュ終了。

糸色望した！世界の壁は高すぎる！

おき神によって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先生

x60sを英語キーボードに換装 for ICPC。

日本語切り替えすらままならん。

記号に特化したタイピング練習ソフト/サイトって無いですかねぇ。PKU? (違

# 台風に続いて地震って・・・

今日は変なメンバーで飲み。超楽しかった。またやります！ZeroCopyはやっぱり速いよね、っていう。

この３週間は色々な人と会って食って飲みまくった。人脈の輪が広がりまくりで楽しい。次の２週間は試行錯誤してコード書いたりアイデア練ったりする。

学校の方は演習３が終わった。今学期は授業に惹かれなくて全然出てないけど演習３は楽しかった。来週はテストがあるみたいですが、徹夜で乗り切る。

nuさんがHandAsmOptimizationでCPU実験の記録を次々更新している(現在: 16.493s)。id:MaD氏とkoiken氏(3年生)は既にUSBとSRAMを動かして、DRAMを動かしにかかっているらしい。なんだ、こいつら、凄すぎるー。

今更ですが、PaperVision3D(重いので注意)というActionScript3.0の3Dライブラリを使ってみました。

ICPC(International Collegiate Programming Contest)国内予選にid:ushiodaとid:nyaasanと出ました。チーム名はそれぞれの頭文字u, n, k.oを取って、「Unknown」です。

結果としてなんと国内一位を取る事が出来ました。もう感激・・・。というか僕以外の二人が凄すぎ・・・。なんというか、もうこいつら天才かという感じです。

この調子でアジア予選も頑張りたいと思います。

追記: 2007/07/09
当日の様子はnyaasanのエントリ参照。

先週はPFIニコニコマーチ, IPAX, Esperに参加しました。ここ一年ぐらいイベントにあまり参加していなかったので、色々新しい人に会えて楽しかったです。

ニコニコマーチでは田中さんと、周りのPFI面々の爆発力が凄まじかった。6月は何コミット有ったんだろう・・・。

IPAXでは興味を持ってくれる人が多くて良い感じでした。結構技術的な事も質問されて、ちょっと驚き。おかだいさんは、居ないのにも関わらず人気でした。清水さんにも久々に会えた。太ったねって人生で初めて言われたorz。

Esperでは、ついにおくじさんにお会いする事が出来たので大満足。首藤さんとも今まで話した事が無かったのですが、色々境遇が近くて共感する所が多かったり。五十嵐先生のプレゼンは授業と一緒だった(笑)しかし何度見ても見入ってしまうから凄い・・・。

そんな感じで色々刺激が有った一週間でした。