ICFP: How We Came 2nd

I've been posting a lot about the ICFP Contest and how we did this year. Just recently the results were announced, placing us in second position behind last years winners Team Smartass. Up until then we kept most of how we did to ourselves to prevent the public from guessing where we came. However, that's all public knowledge now and so what follows is a continuation of this post describing how we tried to save Endo.

The tools formed the most important part of our success. I briefly touched on our DNA->RNA and RNA->image simulators in the previous post. Extras included in our DNA->RNA simulator include translating the DNA into a more readable form as well as several further hacks which helped us better understand the DNA sequence. Extras included in our RNA->image converter include hacking the default image to white to reveal hidden black-on-black messages, post-processing to make the images printer-friendly (we're al-cheapo in SA :-P) and some OpenGL code to render the image as it's being drawn.

Then we had plenty debugging tools to reverse engineer the DNA. Each function spews out a unique RNA marker upon entering and CFPICFP upon returning (Undocumented RNA). With this we were able to create a stack trace. We had tools to extract the code from a function, to extract a page from the Repair Guide. There was a tool to generate the prefix to call a function. It's worth noting here that we had a table mapping from function name to offset and size so we could call by name making things go a lot faster. We even had a tool to investigate the DNA between consecutive functions which found odd things such as overlapping functions, a fairly constant gap with some really large gaps.

We wrote a common library that covered many things including quoting, unquoting, text and integer encoding, integer decoding. It also includes higher level functions to process the symbol table, interpret symbolic addresses and generate DNA to call the adapter, copy pieces of DNA around, make patterns and templates and so on.

We had tools to generate prefixes. We had one that would call a function using the adapter, encoding parameters in several formats. Another was used to patch the DNA by overwriting selected portions. Then we had a tool that would either overwrite a function with another one of the same size or replace it with a stub to call another function. We used this extensively to nuke functions by replacing them with no-op code (e.g. init function), allowing us to easily erase objects such as Endo! Related to that, we had another tool that would search a section of DNA and replace all calls to another function with a third. This was useful in cases where we wanted to redirect from within certain functions only as well as a debugging tool to poke at function parameters. We had tools to encrypt and decrypt, but since we didn't figure it out in time it wasn't useful. There was a tool that output DNA to reverse a piece of DNA and a colour mixer to generate a required colour.

The DNA->RNA and RNA->image converters were written in C++. All the tools mentioned above were written mostly in Perl with a little Python as well. Since the tools written in Perl were the most fundamental in our success, that was the language we chose to nominate.

All these tools are great, but how did we morph Endo? Since we had a mash of Perl and Python scripts generating bits of the prefix, we chose middle ground in Bash as the glue. We wrote simple Bash functions as wrappers around the Perl and Python tools to make the script very easy to work with. There was a lot of crap that went into it so the more concise the better.

We started off with nuking Endo and several other objects that weren't in the target image. We then figured out how to do translations to get the different objects into the correct positions. It was very tedious, but that's where having a large team of ten was a big advantage. Bertus spent most of the time placing the objects, with help from others at times of course. We did the ducks first, then the cow, the caravan and so on. The function that drew the middle spot on the cow was broken and needed an error correcting code (I can't remember where this came from though!). One problem we had was that there was an anti-compressant function which drew hatching lines that was getting called before our add-ons were being drawn. This was losing us lots of points so we scurried to figure it out. Due to a couple silly misunderstandings this took us unnecessarily long to work out, but we eventually got it.

We rotated the windmill by calling setGlobalPolarRotation. We changed the colour of the cargo box by hacking the colours. To draw the whale we first nuked the ufo-with-smoke function and poked in the ufo-cup function to get it to spew out RNA codes to rotate it by 180 degrees. This was placed on top of a layer of water which was clipped with the correct shape. The scenario function was patched at the offset where the whale was located to translate the whale to the correct location. We nuked the crater in which the dead whale was lying. The motherduck-with-chicks was buggy and the anti-compressant wouldn't work on it or anything drawn after it. We couldnt' fix this so we drew it last. The lone duckling is drawn by enabling ducksShown, but to get it to the correct location required hacking of the DNA. The goldFishLeft and goldFishRight functions were swapped which got most of the fish correct. The colour functions for the flowers were swapped to get the correct colours, while the cow's flower required some nasty hacks to get working.

The sun required a little hacking to get working. After some investigation we noticed that the sunflower function had the same length as the sun function. When we noticed this we decided to XOR the sunflower and flower functions, replacing the sun function with the resulting data. Setting the weather value to 3 and calling sky-day-bodies caused the sun to be correctly rendered. To get the correct colour we had to nuke the colour bucket in the sun function and replace it with our own. We only found the spirograph help screen after the contest so we couldn't finish the sun completely.

Getting the clouds to render correctly was also a pain. With the palindromes hint, we noticed that the function name duolc was actually the reverse of cloud. With a little investigation we noticed the contents were similar, but in reverse. We then dumped the reverse of the data in duolc into the cloud function and that fixed the cloud function! Using some tracing data we noticed the function took a parameter, which we discovered was a scaling factor.

Setting the hillsEnabled value to true drew the hills, however, it was infected with a virus causing the rest of the image to be buggered. When running it through our trace tool we discovered that it output an invalid RNA command. We tried patching the RNA output to replace this with various drawing RNA, and found that emptyBucket worked. We then found the bogus RNA in the raw DNA, triple-quoted, and patched it. The shape of the hills were slightly off. Fixing this was simply a matter of finding the correct parameters to draw the correct polynomials, however, we never got around to doing this in time.

There were still a few things we never quite got by the end of the 72 hours. Some of the things we solved after the contest, but those don't count. The spirograph in the sun we solved afterwards. The bit of the left cloud drawn over the windmill we solved afterwards. The shape of the hills we know how to solve, but haven't attempted to fix them. The weeds are solved by setting the rng seed to 8128, the fourth perfect number, which we found out from the contest report. We haven't figured out how to fix the ducks from breaking the anti-compressant. An explanation of how to move the grass is in the contest report, but it involves quite a lot of effort. The whale spout is displayed when viewing an invalid gene table page.

The fish are moved into place by modifying the structure defined in the goldenFish_adaptation data. The speech bubble was apparently the only thing that cannot be drawn by embedded code and had to be approximated by a polygon. The mu inside the bubble was one of the characters in the character set, but needed some repairing using a hint drawn behind the previous contest pages. The cow's tail was infected by a virus it's possible it could be fixed in a similar manner to the hills, however, we never got to trying this out. There were another couple small things such as the "Endo has morphed! text and the whale's face, but these made little difference.

This was our final submission:

And this is a diff between our final image and the target:

Our history of submissions:

Risk	Survival Chance	Prefix length	Message	Submit time
224623	84.9187%	23673	OK	2007-07-23 11:56:28.189071
254088	81.1252%	21068	OK	2007-07-23 10:58:10.198941
269115	79.0847%	21285	OK	2007-07-23 08:53:27.874742
270181	78.9376%	19781	OK	2007-07-23 07:55:09.512691
387471	61.4815%	17851	OK	2007-07-23 06:29:08.842547
416660	56.9793%	13870	OK	2007-07-23 03:48:30.984398
443941	52.8057%	12891	OK	2007-07-23 03:36:01.053116
451319	51.6876%	12509	OK	2007-07-23 02:28:27.616679
536581	39.3428%	11551	OK	2007-07-23 00:07:32.848233
657680	24.6242%	19340	OK	2007-07-22 23:28:13.925382
650943	25.3378%	7783	OK	2007-07-22 18:19:45.066483
954716	5.2172%	2006	OK	2007-07-22 13:41:59.578933
982012	4.3960%	1792	OK	2007-07-22 04:56:01.66359
1026470	3.2916%	1160	OK	2007-07-22 04:29:04.920747
1026507	3.2908%	1197	OK	2007-07-22 04:06:09.381258
2586153	0.0000%	1553	OK	2007-07-22 03:22:03.213929
1154651	1.3305%	441	OK	2007-07-22 02:23:20.692856
1155452	1.3225%	242	OK	2007-07-22 00:17:33.173277
Error	Error	Error	Zip corrupted or no Zip.	2007-07-22 00:16: 36.408618
1160658	1.2719%	28	OK	2007-07-20 22:11:07.7945
3583008	0.0000%	28	OK	2007-07-20 21:43:02.3871
3598660	0.0000%	0	OK	2007-07-19 14:59:28.351108