Thursday, August 23, 2007

Investigating Endo: Junk DNA

My friend Marco has blogged about my team's experience in the ICFP, but since the contest, I've been investigating Endo's DNA. Johann Jeuring is slowly revealing some interesting facts, but as we know, he was kidnapped by Fuun invaders, and so we can't really trust what he tells us.

I've discovered some truly remarkable properties of Fuun DNA, the proof of which this blog is wide enough to contain. Unfortunately Earth's internet has already been infiltrated by Fuun agents, as attested by their subversion of the ICFP itself.

I will, however, reveal a single DNA sequence, which may prove useful in the defense against Fuun invaders, should they further threaten our planet. When "executed" it generates large amounts of "junk DNA". JB and HM indicate that in generates on the order of 10865 acids in about 101730 iterations before destroying itself, but of course our gene simulators would take many years to confirm this.

Anyone who discovers more about this sequence or others related to it should post them on this blog, so that we may broaden our knowledge of our universe's lifeforms, and begin to coordinate anti-Fuun defense, should it be necessary.

IIPIFFCFPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPIC
PIFPCPIFPICPIICICFFFICFCIPIICFCCCCICFCPICFCFICFFII
CFFCIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICCFPPFIICIFPPICFCFPFFFFCFPFICCFPFPFCCFPFICIFPCPC
FPPFIICIIPIFFCFPFCIICICCCFPFFFFCFPFICCFPFPIIPIFFCF
PPCIICIIPIFFCFPFICIICIICIFPPICFCFPFFIFPICPCFPFPFCC
FPFICIFPCPIICIIPIFFCFPFCIICICCCFPFFFCCFPFICCFPFPCF
PPCIICIFPPPFCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICCCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIPI
FFCFPPCIICIICIFPPPFCFPFFIFPCPCFPFPIFPICPFFCFPFICII
CIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPCIIC
CFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCFPP
FIICIIPIFFCFPFCIICICFCFPFFFFCFPFICCFPFPIIPIFFCFPPC
IICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFPFPFFCFPF
ICIFPCPIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICICCFPFFFFCFPFICCFPFPFFCFPFI
CIFPCPCFPPFIICIIPIFFCFPFCIICICFCFPFFFCCFPFICCFPFPI
IPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPICICCFPFFIFPICP
CFPFPFFCFPFICIFPCPIICIIPIFFCFPFCIICICPCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFCCFP
FICIICIIPIFFCFPFCIICICPCFPFFFFCFPFICCFPFPIIPIFFCFP
FICIICIIPIFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPI
CPFCCFPFICIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFPII
PIFFCFPPCIICCFPPFIICIFPPPCCFPFFFFCFPFICCFPFPFCCFPF
ICIFPCPCFPPFIICIIPIFFCFPFCIICICPCFPFFFCCFPFICCFPFP
IIPIFFCFPPCIICIIPIFFCFPFICIICIICIFPPPCCFPFFIFPICPC
FPFPFCCFPFICIFPCPIICIIPIFFCFPFCIICICICCFPFFFFCFPFI
CCFPFPCFPPCIICIFPPPCCFPFFFFCFPFICCFPFPCFPPCFFCFPFI
CIICIIPIFFCFPFCIICICICCFPFFFFCFPFICCFPFPIIPIFFCFPF
ICIICIIPIFFCFPPCIICIICIFPPPCCFPFFIFPCPCFPFPIFPICPF
FCFPFICIICIIPIFFCFPFCIICICICCFPFFFCCFPFICCFPFPCFPP
CIICIFPPICICCFPFFFFCFPFICCFPFPCFPPCFFCFPFICIICIIPI
FFCFPFCIICICICCFPFFFCCFPFICCFPFPIIPIFFCFPFICIICIIP
IFFCFPPCIICIICIFPPICICCFPFFIFPCPCFPFPIFPICPFFCFPFI
CIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPPCI
ICCFPPFIICIFPPICCCFPFFFFCFPFICCFPFPFFCFPFICIFPCPCF
PPFIICIIPIFFCFPFCIICPCCFPFFFFCFPFICCFPFPIIPIFFCFPP
CIICIIPIFFCFPFICIICIICIFPPICCCFPFFIFPICPCFPFPFFCFP
FICIFPCPIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIPIF
FCFPPCIICCFPPFIICIFPPICPCFPFFFFCFPFICCFPFPFCCFPFIC
IFPCPCFPPFIICIIPIFFCFPFCIICPCCFPFFFCCFPFICCFPFPIIP
IFFCFPPCIICIIPIFFCFPFICIICIICIFPPICPCFPFFIFPICPCFP
FPFCCFPFICIFPCPIICIIPIFFCFPFCIICPFCFPFFFFCFPFICCFP
FPCFPPCIICIFPPICCCFPFFFFCFPFICCFPFPCFPPCFCCFPFICII
CIIPIFFCFPFCIICPFCFPFFFFCFPFICCFPFPIIPIFFCFPFICIIC
IIPIFFCFPPCIICIICIFPPICCCFPFFIFPCPCFPFPIFPICPFCCFP
FICIICIFFCFPFCPFCFPFFFCCFPFICIFFCFPPPIICIICIIPIFFC
FPPPIICIIPIFFCFPPFIICIIPIFFCFPPPIICIICIFPICPIFPCPI
FPICPIICICFFF


As a token, I leave you with this essence of my deepest result yet: 54c763a5f6b9beba26eeae2e98ba786f45b0fef8.

EDIT: Thanks to Jochen for the correction. In case you were worrying, he is not a Fuun agent: I have carefully checked his patch.

4 comments:

  1. Okay it is obvious who JB and HM are. It looks like their #r.

    I think there is a typo; you start in state "C" instead of "A"

    the second line
    ...ICFCIPFICFCC...
    should be
    ...ICFCIPIICFCC...

    or am I missing something here?

    ReplyDelete
  2. Jochen,

    You've got it in one. 100 points.

    Yes, your correction is correct :). Did you parse it by hand or do you have some funky tools?

    I guess JB and HM are obvious if you know something about this field.

    May I ask what team you were on?

    Have you got any interesting DNA sequences of your own? Please share them.

    I'm pretty chuffed that you not only bothered to read this, but took some time out to investigate. Thank you.

    ReplyDelete
  3. I first started converting by hand (working so much on DNA lately that I can already read it almost fluently). Then I used my perl script that converts DNA to patterns and used search/replace to convert the markers like ICFCC to some special symbols.

    I'm still working on minimizing my perfect prefix. My latest prefix has risk 5338 and produces the correct target image.

    It may be interesting to analyze, especially the simple Huffman-compression, the patching loop and the reversal loop.

    Our team was SwtPl.

    ReplyDelete
  4. Here is another way to sabotage Fuun DNA:

    IIPPIICIICIPCCCCCCCCCCCCCCC
    CCCCCCCCCCCCCCCPPIICFIICIIC

    This is converted to the empty string in only two iterations, but it has a cost and a maximum DNA length of more than 10^(10^8).

    ReplyDelete