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ドキュメントに仕様が(英語で)書かれています。
足し算命令や掛け算命令のあるマイコンとかと全く違うアーキテクチャです。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に含まれている隠し画像みたいなのをいくつか見つけました。長くなってきたので続きます。
おもしろそうなのでプログラムを作りはじめたのですが、こりゃまた大変で、こんなのたった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に含まれている隠し画像みたいなのをいくつか見つけました。長くなってきたので続きます。
