ICFP, if you don't know, stands for International Conference on Functional Programming. Functional programming is my favorite kind of programming.
I'll try to tell the story in layman's terms as much as possible. Warning: spoilers.
Before the problem was even unveiled, we had set up a Pibb channel to act as a sort of digital "whiteboard", and
Friday
The problem was unveiled at 3am Friday morning (a reasonable time if you live in Utrecht).
It said that an alien life form, called Endo the Fuun, had crash landed on Earth, and needed his DNA modified in order to be able to survive in our environment. They gave us an algorithm we could use to simulate how Endo's DNA gets converted to RNA, and another algorithm we could use to simulate how Endo's RNA would get translated into Endo itself, by translating it into a 600x600 image. And, of course, they gave us a copy of Endo's DNA sequence, which was 7.5 million bases long. Unlike Earth DNA sequences, which are represented by the letters A, C, G, and T, Endo's DNA is sequence represented by the letters I, C, F, and P. Cute.
In case it isn't obvious, Endo's DNA was a computer program, and the two algorithms were programming languages, one for manipulating DNA/RNA sequences, and one for translating the RNA result into a picture. For handy reference, they showed us a picture of what Endo's DNA produces after you execute it.
Our task was to create a "prefix" DNA sequence, which if you attached it to the beginning of Endo's DNA, would produce this picture:
The problem statement even spelled out exactly how our entries would be judged: a computer program written by the contest organizers would run our DNA sequence, convert it to an image, and analyze the image to produce a "survival probability". It would mostly be based on counting how many pixels were correct, with a slight penalty if your DNA sequence was overly long.
I met the others at Fuel Cafe about 8:30 or 9.
While I combed through the problem statement,

At around 11:30 we moved to my house and holed up in the basement. The DNA-to-RNA program was slow going. The RNA-to-picture program was mostly done, but it was extremely slow, and we couldn't see how to speed it up without rewriting it in a different language. So
By about 2, the DNA-to-RNA program was partly working, but it seemed very buggy--it just didn't seem to produce correct looking results. I switched over to look at that with
A lot of coding and debugging followed.

