2007/問題文/Fuun DNA - ranha-icfp @ ウィキ

Fuun DNA

Fuun DNAは、有限長の連続する4種の塩基から成り立っている。
ここでいう4つの塩基とは

I(infinine), C(continuine), F(functorine), P(polymorphine)

の事である。
地球でのDNAとは、build planを圧縮したプログラムで、実行するとRNAを生成する。RNAは順番にタンパク構造に指示し、タンパクは全生物の品種の構造区画を構築します。

Fuunの為に、状態はほぼ同様ですが、2,3の例外が存在します。

1. RNAを生産する際に、Fuun DNAを実行するとDNA自体を操作することになります。人間の場合と同じく、Fuun RNAタンパクの生成・合成を指示し、生きている状態で終了します。
2. Fuun DNAはもう一つの一部を変えることが可能です。これは、もうひとつへのprefixとしてのDNAを用いることで達成されます。もう一つのFuun DNAにFuun DNAを前に付加することは、やや異なったFuunを生成します。
3. Fuun DNAは作用するだけでなく即座に環境に適応するという驚くべき特徴を備えています
4. 地球の生物に反して、Fuunは知的デザインの結果としてそうなったと仮定されます。Endoを変える計画を助けてくれるプレゼントして、ArrowはDNAの中に作者からの「メッセージ」が含まれているかもしれない。そして、遺伝子がすでに存在するかもしれないという事実がある。とヒントを出しています。なので、我々はそれを信用しています。

我々は構築プランの作成と、その実行をシュミレートする方法を知っています。我々には、Endoをアセンブルする能力が欠如しています。Arrowはそれをすることができます。幸いにも、生物形態と、その環境の二次元の画像として、Arrowは視覚的にFuun DNAを適用する方法を説明してくれました。我々はEndoのDNAを持っており、現在の状態を視覚的に表現した画像を持っています。
Arrowは、Endoの最適修正を視覚化した「目標」画像も備えていました。完全に目標にマッチしない間、我々はEndoの生き残りの可能性をあげるため、なるべく間近まで行かなければなりません。
再連続しているDNAは、危険な事柄であり、より長いものはprefixである、より高いものは変化が失敗するという、あるいは、Endoの心が回復不能なほど損害を受けるという可能性があります。したがって我々は、出来る限り密接に目標にマッチさせるだけでなく、出来る限り短くもあるDNA prefixも見つけなければなりません。
また、再連続しているDNAは、多くのエネルギー（Arrowが損害を受けた状態があればそれは同様に不十分なリソースです）を消費して、更なる制約に至ります。
図1は、DNA変化プロセスの2段階的な構造を表します。我々は、2つの段階を2つのプログラムのパイプラインと言います。
以降は、方法に関する情報を提供します。

---

図2:DNAデータ型

1. Base ::= I|C|F|P
2. DNA ::= Base*
3. RNA ::= DNA*

図3:シーケンスの種類

1. X* タイプXの要素によるシーケンスのタイプ
2. ε 空シーケンス
3. x＜xs シーケンスxsの"前"に要素xを付加
4. xs＞x シーケンスxsの"後"に要素xを追加
5. xs◇ys 2つのシーケンスxsとysを連結
6. xs[m..n] xsの結果は、index mからindex nの一つ前(つまりindex (n-1))。決して失敗しない
7. xs[m..] xsの結果(mで始まる)(xs[m..len xs]の省略形)
8. xs[n] 第n番目の要素(ひとつの要素 xs[n..(n + 1)])またはε
9. len xs シーケンスxsの長さ

• DNAをRNAに変化させてください。(プログラムの実行についてはchap3)
• 画像を生成することで、RNAから生合成をシュミレーションしてください。(プログラムの構築についてはchap4)
• 特定のDNA prefixを与えられるEndoの生き残りの可能性を推定して、そのようなprefixを我々に提出してください。(chap5)
• 元のDNA文字列で始まって、我々がこの説明を集めている間、我々自身実行することができた微小な実験に基づいてください。(chap6)