ICFP2007ようやく少し進んだ

2013-04-26
年末年始に挑戦していたICFP2007は、7Mとかある文字列の切り貼りを大量にする必要があって、最初C++で`std::string`を使って書いたんだけど1枚の絵を出すのに9時間ほどかかっていた。部分文字列を取り出したり文字列の連結を高速に行うデータ形式として[Rope](http://www.kmonos.net/wlog/39.php#_1841040529)というものがあるらしいんだけど、導入方法がよくわからなくて、じゃあっつって自前で実装しようとしたがうまい実装方法がわからなくてそれほど速くならなかった。[HaskellでData.Sequence](http://d.hatena.ne.jp/katona/20070802/p3)というのを使えば速いというのを見たので、Haskellに書き換えてたんだけどどこかにバグがあるのかうまく動かず放置していた。テストコードも書いて試した限りではうまく動いているふうなんだけど…。ふと気が向いて久しぶりにソースを見てみると、DNAからテンプレートの取り出しの部分でDNAを消費してない箇所があってバグっていた。ので修正するとようやく動くようになった。Haskellで[Data.Sequence](http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html)を使った版だと、DNAからRNAへの変換が2分ほどで終わるようになった。

prefixを与えずに描画させた時に、rnaの最初の部分でIIPIFFCPICFPPICIICCIICIPPPFIICというヒントみたいな基が表示されるので、それをprefixとして与えてみると、FUUN FIELD REPAIR GUIDEというのが表示された:

fuun_field_repair_guild

テキスト:

FUUN FIELD REPAIR GUIDE FUUNTECH INC. DNA RESEARCH GROUP 1 FUUNTECH WAY RIGEL IV STARDATE 90.7.65.44 IF YOU HAV MANAGED TO ACCESS THIS MESSAGE, IT MEANS THAT YOU HAVE FOUND A CRASH-LANDED FUUN AND ARE ATTEMPTING TO REPAIR IT. THANK YOU FOR YOUR EFFORT IN SAVING A FUUN. ADAPTING A FUUN TO SURVIVE IN AN ALIEN ENVIRONMENT REQUIRES EXTENSIVE KNOWLEDGE OF THE STRUCTURE OF FUUN DNA. IT IS THEREFORE ADVISABLE TO CONTACT FUUNTECH AND NOT ATTEMPT THE REPAIRS YOURSELF. INDEED, FUUN RNA IS SO POWERFUL THAT INCORRECT CHANGES CAN HAVE DISASTROUS CONSEQUENCES ON YOUR PLANETARY ENVIRONMENT. FOR THE EVENTUALITY THAT YOU ARE UNABLE TO CONTACT FUUNTECH. HOWEVER, WE HAVE EMBEDDED THE FUUN FIELD REPAIR GUIDE. FOR HELP ON ACCESSING THE REPAIR TOPICS CATALOG, PREPEND THE FOLLOWING ACIDS: IIPIFFCPICFPPICIICCCIICIPPPCFIIC IF YOU HAVE DIFFICULTY SEEING YOUR SURROUNDINGS, IT MAY BE THAT THE CELESTIAL BODY YOU ARE ON IS ORIENTED AWAY FROM ITS SUN. TO ACTIVATE POWERFUL GEENS THAT ROTATE IT TOWARDS THE NEAREST BODY SUSTAININING NUCLEAR FUSION, PREPEND THE FOLLOWING ACIDS: IIPIFFCPICPCIICICIICIPPPPIIC DON'T PANIC

2つのprefixが紹介されている。

下のを見てみると、

noon

昼になった!空が明るくなって地面も照らされて、これだけでグッとそれっぽくなった!

上のは修理カタログのページで、見てみると

repair_guide_navigation

カタログを見たい場合の説明が書いてあるんだけど、英語がよくわからん…。カタログのページを2進数で下位から上位の順に、0と1をICにエンコードして置き換えて長さは変えるな、ということなんだけど、どこにページ数を埋め込めばいいのかわからん…。

ググったりして調べたところようやくわかった。このページを見るために与えたprefix IIPIFFCPICFPPICIICCCIICIPPPCFIIC

パターン:

意味
IIP (
IFF CPICFPPIC ?”IFPCFFP”
IIC )
C I
C I
IIC 終わり

テンプレート:

意味
IP P P {0,0}
C I
F C
IIC 終わり

となっていて、matchreplaceでパターンの「(?"IFPCFFP")」でDNAの先頭からIFPCFFPという並びまでを環境0にセット、「I」「I」を消費して終わり。次にreplaceでテンプレートで、「{0,0}」で環境0をそのまま出力、「I」「C」を出力して終わり、という処理になる。これで元のDNAの、IFPCFFPに続くIIICに置き換えたことになる。実際に元のDNAを見てみると、IFPCFFPに続いて24個のIが並び、Pで数値の終わりを示している。ここがページ数を表しているものと思われる。

ということで、カタログの索引ページという1337ページを見るには、1337 = 0x539 = 0b10100111001 をエンコードして置き換えるコード、IIPIFFCPICFPPICIICCCCCCCCCCCCIICIPPPFCCFFFCCFCFIICというprefixをつけて変換してみる:

catalog_page_index

おおー、違うページが表示された!「Catalog seems to be damaged」と表示されてるのが気になるが…。

とりあえずここまで。