ICFP2007 (4) 修理ガイド(2)

ICFP2007 (3) 修理ガイド(1)の続きです。

修理ガイドのカタログ(ICFP2007 (2) 見つけた画像の一番下)に従ってページを見ていきます。

(page 85 help_patching_dna)


blue zoneのスタックにデータを積む方法やgreen zone内のサブルーチンを呼び出す方法が書いてあります。green zone内のサブルーチンはgreen zoneの直前に置かれることを前提にしているので、ユーザーのprefixの前とかに置いても正しく動作しません。

新たなマーカーが2つ登場しています。IFPICFPPCCCはサブルーチン呼び出し用ルーチンを探すためのマーカーで、IFPICPPCFIPPはblue zoneを探すためのマーカーです。
blue zone markerはGZ+729594で見つかります(GZ+ほにゃはgreen zoneからのオフセットの意味)。この直後のGZ+7295a1からblue zoneが開始します。
サブルーチン呼び出し用ルーチンのマーカーは一つ目がGZ+24344Bで二つ目がGZ+25357dで見つかります。このルーチンの開始番地は最初のマーカーの後なのでGZ+253456になります。このあたりからオチコボレはじめています。

page 84は暗号化されているそうで見れませんでした。

(page 2181889 help_undocumented_rna)


無効RNAのことが書いてあります。morphing processって何？

(page 5 help_lsystems)


Lシステムというのがあるみたいです。見た感じ再帰的に絵を描くものみたいです。画像の修復に使うのではないでしょうか。

(page 4405829 help_fuun_security)


なにやら暗号化されているようです。雰囲気的に原文は英語で単換字式暗号っぽいです。
英語で1文字の単語はaなのでa→nに変換されているっぽいです。そうすると下の方の5.の次の行はA.になるので、その次の行はB.でしょうか。となるとb→oになっています。3.の行にある0 gb 255はたぶんtoでしょう(t→g, o→b)。3番目のパラグラフのカッコ内の24-npvqはたぶん24-acidなのでc→p, i→v, d→qが分かります。NqqはAddなのでNyyはAから始まる3文字だとAllです(l→y)。sbbは?ooですがたぶんfoo、oneはba?ですがたぶんbarです(f→s, r→e)。よく出てくるgur(t??)をtheに決め打ちにします(h→u, e→r)。対応表を作ってみると
a→n
b→o
c→p
d→q
e→r
f→s
・・・
というわけでシーザー暗号でした。平文に復号するのは面倒そうです。

(page 123456 help_compression_rna)


RNAの圧縮について書いてあります。

画像を貼るのに疲れてきたのでこのくらいにしておきます。この次はカタログページに載っていないページをいくつか見つけたので、それを載せます(p.3 p.100 p.1024等)。いっぱい情報がはいりすぎで、混乱気味です。

ICFP2007 (3) 修理ガイド(1)

ICFP2007 (2) 見つけた画像の続きです。

前回の修理ガイドのカタログに従ってページを見ていきます。

(page 1729 help_fuun_structure)


DNA自体は3つのエリアに別れていて、先頭のred zoneには現在実行しているコード片が置かれていて、red zoneに置かれるコード片はgreen zoneからコピーされてくることや、blue zoneが作業域として使われることなんかが書いてあります。blue zoneは実際はスタックになっています。

(page 8 help_encodings)


真理値はPとFとか色々書いてあります。負の数は1の補数じゃない？文字は9acidと書いてありますが、数値は最後にPがつくので実際は8bitです。ここまでに色々なフォントが出てきていますが、画像として表示しているのではなく、フォントテーブルと文字列といった形で表示しているみたいです。

self testをしたり、空が青くなるprefixではF→PやP→Fという書き換えをしていましたが、これは真を偽にしたりといった真理値の書き換えだったということです。

次のpage 23 Activating Genesは暗号化されているそうなので中身は見れませんでした。
(page 23 help_activating_genes)

(page 42 printGeneTable)


一番左の列がgreen zoneからのオフセットで、二番目の列が長さ、三番目の列が名前です。14pageのうちの1page目ということですが、他のページも見れるのでしょうか？試しにpage 43を見てみましたが駄目でした。

page 43の画像


green zoneの先頭にIFPICFPPCFFPPというマーカー(?)があることも分かります。検索してみると先頭から13615バイト目からの13バイトで見つかります。この値はマーカーとしては使えません。IFPICFPPCFFPPの先頭のIのあるところがgreen zoneの先頭番地だからです。

