We did'nt find time to document our approach in detail.

  1. short:
  • dna to rna converter in Java (for speed optimisation we used a linked list of strings with defragmentation functionality for the DNA. 1min 30 on a normal PC for the source dna)
  • rna to image converter in Java with GUI
  • a small and very simple compiler from a imperative language to fuun written Haskell
  • some other small tools like a super-adaptive-gene tree extractor

and a inspector for parts of the dna written in Haskell

We unfortunatelly got the right idea how to access the gene table pages too late. We only managed to turn the windmill and to switch on the daylight. However we optimised the prefix with direct skips and got it down to 78 bases and managed a survival chance of 4.2009%. We end up on place 25 and are quite happy with it.

Here a comment from Johannes, short after the issue of the task.

Pattern:   ( !_2 ) _P

IIP  (
  -     !_
ICP       2
IIC  )
  -   _P
IIF  ) end of pattern


Template:  _P _I 0_0

  -  _P
C   _I
  -   n_k-form folgt
P   0
P   0
IIC   )  end of template


Match (für den Rest  CFPC  )

CF   -> [[ CF ]]  environment
P    -> geprüft und ignoriert
C    -> bleibt stehen (nicht im Pattern)


Replace (ausgehend von Template)

_P   -> P
_I   -> I
0_0  -> CF  (aus Environment, 0-mal quotiert)

        C blieb stehen.

Tja. Da müssen wir also zwei Interpreter schreiben: execute und build. Evtl. erstmal prototypen, die das direkt so machen, wie in der Spec bescrieben (es steht ja alles da). Dabei dann über Optimierungen nachdenken.

Es wird ja wohl in die Richtung gehen, daß man das ewige Stringmatchen vermeidet und stattdessen direkt auf einer Baumstruktur arbeitet. Problem ist natürlich, daß die nicht lokal eindeutig ist (wenn man nur einen Ausschnitt sieht, weiß man z. B. nicht, ob IIC Klammer zu ist oder Teil einer Binärzahl). Deswegen könnte man ein Typsystem erfinden (mit Typchecker) für “sichere” Programme (z. B.: was einmal binärzahl ist, bleibt binärzahl) und dann hoffen, daß die verwendeten Programme auch diese Eigenschaft haben (typisierbar sind). Man könnte die Typen bei der Ausführung prüfen oder aber schon vorher.


projects/icfp2007/our-approach.txt · Last modified: 13.11.2008 22:34 (external edit)