ICFP Programming Contest 2007

Again, I participated as a one-person team. And, as has become the norm for me at ICFP-Contest time, I had to go partying on saturday evening. This year it was a friend's 50s anniversary.

The task was published 12:00 local time, and I managed to whip up a simple implementation of execute in Haskell over the afternoon, between work tasks (sort of). This went really well (or so I thought), and while it ran without errors, it didn't seem to get anywhere. DNA data structure much too slow, of course.

This continued to be the case through the whole weekend, including several different implementations in my not-so-favorite - but very familiar - work language, Java. On monday morning, I finally had an array-based Java implementation that would 'only' take several hours to produce Endo's rna.

In contrast to execute, I had no trouble at all with the build step. A small java program soon reproduced an exact copy of the source image from the rna. Unfortunately, I'd written this strictly as batch program, which just wrote the final image to disk as a 'plain' format ppm file. The idea that messages might be hidden in intermediate images never entered my mind.

So, the only thing left was the prefix provided in the task description, which quickly yielded the self check image. After that, it was time over.

So, I did not submit a single prefix with a chance to save Endo. Fortunately, other teams did better, and there's still hope that Endo will be saved.

After the contest

I continued to work on a faster version of execute. A DNA implemented as a linked list of array chunks, with occasional compression if the list got too long, finally yielded a reasonable run time of about 5 minutes for endo.dna.

After reading that another team using Haskell had found Data.Sequence fast enough for using it in execute, I tried that too. And immediately got a runtime of 6 minutes!

Naturally, I felt stupid having spent most of the contest time on a DNA sequence implementation when a working one was just waiting to be used.

My next step (time permitting) will be to write a version of the build program which constantly displays the image as the rna is executed.

Final thoughts

I really liked this year's task, even though I never got to the "fun" parts at all.

My performance left something to be desired, though. I'm perfectly ok with not getting far in the creative, 'puzzle' part of a task. With basic algorithms and data structures however, I'm supposed to do reasonably well, and I certainly didn't. That I could not come up with a performant DNA implementation in Haskell really irritates me.

Page history:

2007-07-24

First quick draft.