Tja, ich hab' mich dran versucht, bin aber nicht so weit gekommen.
Kurz die Aufgabe umrissen: Es gibt eine Alien DNA mit den Basen I, C, F und P. Diese DNA kann man "ausführen". Dabei wird immer ein Muster (pattern) und eine Vorlage (template) vom Anfang der DNA dekodiert und das auf den Rest angewendet. So ähnlich wie reguläre Ausdrücke. Vom Muster bekommt man einen "Match" mit Gruppen und in der Vorlage können Referenzen auf "gematchte" Gruppen vorkommen. Nach der Ersetzung wird das Ergebnis vor die restliche DNA gehängt und das ganze geht von vorn los. Solange bis keine DNA mehr vorhanden ist.
Beim Dekodieren von Mustern und Vorlagen gibt's auch Regeln bei denen Teile der DNA in RNA überführt wird. Diese RNA wird in einem weiteren Schritt als Folge von Anweisungen für eine Art "Turtle"-Grafik benutzt.
Das Bild soll man durch voranstellen eines eigenen DNA-Stücks so ändern, dass ein vorgegebenes Zielbild heraus kommt.
Die Programmstücke zum "Ausführen" der DNA und Malen eines Bildes aus RNA sind in der Aufgabenstellung recht ausführlich in Pseudocode angegeben. Trotzdem nicht ganz einfach umzusetzen, weil die Fehlersuche bei den grossen Datenmengen ─ lange Ketten aus den vier Basen ─ nicht so leicht ist. Ich hatte einen Fehler, den ich erst am Sonntag gefunden hatte, nachdem die Veranstalter so gnädig waren ein paar Eckdaten der ersten 10 Iterationen des Suchen und Ersetzen-Teils zu verraten.
Als es dann lief, lief es laaaangsam. Ich habe eine recht naive Implementierung der DNA und die Laufzeit wird vom "Vorhängen" der Ersetzung vor die Rest-DNA dominiert. Da werden dann immer lustig grosse Zeichenketten im Speicher angelegt, umherkopiert und wieder freigegeben. Mehr als ca. 20 Iterationen pro Sekunde gibt mein Rechner nicht her. Die Original-DNA benötigt allerdings ca. 1,8 Millionen Iterationen bevor sie abgearbeitet ist. Das wären 25 Stunden. Argh.
An der Stelle habe ich das Handtuch geworfen.
Wenn ich weiter gemacht hätte, dann mit einer Implementierung einer verketteten Liste von DNA-Segmenten um diese `prepend()`-Operation in O(1) Zeit durchzuführen. Das hätte allerdings bedeutet, entweder die Suchoperation einer Teilsequenz in Python zu programmieren ─ vorher konnte ich einfach `str.index()` benutzen ─ oder auf C auszuweichen. Dann hätte ich noch die "RNA-Turtle" implementieren/debuggen müssen und dann die DNA "reparieren". Das alles in nicht mal mehr einem Tag, erschien nicht schaffbar.
Etwas verwundert hat mich, dass jemand auf der Mailingliste mit Java und einem ähnlich naiven Ansatz, eine noch deutlich langsamere Lösung hat. Es wurde die Vermutung geäussert, dass das daran liegen könnte, dass Java's Zeichenketten Unicode-Zeichenketten sind.
Ich habe auf jeden Fall vor, noch ein bisschen weiter zu basteln. Ohne Zeitdruck.
).