ダメージを受けたエントリー(damaged entry)という表示は、表示の上や下のエントリーがダメージを受けているという意味ではなくて、本来ならそこに表示すべき値がダメージを受けていて表示できないという意味です。

integrity checkはよく分かりません。一般的には壊れているかどうかハッシュ値とかで検査するという意味のはずです。

長さが短いのはグローバル変数っぽいです。int24とかint9とか書いてあります。int9は8bit、int24は23bit?

一番最初のAAA_geneTablePageNrは0x510から24バイトです。前回のダンプの範囲なので見てみます。

0004d0  CCCPCCCCCCCCPIFP
0004e0  CFFPIIIIIIIIIIII
0004f0  IIIIIIIIIIIPIFPF
000500  PIIIIIIIIPIFPFIP
000510  IIIIIIIIIIIIIIII
000520  IIIIIIIPCCCCCCCC

直前にIFPFIPマーカーがついていて、値が0になっています。前回あてずっぽうにマーカーでないかと思ったものは実際にマーカーとして使えそうです。名前からすると、ページ番号なので14ページの他のページが見れるかもしれません(後回し)。

(page 112 most_wanted)


イメージというか画像も貼れるんですね。原理的にはできることは分かりますがなんかすごいです。これはジョークでしょうか。一番下の外人さんは誰？

(page 10646 printCharSet)


page 8 encodingで触れられていた文字セットです。って、文字が全部四角になっています。昔なつかしいEBCDICを寝かせています。これを見てピーンとくるのはかなり年配の人ってこと? (分かったので年寄りかも・・・)

長くなってきたので続きます。

ICFP2007 (2) 見つけた画像

ICFP2007 (1)の続きです。

RNAは1つが7文字で表されるコマンドで、このコマンドがひたすら並んでいます。パラメータとかはないのでタートルグラフィックみたいな感じです。色はバケツにためた色の平均になります。バケツに赤を入れるとか青を入れるといったコマンドがあります。描画コマンド自体は直線と塗りつぶしだけです。色はRGB以外にTransparency(透明度?)が画素ごとにあって、画像を重ね合わせるときの比率になります。画素数は600x600で作業用に9個まで同サイズの画像を作って、後で重ね合わせることができます。コマンド自体は20種類なのですが、RNAには無効なコマンドがたくさん含まれています。処理するときは単純に無視するだけですが、何かのマーカーになっているのかもしれません。

画像表示のデバッグの時に見つけた画像です。最初に一瞬だけ表示されます。左上にprefixらしきものが見えます。


IIPIFFCPICFPPICIICCIICIPPPFIICと書いてあります。これはDNAからIFPCFFPというマーカーを探して、マーカーに続くIをCに置き換えています。ドキュメントの記法に従えばpatternが(?IFPCFFP)I、templateが#0,0Cです(#はドキュメントのn_lの代わりです)。IFPCFFP自体はendo.dnaの先頭から14860バイト目にあるので14867バイト目を書き換えていることになります。IFPCFFPマーカーの直後はIが23個並んでPが1個あります。

このprefixを連結してみると次の画像が得られました。
(page 1 help_intro)


ここにもprefixが2つあります。IIPIFFCPICFPPICIICCCIICPPPCFIICとIIPIFFCPICPCIICICIICIPPPPIICです。最初のはIFPCFFPマーカーを探して直後のIIをICにしています。マーカーは上のと一緒です。直後の23個のIのうちどれかをCにすると違うことがおきるようです。後のprefixはIFPFIマーカー直後のPをFに書き換えています。新たなマーカーです。フラグ(?)を書き換えると色々なことがおきるということでしょうか？

とりあえず最初の方をつけてみたときの画像です。
(page 2 help_integer_encoding)


また、新たな画像が出ました。こうやってマーカーとかヒントを探していくアドベンチャーゲームみたいなものなんでしょうか？でも、元々のコンテストの目的の画像の修復とはどんな関係にあるんでしょう。

後の方のprefixをつけてみたときの画像です。


問題の誤り入り画像より空というか全体が明るくなっています。とりあえず、こっちの方はほっておいてrepair guideの方を追っかけてみます。もしかすると、アドベンチャーゲームで言うと選択ミス？罠にはまったかもしれません。このあたりはたぶんチュートリアルというか操作の基本になれる例題と割り切ります。

