Wednesday, October 3, 2007

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
22462384.9187%23673 OK2007-07-23 11:56:28.189071
25408881.1252%21068 OK2007-07-23 10:58:10.198941
26911579.0847%21285 OK2007-07-23 08:53:27.874742
27018178.9376%19781 OK2007-07-23 07:55:09.512691
38747161.4815%17851 OK2007-07-23 06:29:08.842547
41666056.9793%13870 OK2007-07-23 03:48:30.984398
44394152.8057%12891 OK2007-07-23 03:36:01.053116
45131951.6876%12509 OK2007-07-23 02:28:27.616679
53658139.3428%11551 OK2007-07-23 00:07:32.848233
65768024.6242%19340 OK2007-07-22 23:28:13.925382
65094325.3378%7783OK2007-07-22 18:19:45.066483
9547165.2172% 2006OK2007-07-22 13:41:59.578933
9820124.3960% 1792OK2007-07-22 04:56:01.66359
1026470 3.2916% 1160OK2007-07-22 04:29:04.920747
1026507 3.2908% 1197OK2007-07-22 04:06:09.381258
2586153 0.0000% 1553OK2007-07-22 03:22:03.213929
1154651 1.3305% 441 OK2007-07-22 02:23:20.692856
1155452 1.3225% 242 OK2007-07-22 00:17:33.173277
Error Error Error Zip corrupted or no Zip.2007-07-22 00:16: 36.408618
1160658 1.2719% 28OK2007-07-20 22:11:07.7945
3583008 0.0000% 28OK2007-07-20 21:43:02.3871
3598660 0.0000% 0 OK2007-07-19 14:59:28.351108


  1. Congratulations! We only got 9th place (SwtPl) but I was able to produce a perfect prefix afterwards, so I know what you had to solve. We were about 24 hours behind you during the contest having the first prefix that got us top 15 on Sunday morning, 4 am, (daylight mode+cargo box, actually we started with patching the cargo box color), and started to reposition the image parts at Sunday evening. I found out about the palindromed clouds only few days after the contest was over.

    For your information: The mu and the cow's tail were encrypted, one with the password from the sticky note and one with the number hidden in the E.T. image. The speech bubble was simply missing and its gradient had also to be carefully positioned. And of course the grass had to be repositioned as mentioned in Johan Jeuring's blog.

    In the motherduck polygon one number was wrong (they didn't sum up to zero) and this made everything drawn afterwards to be moved by two pixels, which broke the anti-compressant. But I found this also only two days after the contest.

  2. Yes, I've heard a lot about your perfect prefix. There certainly was a lot embedded in that DNA and from speaking with Johan they even left out many things such as those long palindromes he posted about on his blog. At least it prevented anyone from finishing within the 72 hours as was the case last year. I'd love to have had two weeks off to investigate the problem further. :D

    Thanks for the tips!

  3. Thanks for posting the details! I didn't enter myself, but I spent far too much time after the contest was over digging through everything (and eventually gave up when I couldn't find the Hamming codes to repair anything with), and have been eagerly awaiting this sequel post. Congrats!