How did this happen?

Concerning this matter, the organizers definitely intended that people have to reverse-engineer the alien genome and solve their little puzzles; earlier I'd wondered if they'd deliberately designed the problem to make the image-processing approach feasible, but this appears not to have been the case.

Now, that kind of strategy had certainly occurred to them, and indeed they deliberately did not outright forbid it, but they did seek to make it highly challenging at best. And they tested all this on two separate batches of undergrad guinea pigs.

Clearly, then, my relative success is a sign that something went horribly wrong.

My theory: the organizers were thinking of the DNA as just a platform on which to build some kind of sequential random-access machine, on which conventional algorithms could then be run; and the RNA as a mostly opaque means to an end. (In fact, now that the official report has been released, evidence of this worldview can be seen.)


But in fact the RNA is all but opaque: where the DNA can use all manner of obfuscation and even outright encryption to hide its secrets, the RNA has no control flow, and is limited in what it can do with the graphics context.

Then, the genome's output RNA almost invites editing — pretty much everything in the image, including the “anticompressant” moiré pattern applied at the very end, is drawn in its own canvas and composed down, recursively where appropriate. Deleting or extracting items is thus relatively easy; and there's no need to guess at what each piece does, because it's immediately visible. (Okay, maybe not the anticompressant so much, but once you know it's there....)


As for the DNA, certainly it would be difficult indeed to outdo the organizers at creating an operating system and libraries for such a strange substrate in the time provided, let alone port a useful image decompressor to it, and then you're still stuck with an image that's 240kB in PNG. So went the organizers' reasoning, anyway. Thus, surely teams would abandon such foolish ideas for the simpler alternative of dealing with the existing genome, puzzles and encryption and damaged bits and all. Right?

But what if I don't want general computation? Let's say I want a very specific computation: Given a dictionary (list of words) and a list of numeric indices into the dictionary, return the concatenation of the corresponding words. The DNA machine can execute this operation directly: just put the dictionary words into the data section, capture them with sub-patterned skips, and encode the list of indices as a template. Or, in other words: copy and paste.

And that is data compression. Mostly because it can be iterated; I've prepared a DNA sequence that may be instructive. Obviously not every piece of DNA will be quite that repetitive, but it can get pretty good results, especially for something so simplistic — 90:1 for my winning prefix — and I didn't have to do anything remotely like building an entire computational world to get there.

Once practical inexpensive compression becomes available, the picture changes a bit (so to speak). No longer does it matter that the RNA commands are so long — a deliberate countermeasure to image reconstruction — nor that lengthy runs of IIIPIIIIIP are needed to move the point around, and similarly for color. Nor even is subtlety in the use of flood-fill and such to keep the RNA size down necessarily still a win; it may even be a net loss compared to, say, just drawing lots of identical 3x3 boxes.

The Proximate Cause

There is, of course, a specific event that got me to actually create this thing. That would be ICFP'07, or rather the 2007 ACM SIGPLAN International Conference on Functional Programming. It was last week. And, every year since 1998, there's been a programming competition associate with it held back in July or so, with winners announced (and the contest organizers' experience reported on) at the conference.

I attended the conference, as I (as team Celestial Dire Badger) had won the Judges' Prize (for an uncommonly “creative” solution) in the contest, and — as even I didn't discover until last Tuesday when the announcements were made — also placed third out of, oh, 357 teams. As a team of one person, while for example the #1 team had four and the #2 twelve.

So, I don't know, maybe I'm famous now or something? I mean, I was declared to be an “extremely cool hacker” to the applause of a few hundred members of the functional programming community, which I guess isn't quite the same as being entirely unknown. Or at least someone might be wanting to read what I have to say about that thing. And besides, everyone else is doing it.

In that case: I already have a chronological writeup of the contest weekend itself, but I have a bit more perspective now that I know more about the making of the contest... but more on that later.


Useful background for random people wandering in: if the contest website doesn't have enough info lying around, then the beginning of the problem statement (PDF) should be helpful in determining what on earth I'm talking about.