この段階でマーカーは3つ分かっています。
(1) IFPP 直後をF→Pでセルフテスト
(2) IFPCFFP 直後をI→Cでrepair guideの画面(上から2番目)、直後をII→ICでrepair guide navigationの画面(上から3番目)
(3) IFPFI 直後をP→Fで青空画面(上から4番目)

repair guide navigation画面でexisting repair guide prefixと言っているのは(2)のIFPCFFPのことだと思われます。また、2進数に最下位ビットからエンコードして0をI、1をCで置き換えるということも書いてあります。IをCに書き換えているのでrepair guideはpage 1、IIをICに置き換えているのでrepair guide navigationはpage 2ということになります。そして、カタログページのインデックスが1337と書いてあります。

ちょっと寄り道。既存のマーカーは(といっても3つだけだけど)全てIFPから始まっています。patternだとマーカーの検索はIFから始まることになっていて、3文字目はは何でもよくて4文字目以降に探索するマーカーを書くことになっています。見た感じ、3文字目としてはFが使われているみたいです。templateだとIFはIPと書いてもいいことになっているけど、たいていIPが使われています。何が言いたいかというと、もしかするとpatternとtemplateにはIFPというのが現れないからIFPがマーカーの接頭辞として使われているのかもしれない、ということです。それならIFPを検索すればマーカーの一覧が作れるかもしれないとふと思いました。

試しにダンプしてみるとマーカーっぽいものが見つかります

0004d0  CCCPCCCCCCCCPIFP
0004e0  CFFPIIIIIIIIIIII
0004f0  IIIIIIIIIIIPIFPF
000500  PIIIIIIIIPIFPFIP
000510  IIIIIIIIIIIIIIII
000520  IIIIIIIPCCCCCCCC

0004dd-0004e3にマーカーIFPCFFP (既出(2))
0004fc-000500にマーカーIFPFP (未知、IFPFPIとかかもしれない)
00050a-00050eにマーカーIFPFI (既出(3))
(アドレスはGreenZone起点)

さて、1337は16進で0x539最下位から2進でエンコードすると1001 1100 101、0→I, 1→CにするとCIIC CCII CICになります。page1やpage2を表示したprefixを真似してIFPCFFPマーカーの直後の11個のIをCIICCCIICICに書き換えるprefixを作ります。
IIPIFFCPICFPPICIICCCCCCCCCCCCIICIPPPFCCFFFCCFCFIICです。patternとtemplateの解釈時に文字変換が行われるのでI→C、C→Fになります。

作ったprefixを連結した画像です。
(page 1337 help_catalog_page)


さらにいっぱいページが見れそうです。下から2番目の「究極の答え」というのはSFで有名な42のことでしょうか。長くなってきたので続きます。

ICFP2007 (1)

ICFP2007というプログラミングコンテストが7/20-23に開催されたそうです。もう1ヶ月くらい前になりますが開催されたことすら知らなかったのでもちろん参加はしていません。

おもしろそうなのでプログラムを作りはじめたのですが、こりゃまた大変で、こんなのたった3日でできるの？って感じです。分かったことと、今までのまとめを書いておくことにします。

DNAという文字列を規則にしたがって変換するとRNAという文字列になります。このRNAは描画コマンドになっているので、RNAを解釈すると画像が得られます。問題では初期DNAと、初期DNAから生成される誤りを含んだ画像と、ゴールの画像が与えられます。初期DNAの前に連結するprefixと呼ばれるDNAを開発して、なるべくゴール画像に近づけるというコンテストです。単にゴール画像に近いだけでなく、なるべく短いprefixの方が得点が高くなるようです。

コンテスト自体はprefixコードをサーバーに送ると自動的に採点するというもので、どんな手段を使ったかはコンテストには関係しなかったようです。

DNAもRNAも塩基(base)と呼ばれる4種類の文字から出来ています。DNAに対する操作も部分列を取り出したり連結したりコピーしたりといった、いわゆる文字列操作みたいなことばかりなので、まるで本物のDNAみたいです。

DNAの操作は以下の4つのことをひたすら繰り返します。この操作についてはpdfドキュメントに仕様が(英語で)書かれています。