At around 8 or 9 pm, we had "finished" coding both the DNA-to-RNA and RNA-to-picture programs, and fixed most of the bugs. We were anxious to process DNA to RNA so that we could run it and start seeing pictures. Only problem: the DNA-to-RNA program was impossibly slow. So slow that there was no way it would finish executing before the contest was finished. And we hadn't yet begun to think about to write the DNA-modifying program that we would eventually have to submit.
A happy side effect of the slowness of the code was that we found a hint we would have otherwise missed. The first thing the Endo DNA does when you execute it is output drawing commands that produce this image:
And then it immediately erases it.
Clearly this was a sequence we were supposed to try applying to Endo's DNA. We tried applying it, but our code was so slow that we couldn't see its effect.
Finally,
Sometime around 2 am I curled up to sleep on the couch.
Saturday
About 6am I woke up again, with Tina (one of the cats) asleep on top of my feet. They were extremely warm.
The others got up soon afterward, and
At some point someone reread the problem statement and noticed this promising hint: "we noticed that something curious happens if the following prefix is used: IIPIFFCPICICIICPIICIPPPICIIC". We ran that sequence and got this image:
Clearly we had some bugs, and we suspected they were in our RNA-to-image code. They were. I found one bug, which caused the image to get more and more transparent as the drawing process went on, and
Now our images looked like this:
And
At some point we remembered the DNA sequence that we had first tried prepending to Endo's DNA (the sequence that Endo draws and then erases when you start executing its DNA), and tried running it again now that our code was fast. It produced the "field repair guide" image.
We headed for breakfast somewhere on Mississippi. We felt great: the contest was less than half over, and we had already managed to render the source image and find two hint images.
We had a lot of great ideas about where to go next, but I can't remember what they were. I should go find our notes from that breakfast (which are still at Farpoint) and transcribe them for for posterity.
Here's what we actually wound up doing, as far as I can remember. I don't really remember who did what.
We tried the sequences we found in the field repair guide. Some of them led us to still more images, which contained other sequences and text. The field repair guide turned out to be a manual with a dozen or so pages. Some of them were beautiful. Some contained data in code. Some of them were silly. Here's one of my favorites:
At some point I started executing some of Endo's DNA by hand, trying to understand how it worked. I found a pattern that seemed to be a kind of function call. Someone else (
I continued hand executing Endo's DNA (doing dynamic analysis, if you will), and started picking up some of the clever techniques the contest authors had come up with to use Endo's DNA-to-RNA rules as a programming language.
I don't remember what everyone else was doing. But several times during the day, someone would tell me and
We had a late lunch/dinner (at Thai Noon I think) and headed back to Farpoint.
I began to become despondent again. Although we had made a lot of progress in understanding how Endo's DNA worked, it was clear that we had a long long way to go before we could write a program of any significant length in Endo's DNA language, and it seemed like we were going to have to write a pretty huge program in order to paint all the shapes that were different between the two images.
Then, shortly before 5pm, we had a breakthrough. Someone noticed that we had forgotten to follow up on one of the prefix sequences in the field repair guide. It was 28 letters long. We tried it and discovered that it lightened up the image, so that rather than having the nighttime color scheme of the original image, it had the daytime color scheme of the image we had to produce. This was a breakthrough for two reasons: (1) it took us from having no pixels correct to having lots of pixels correct, namely all the pixels in the background of the image. (2) It gave us the hint that maybe we wouldn't have to write a huge program to draw the target picture--maybe all the elements of the target picture were already programmed into Endo, and we just had to figure out how to activate them.
We submitted the 28 letter prefix as our first entry, at 5:04pm. In about 10 seconds, the result came back. Survival probability: 1.2719%. Looking at the scoreboard, we saw that dozens of teams had the exact same score as us, and the exact same prefix length. Clearly we had all found the field repair guide, found that sequence, and tried it. So we weren't winning. But we were in the standings.
In the evening
We continued into the night doing further optimization, finding more hidden images, and following up on hints.
I think it was about 4:30am at this point. Everyone else had gone to sleep. I realized that my modification to the adaptor activator was a major breakthrough. Now I could execute any one of Endo's functions in isolation and see what it did. Some of them took a long time to run so I didn't investigate them. Others didn't work because they needed parameters, and I didn't know what parameters to give them (or even how to give them parameters). But others just worked. I found the function for drawing the apple tree, and the function for drawing a single apple. I found the function for drawing Endo's left arm, his spaceship, and the cargo box. And this was the clincher: I found a function to draw Endo's cow mouth, a shape that only existed in the target image we were supposed to produce.
Suddenly the problem seemed easy: all we had to do was figure out what each of Endo's function's did, and patch them. We'd find the function that drew the original alien Endo, and the function that drew the final cow-shaped Endo, and we would just have to replace a call to the first function with a call to the second. It was going to work.
Sunday
The sun had come up at this point. At around 7am or so
Since our DNA-to-RNA translation was still so slow, we were not able to simulate the whole effect of the prefix. But we were able to simulate its effect on the apple tree in isolation. And sure enough, it transformed it into a pear tree. At 10:08 am we submitted the patch. In about ten seconds the result came back. Survival probability? 1.3131%. Our rank in the standings? It wouldn't tell us our exact rank, because we were in the top 20.
Now, it was just after 10 am, two hours before our self-imposed stop time, 17 hours before the contest would officially end, and for all we knew, we might indeed be winning.
We had to keep going.
Some of the others spent some time working on splicing into Endo's DNA a no-op function (a function that did nothing but return). The idea was that if we wanted to make something in the image disappear (like, for example, the λxx to the left of the windmill, or the spaceship), we could replace the call to whatever function drew that thing with a call to the no-op function. But they couldn't get the no-op function to work.
They also spent some time writing a program that would interactively execute Endo's DNA one step at a time, allowing you to examine what the DNA looked like at every stage of execution. In other words, it was a debugger for Endo DNA. That was a stroke of genius. It basically automated the dynamic analysis process I had begun doing the previous day.
By around 2:30pm, we had not come up with anything better to submit, and we had fallen in the standings. I can't remember where we fell to--around 40th, maybe?
I still had not slept, and was in no mood for sleeping. I hung out with people in the park and juggled with
I can't remember when dinner was served. 6pm maybe? While I was going back for seconds, the others showed back up. They were ebullient.
Also, they realized that in order to find parts of the image we could replace, they needed to try running every one of Endo's functions to see what its output looked like. And since our DNA-to-RNA translator was still so slow, they needed to set up as many machines as possible to do it during the party. So
I finished dinner, did a little tango dancing, and listened to some lovely stories. At about 8pm,
The others explained to me that (1) the Endo DNA debugger was much improved, and could be used as a tool for figuring out how to write a no-op function, (2) nonetheless their attempts to write one had failed, and (3) they needed me. I was honored.
We got back to the house and dove right into the no-op problem. By some miracle my brain still seemed to be firing on nearly all cylinders. I knew I needed to understand the ABI in order to fix it, so I started by just brain-dumping everything I had thought about it. The others provided information they had learned while I was at the party. We watched some functions execute in the debugger. We cross-referenced with a page in the field repair guide that seemed to be obscurely trying to tell us what we wanted to know.
Slowly the remaining pieces fell into place. Endo's DNA was simulating a fairly conventional computer architecture, with scratch memory, a code segment, and a call stack. It even used fairly standard calling conventions (Pascal style IIRC, but I don't have my notes with me). Armed with this information, I wrote no-op, and it nearly worked. At some point
It was midnight. I had been up for 42 hours, and had 3 to go. I was beginning to ache all over, and my short term memory was completely gone. Every time I switched to a shell window to type a command, I immediately forgot what I was planning to type and had to spend about 20 seconds trying to remember it. But there was a bug in no-op, and I had to fix it. I found it and fixed it, and I was trying to commit it to the master source control repository when I had what
Our source control system, darcs, completely failed me.
I managed to fix the source control problem in about 20 minutes and send the fix to the others. Then I calmed down again. It was about 12:30 am and I was losing coherence.
The next big task seemed to be to transform Endo from his alien form to cow form. We started examining the routine for drawing Endo, and discovered that one of the first things it was test a flag in Endo's DNA. If the flag was "P" (meaning true), it executed one block of code; if it was "F" (meaning false), it executed another. Maybe that's how Endo is supposed to turn into a cow, we thought: we just change this flag.
My last meaningful contribution was to help find where in Endo's DNA the flag was located. We found it, flipped the flag, and re-rendered Endo. This happened at about 1:48 am. What resulted was my favorite image of all:
I could feel the smile spreading across my face as I said "those bastards!" (here is a wikipedia ref if you don't get the joke).
A few minutes later, I took a turn for the worse. It was nearly 2am, and I had not slept for 44 hours. I was having incredible lapses in concentration. Even though there was only an hour left in the contest, I realized I would not make it. I closed my laptop and announced I was going to sleep. And I did.
I woke up at about 7 the next morning with Tina curled up next to me.
Apparently they turned Endo into a duck on purpose. None of us know where the duck in the trees came from.
Submissions we made
The last column is Utrecht local time--subtract 9 hours to get to pacific daylight time. So, for example, our last submission was made at 2:55am Monday the 23rd.
Risk | Survival Chance | Prefix length | Message | Submit time |
---|---|---|---|---|
3587389 | 0.0000% | 3999 | OK | 2007-07-23 11:55:19.113691 |
1036119 | 3.0861% | 3549 | OK | 2007-07-23 11:43:35.658635 |
3594624 | 0.0000% | 3994 | OK | 2007-07-23 11:33:30.875791 |
1036316 | 3.0820% | 3746 | OK | 2007-07-23 11:22:59.168592 |
1055469 | 2.7068% | 2869 | OK | 2007-07-23 10:58:52.294476 |
1064431 | 2.5452% | 3521 | OK | 2007-07-23 10:47:39.839214 |
1050716 | 2.7960% | 3296 | OK | 2007-07-23 10:24:35.973925 |
Error | Error | Error | Zip corrupted or no Zip. | 2007-07-23 10:23:23.427417 |
3585323 | 0.0000% | 1933 | OK | 2007-07-23 10:12:15.605605 |
1098629 | 2.0028% | 1659 | OK | 2007-07-23 02:47:11.516359 |
3584940 | 0.0000% | 1550 | OK | 2007-07-22 22:28:14.430673 |
1156403 | 1.3131% | 1193 | OK | 2007-07-22 19:08:55.244399 |
1160705 | 1.2714% | 75 | OK | 2007-07-22 08:44:27.694574 |
1160658 | 1.2719% | 28 | OK | 2007-07-22 02:04:22.83462 |
3598660 | 0.0000% | 0 | OK | 2007-07-19 14:59:38.477502 |
UPDATE: This entry has been repeatedly targeted by spammers, so I've turned on comment screening. You can still make a comment, but it won't appear until I approve it.