(1) DNAの先頭からpatternと呼ばれる部分列を切り出す
(2) patternの続きからtemplateと呼ばれる部分列を切り出す
(3) (match) patternとtemplateを取り除いたDNAに対して、patternに従ってDNAの部分列を複数切り出す。
    DNAがpatternにうまく適合しないときは(4)は行わない
(4) (replace)
  (4-1) DNAからpatternにmatchした部分を切り取る。
  (4-2) templateに従って(3)で作った部分列を並び替える。
        場合によってはtemplate内にある定数を付け加える。
  (4-3) (4-2)で作ったDNAと(4-1)で残ったDNAをつないで新たなDNAにする。

足し算命令や掛け算命令のあるマイコンとかと全く違うアーキテクチャです。patternとtemplateが基本命令で、この繰り返しになっていると考えることもできます。DNAの先頭にあるpatternとtemplateを解釈するので、プログラムカウンタは常にDNAの先頭にあることになります。サブルーチン呼び出しはサブルーチンを表すDNA部分列を先頭に連結してやります。DNAの後ろの方はスタックとして使用しています。

DNAのRNAへの変換は、やたら文字列連結と部分列の切り出しが多く、まじめにデータ構造を考えてやらないと破綻します(というか破綻しました)。そのあたりはドキュメントにもヒントとして書かれています。

とりあえず、今までの履歴

コンピュータ関連の英語を読んだことがあまりなかったので言葉がよく分からなくてドキュメントを理解するのに結構時間がかかりました。

最初、javaの勉強もかねてjavaで書き始めましたが、上でも書いたように文字列操作が遅すぎて全く実用になりませんでした。たぶんRNAへの変換に数ヶ月かかっていたかもしれません。ちなみにRNA変換は1891886回、上の4つを繰り返します。

次にbyte配列へのリンクリストみたいなデータ構造を考えて作り直してみました。部分文字列の大量発生でリンクノードがあふれてしまってメモリ不足になってしまいました。

しかたないので、リンクノードの数がある程度以上になったら、新たに配列を取ってリンクされたbyte列を1つの配列に作り直す処理を追加してやったところ、なんとか最後までいけるようになりました。このときで確か5分くらいかかっていたと思います。

たぶんコンテスト的には、このくらいのプログラムができたら、本題に取り掛かるのでしょうが、どうせ参加しているわけでもないのでプログラムの改造をしていました。動作を眺めていると元のDNAとほぼ同じ長さの長い部分列が含まれていることが多いのに気づきました。ほぼ7Mバイトくらいあるのでこれをコピーするのは時間がもったいないので、DNAの再構築処理から長い部分列を除外して短いものだけ作り直すように変えてみたところ、ほぼ2分くらいでRNA変換ができるようになりました。短い部分列の追加はStringを使って、ある程度まとまったらリンクリストに参加させるようにしたのも効果があったようです。

javaは遅いという話もあるようなのでCで書き直してみようと思いました。C++はよく分かっていないので、とりあえず分かるCです。javaからCへの移植作業は結構たいへんでした。参照されているbyte配列に参照カウンタをつけて0になったらfreeするみたいな仕組みも全部書いてやらないといけません。結果としては7秒ちょいくらいでRNA変換ができるようになりました。手間がかかる分速く動くというところでしょうか。

まだコンテストのスタートラインにすらたっていないです。72時間なんて絶対無理。さすが世界のコンテストはレベルが高い。

RNAから絵を出すプログラムも途中で書いています。RNA変換のデバッグ用です。WIN32APIをたたくCのプログラムです。Cは古いVisual C++6.0をVMWareの上で動かしています。

このあたりでほぼ2週間くらい毎日1時間とか2時間とかやっていました。チーム参加ありのコンテストなので、かわるがわる寝たり、分担して複数のプログラムを作ったりしないと上位入賞は難しそうです。

ドキュメントに簡単なprefixが載っています。IIPIFFCPICICIICPIICIPPPICIICです。これはDNAの中からIFPPというマーカーを探して、マーカーの次がFならPに書き換えるという意味のDNAになっています。これを連結して実行してみると次のような画像がでました。セルフテストなわけですがデバッグにとても役にたちました。

画像のセーブ機能がないので(笑)、alt+PrintScreenでPaintに貼り付けてセーブしました。

この後DNAに含まれている隠し画像みたいなのをいくつか見つけました。長くなってきたので続きます。