ICFP Programming Contest

The 11th ICFP Programming Contest is underway in less than 48 hours. Last year my team took 2nd place. Unfortunately a number of things are preventing a repeat performance, with the number one problem being that I am flying over to China for RoboCup when the contest begins. Bruce and Carl are, however, forming their own team up in the UK where they'll hopefully win it for us. There's also the UCT team of Max, Keegan, Julian, Richard and Timothy who's sole aim is to pwn Bruce and Carl.

If you haven't heard of the ICFP Contest before, it's an annual contest run alongside the International Conference of Functional Programming with the aim to provide a language neutral programming problem and recognise the winning teams' languages. It's a 72 hour long marathon contest with almost no rules (anyone can compete, etc.). Last year's problem was to "implement a 2-stage virtual machine that executes a DNA-like string to produce an image. Then, given an input string for this machine, find a prefix that when added to this string yields an image as close as possible to the given target image." This year's organisers all have PhD's in computer graphics...me suspects something!

In closing I'd like to say that I very much disagree with the rule limiting teams to five people. It is almost always true in these contests that having more than five people is actually worse so that removes the reasoning of making it fair for all. The reason we had such a large team last year was to have a more enjoyable time together and it truly was a most enjoyable experience. It brought ten of the top students at our university together to work on a well-defined goal over just 3 days. It was awesome! If this rule continues I fear we have lost the opportunity for a repeat of that amazing experience. Competing for fun without submitting is not an option as that removes...well, everything! Consider this as my plea to the organisers of the 2009 contest to relax this restriction.

SACO Online Contest

The second training camp for the South African IOI squad is coming up in a weeks time on the weekend of 2-4 May. This will be the final round of training and competition before we select the team for the IOI in Egypt.

As we've done in the past, we are continuing to offer the problems in an online contest that will be run simultaneously. You are all welcome to participate. The contest page and place to register is:

https://olympiad.cs.uct.ac.za:8082/contests/camp2-2008/

The times are:

• Friday 2 May at 13:00 to 18:00 SAST
• Sunday 4 May at 08:30 to 13:30 SAST

Languages accepted are C/C++, Pascal, Java, Python and Haskell. If you have any clarification requests or other queries, email them to online-contest@olympiad.cs.uct.ac.za.

And while I'm at it, there are a couple other really good contests coming up soon. The IPSC on 24 May is a team of 3 contest with no limits on computers used or programming language. The problems are typically very mathematical and some rather interesting and unusual problems creep in.

The there's the ICFP Contest. Yes, that's the one we came 2nd in last year! Things weren't looking so hot for this one as there was a long period of silence as to what was happening with the contest this year. We were concerned in particular because we had offered to host and received positive feedback initially, but then the organisers went mute and we never heard from them. Anyway, it's being hosted by John Reppy (University of Chicago) and Tim Sheard (Portland State University) this year (from here), although we don't yet have the dates. As soon as we have them we will know who's available for our team. Here's hoping it's a smashing contest this year! If you look around you'll see that John hosted the 2000 and Tim the 2002 ICFP Contests...interesting!

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

ICFP Results

The results of the Tenth Interstellar Contest on Fuun Programming were announced this afternoon. If you've been wondering where I've been the last couple of days, I'm in Freiburg attending the ICFP Conference. Yes, we were invited after being told we had "won a prize" the week after the contest.

We came in a very close 2nd with 84.92%, beaten only by Team Smartass who took top honours yet again (they won last year) with 90.22%. Team Smartass is a team of four Googlers from the Mountain View office, with an ex-South African (Daniel Wright). And surprisingly, the only member of their team to come to the conference was him! So three of the four prize winners that are here are South African. A quote from the contest report sums it all up:

Incidentally, Africa was the continent with the highest percentage of winning teams.

Go Africa!! There was also another South African team, which I'm curious to find out who they were. There's a graph in the report showing the scores of the top six teams over the 72 hours and we were in the lead until the very last hour when Smartass made a big jump just leaping past us.

The organisers were concerned about a brute-force approcach of drawing the scene manually doing too well. Well, they were correct to be concerned as the third place team and judges prize went to Celestial Dire Badger (Jed Davis on his own) who got 75.59% using this strategy.

The top 15 scores:

Place	Score	Survival chance	Team name
1	178246	90.22%	Team Smartass
2	224623	84.92%	United Coding Team
3	293898	75.59%	Celestial Dire Badger
4	321617	71.52%	ryba
5	358246	65.98%	PurelyFunctionalInfrastructure
6	453744	51.32%	jabber-ru
7	498781	44.66%	Begot
8	514121	42.47%	Basically Awesome
9	543163	38.45%	SwtPl
10	608964	30.07%	shinh
11	682894	22.07%	SzM
12	819614	11.34%	kuma-
13	862213	8.99%	Unknown?
14	865556	8.83%	voyo
15	872788	8.47%	kokorush

So the judges have declared that:

Perl is a fine tool for many applications

Keep your eyes open for a post on our tools and how we morphed Endo! There is just one thing we'd like to ask all the keen Endo hackers out there that is not answered by the contest report. Anyone have a blinking clue as to what the "crucial hint to solving the contest sneakily hidden in the Major Imp stories" is?

ICFP Contest Losing It's Functional Nature?

When I first participated in the ICFP Contest last year I was expecting an AI problem from looking at previous years. I was attracted to the contest because of this. My team had won the Java Challenge (renamed the Parallel Challenge for that year) in the ACM ICPC the previous year, so I thought it would be nice to try out the longer version.

So I got a team together telling them to expect some AI. None of us knew any functional programming and although we could see from previous years that it was beneficial we weren't taking it seriously. We get the problem and boom, "code a VM". Ok, where's the AI? We immediately jumped in with C++ and even then we initially had efficiency problems, although those were quickly rectified. Everyone complained afterwards that functional languages lost out there.

Then the mini problems started revealing themselves one by one. I will admit we didn't get very far with them (mainly due to factors out of our control and a lack of interest from some who expected an AI problem). Some of the problems were slightly functional in nature, but I still don't think there was any major benefit in using a functional language.

After the lack of AI in 2006, I was able to gather some people into the team that previously wouldn't participate because of the AI nature in the past. This year we were far more prepared for a non-AI problem. I also got a larger team together after 2006 being multiple small problems. Once again, none of were functional programming gurus (although by now I have at least know a bit of Haskell).

We get the problem this year and once again it starts off with a VM (DNA->RNA). With most of our team being C++ fanatics, we quickly got it running and even discovered ropes pretty quickly. From reading other peoples comments, the functional languages suffered with the VM. Although it was possible to get an efficient VM, the sub-linear data structures appear to be fairly uncommon. Yes, they're not that common in C++ either, but the functional teams sure seemed to rush over to C++.

Then there were the problems once you've passed the VM. Our team used Perl, Python and a bit of Bash to glue the scripts together. I don't see how a functional language could have been beneficial in any way. Even if someone does find a way of using a functional language, I sure would like to see how functional languages can do a better job.

The idea of the ICFP Contest is to promote functional programming. Or at least, that used to be one of its goals. Has this emphasis changed? There sure still seem to be many teams whose primary tools are functional languages. Last year, none of the top three teams nominated a functional language as their primary tool. I'm confident the same will occur this year.

I certainly do not mean for this to be an attack on the contest. I still love it. This is just something that has been on my mind making me wonder what the connection to the ICFP is. Is it possible that the functional programming community can learn from the lack of results from functional teams and make the functional languages more powerful? Maybe that's the aim?

ICFP: How We Reached the Top 15

The United Coding Team once again tackled the ICFP Contest this year. This time we managed to hit the top 15. How did we manage that? Well, read on I say!

The team this year consisted of the following members, all students at the University of Cape Town, South Africa:

• Richard Baxter
• Carl Hultquist
  
• Marco Gallotta
  
• James Gray
• Alexander Karpul
  
• Julian Kenwood
  
• Bertus Labuschagne
  
• Bruce Merry
  
• Max Rabkin
• Harry Wiggins

and two team managers:

• Hayley McIntosh
• Ian Saunder

The problem of this year's ICFP Contest started off with us receiving Endo's DNA, which was 7MB. The DNA was interpreted as a sequence of patterns, which searched for some DNA, and templates, which described how to manipulate the DNA at that point. Some of the DNA caused RNA to spew out. The RNA was then interpreted as drawing commands to draw an image. Endo's original DNA sequence created this image:


Our task was to reverse engineer the DNA and poke away by coming up with a prefix to prepend to Endo's DNA to morph him to stand a better chance of survival on Earth, where he has crashed. We were given a target image to aim for (below) and we were scored by the number of pixels we got correct and the length of our prefix, with a shorter prefix being better.


Being in South Africa, we fitted nicely into the same timezone as the organisers so we started at noon on Friday. We took about an hour to read through the problem statement to decipher the meaning of the DNA. We then split up the tasks of writing a DNA->RNA and RNA->image converter.

Carl, Alex, Harry and I worked on the DNA converter while Bruce and James did the RNA->Image converter, both in C++. The RNA->image converter didn't take too long, but the DNA->RNA converter had efficiency issues. We got a working version by about 17:00, but it was horrendously slow compared for what we needed. Max joined us after work and quickly gave us the idea of ropes. None of us had used them before though so we had to read up on them to decide if they would be useful. We went for them in the end, but they caused us major headaches. The rope substr function defaults to taking only one character from the string instead of the usual running to the end.

After working on all these annoying bugs we finally got it working some time around 20:00 or so. We then used the prefix given to us in the problem text which ran some self checks. Unfortunately one of them failed and it was back to debugging. The bug appeared to be related to ropes, since our strings version passed all the self checks. It was also odd that it worked with compiler optimisations, but not without them enabled. While Carl worked on debugging, Bruce worked on some OpenGL code to display the image as it was being generated so we could see any hidden messages that were covered by later layers.

With the OpenGL code we discovered a hidden prefix which when run gave us a field repair guide which led us to a catalogue page and a prefix to rise the sun. Julien and Richard spent some time trying to figure out how to use the catalogue prefix to view other pages, but only ended up at invalid pages. When Bruce had a moment of free time we gave it to him and he solved it very quickly. We replaced the number in the prefix with the page number we needed. Page 1337 gave us the catalogue index page. This opened up a whole bunch of new pages which both helped us understand the DNA and gave us new problems to solve.

We did a brute force search on the page number to see if we could find any undocumented pages. Of note were pages 100 and 1024. We searched up to about 20000 pages, but didn't find much else. The stegonography hint gave us the number 9546 in the ET page, although we never figured out a use for it. The Virus Alert page we noticed was Wingdings, but we didn't find a use for the message. The Intergalactic Character Set pointed us to ebcdic. The Undocumented RNA helped us print a stack trace of function calls.

One of the pages extracted was a Gene Table. It said "Page 1 of 14" on the top. We got the remaining 13 pages by setting the value AAA_geneTablePageNr to the one we wanted. We also later discovered from the ImpDocs that printGeneTable took a boolean parameter that when set to true ran integrity checks. This proved valuable later on when we got to fixing functions in the various ways. We got some of our team, including team managers, to transcribe the gene table. From this we wrote scripts to call a function in a human readable format. This was the start of our scripting language that generated a prefix.

Some of the function calls yielded further help pages and more problems to solve. We noticed that the contest-xxxx pages had some yellow letters (ICFP's). When combined these gave us another prefix. The Encodings page helped us search for strings and polygons in the DNA. Some of these strings were helpful, while most of them we had already seen. The Fuun Security Features page was easily noticed to be encrypted with rot13.

We extracted the hitMeWithAClueStick function from the DNA. Removing the C's and trying different widths gave us the message "PORTABLE NETWORK GRAPHICS FOLLOWS". We then noticed the data was split into three sections by P's. The second chunk gave us a PNG image, which told us that an audible voice followed and we then interpreted the remaining segment as an MP3, which read out yet another prefix. This gave us the Beautiful Numbers page, which didn't get us anything extra since we had already found page 496 by brute force.

All the above was about sub-problems in the contest. However, none of this helps morph poor Endo into a cow to save him. At least, not directly. Most of the sub-problems yielded clues which in turn helped us find the right DNA to poke into Endo's DNA, call functions and do other interesting things to it. These all helped us morph the source image into the target image. Since we've been asked by the organisers not to reveal our score I think this is as far as I should go.

Hopefully what I have said should be sufficient for those that did not get very far to poke around and at least get some satisfaction from the problem. I can imagine that many of you spent the entire weekend and got nowhere.

Has Endo been saved? More importantly, have we saved Endo? We have to wait until the International Conference on Funtional Programming in October where the results will be announced.

Post mortems from other teams:

• United Coding Team (2nd)
• Celestial Dire Badger (3rd)
  
• ryba (more pages) (4th)
• Purely Functional Infrastuructre (5th)
• jabber-ru (6th)
• Begot (7th)
• SwtPl (9th)
  
• shinh (10th)
• SzM (11th)
  
• kuma- (12th)
• Unknown? (13th)
  
• kokorush (15th)
  
• The Caml Riders (17th)
• The Corn Worf Strategy (28th)
  
• fun (31st)
• solo r6 (32nd)
  
• jsnell (45th)
• /void/ im Kopf der Mensch (48th)
  
• LazyBottoms (more) (56th)
• efg (64th)
  
• on byte nirvana (more pages) (79th)
• tnt (80th)
  
• cashto (84th)
• DylanHackers (88th)
• cultboundvariable (98th)
  
• Side-Effects (more) (116th)
• interfacers (121st)
• The Great Indian Rope Trick (127th)
  
• Raptors (354th)

Other writeups I haven't been able to link to a team:

• Programming contest postmortem
• ICFP '07 Contest
• ICFP with haskell/python ...ocaml??
• Python to the rescue: ICFP contest 2007
• Russian pages translated
  
• clfp
• RNA Debugger
  
• ICFP Programming Contest/Teams 2007
  
• Not Programming for the ICFP 2007 Programming Contest
• Diffing Endo
  
• ICFP '07 Post-Mortem
  

Top 15 in ICFP Contest

The ICFP Contest ended just four hours ago. I'm so excited to tell you that we, the United Coding Team, have found ourselves somewhere in the top 15 out of 869 teams. We suspect that we're reasonably high up within the top 15 as well from looking at positions 16+ on the scoreboard, although we've been asked to keep our score private until the final standings are announced at the ICFP (a conference) during 1-3 October.

I am extremely exhausted right now and it's time to catch up on some much needed sleep. Once I've regained some energy I will post some details of how we tackled the problem. In the meantime, here are a couple of pictures of our team (unfortunately with me being the photographer I'm not in any of them).

Saving Endo!

Over the past 47 hours we have been transforming this image:


into this image:


This year's ICFP task is to save the alien Endo who has crash landed on Earth by morphing him to stand a better chance of survival in this unfamiliar environment. We are given his DNA which for the purposes of the problem draws the image on top. Our task is to prepend DNA to get the bottom image. The full problem description can be read here.

On Friday we jumped into the top 20 and have remained their since. Other than that I shall refrain from discussing our results as the contest is still underway for another 25 hours.

Go United Coding Team!

PS: Thanks Bruce, without you we would still be interpreting the meaning of the DNA. :)

ICFP Contest Tomorrow

The ICFP Contest is finally underway tomorrow at noon and continues non-stop through till Monday noon. That's 72 hours of coding goodness! Sweet!!

Currently we're sitting on a total team size of 19. I think that's a record. :P We have the 4th ranked TopCoder, 6 IOI participants, 2 IMO participants and 4 ACM world finalists on our team. Not to mention the circus guy whose primary form of transportation is a unicyle and some silly man who likes his hair green.

Unfortunately there's a scheduled power cut on Saturday from 11:00-13:00, although we're not sure if we'll be affected.

One of the contest organisers has a blog in which he's been going on about this story about a spam message they received from which they've decrypted and posted several pictures. They are obviously connected to the contest, since recent postings have mentioned that they're getting close to cracking its secrets and it looks like they will "crack" it when the contest begins.

If I get a break I might be posting brief updates during the contest. So keep your eyes glued!

Upcoming: ICFP Contest 2007

It's that time of the year again. Time for the ICFP Contest. Last year Carnegie Mellon set an amazing problem where a 1.8MB file ran on virtual machines we had to write and self-extracted another 15MB source file. The new file ran on the same virtual machine and yielded a mini Linux kernel with user accounts you had to hack into to retrieve the problems to solve. Everything - the problems, compilers, evaluators - came out of that tiny 1.8MB file.

This year our team returns to the scene. This time strengthened with some stronger team members. And the hope that our network will be running for more than 50% of the time. Our team is 100% from the University of Cape Town (UCT), South Africa. Two of our members will be joining in from California though, but still from UCT nonetheless. Our team in alphabetical order to reduce favouritism:

1. Richard Baxter
2. Charles Bradshaw
   
3. Jason Brownbridge
4. Christopher de Kadt
   
5. Carl Hultquist
   
6. Marco Gallotta
7. James Gray
8. Alexander Karpul
   
9. Julian Kenwood
   
10. Bertus Labuschagne
    
11. Kosta Masalov
12. Bruce Merry
    
13. Max Rabkin
14. James Saunders
    
15. Andre Scholtz
16. Ben Steenhuisen
    
17. Harry Wiggins

The first thing you will probably notice is that our team is rather large. One of the nice things about this contest is the unlimited team size. We thought we'd try take advantage of that this year. It will be interesting to see if the advantage of more brains overcomes the disadvantage of managing a large team over such a short time. To reduce the management tasks the team has to worry about we have two dedicated managers - Hayley McIntosh and Ian Saunder.

The only thing that changes this year is it is organised by Utrecht University and of course the problem will be different. It runs from Friday 20 to Monday 23 July (72 hours). One of the teams put together a countdown, as well as one for the more geeky.

Here's hoping the United Coding Team whips many teams this year!

Programming Contests

One of my biggest interests is programming contests. The number these days is ever increasing and more importantly, so is the diversity. In this post I aim to identify and discuss some of the major contests and pick out the parts I enjoy most.

The first international contest I competed in (in 2004) was the International Olympiad in Informatics (IOI). While it is only for high school students, it has a very different structure to any other contest. It is an individual contest consisting of two rounds of three problems with five hours per round. Part marks are assigned based on correctness and efficiency and marks are only returned at the end of each round. I like the split over two rounds, which allows for one to have a bad day and come back on the other day. I also like the way it squeezes you on efficiency, which often contests with a single yes/no response cannot afford. The South African team is picked from the medalists of the South African Computer Olympiad (SACO).

By far the most prestigious contest is the ACM International Collegiate Programming Contest (ICPC), for which I competed in the 2004 and 2005 regionals and the 2005 and 2006 world finals. As the name suggests it is only open to university students. Teams of three compete against one another by solving as many of the ten problems in five hours, with a single PC per team. I like the teamwork that is forced upon teams with only one PC, which also requires very good planning/management skills. The problems are usually of the best quality and the types of problems vary, which allows for teams with mixed skills such as including mathematicians in the team. In this and many other contests, you get the result of a submission back immediately. I must say I am a little against this as it makes teams submit without testing much at all. You also get no part marks which results in very close results, often split by time penalties.

The Internet Problem Solving Contest (IPSC) is similar in structure to the ACM ICPC. The crucial difference is that it is an online event without any specific locations. The contest is open to anyone and everyone and not restricted to students. It also allows for any programming languages and hardware/software resources. These differences all allow for a much larger number of contestants. There are generally about 12 problems to solve in the five hours, each with an easy (1 point) and difficult (2 points) level. Teams of three are competing against one another. The problems are typically far more mathematically inclined than the ICPC, although the problems vary rather drastically between years. This year they even included a simple image processing problem. I really enjoy the problems in this contest and that is the major factor towards this being my second favourite contest.

Another contest which many compete in is the TopCoder. They run contests about once a week - online, as with the IPSC. I must confess that I dislike the format so much that I have only ever competed twice. The short duration of three problems in about 75 minutes really kills it for me. I don't like solving problems so quickly. I like having to think about them. That's why you'll see as you read on that I have a preference for the marathon-style contests. All the top competitors define their own macros to squeeze out an extra few minutes. I'm sorry, but as much as it might prove fun to some people, I just cannot pull myself take part in it again. The Google Code Jam follows a very similar structure and runs on the TopCoder platform.

In South Africa we have a national contest which started in 2005 called the Standard Bank IT Challenge. This is another one I dislike, but for different reasons. However, it has some interesting new ideas. The first round (heats) are four hours with five problems. However, two of the problems are related and you only receive the second part after solving the first part. This adds an interesting dynamic in that you have to be cautious not to leave the problem with two parts too late, although it's typically one of the more difficult problems which makes things very interesting. You are also in teams of four for this one, which adds more to the team aspect. The finals consist of six problems with six hours to solve them in. This time there are two problems with two parts. One of those is very different to all the others as it's an interactive problem. In the three years the contest has run the interactive problem has been the most interesting: foxes and hounds, maze game and suicide chess. The other problems are all mostly simulating some process, with very picky and vague problem descriptions. It's the problems and the poor judging that kills the contest for me. The only reason I compete is that it's a national contest and the prizes are very nice.

My favourite contest to date is the ICFP Programming Contest. It's a 72 hour marathon contest with almost no limits whatsoever. Anyone can participate, teams can be of any size and can even be spread across the world (as will our team be this year). There are no restrictions on programming languages, software or hardware used. There are in fact no restrictions I can think of other than the 72 hours you are given and that they asked us nicely last year not to reverse engineer the platform provided. I competed for the first time last year with a team of seven students. The 72 hour time frame is just perfect I think as it's long enough that you can concentrate on the problem for the full time without getting the feeling you're giving your life up to the contest like with semester-long contests. I also really enjoy having no limit on team size as it allows you to get some people coming in to help on parts they're experts at and then go back to their normal lives while the contest continues. This makes it reasonable to get people not willing to give up much of their time. You can also very easily get advice from people, which takes up very little of their time. Even if the person is not in the country, you can still contact them.

Just last week while in Zurich I was told about the Extreme Challenge. This is another marathon contest, but 24 hours this time. The teams are restricted to three and you aren't allowed access to any external resources, including the Internet. The finals are held in Budapest, Hungary. You are given a single power cord and a desk and you bring all your own hardware - and you can bring as much of it and whatever you like! It sounds like a very interesting contest, although I still think I'd prefer the ICFP due to the lack of restrictions. The problems seem very interesting though and they are very polished, which is seldom the case. I will definitely aim to try it out next year as I like these marathon contests. Until then, I can only go on what others have told me and that is that is is an excellent contest.

For those of you who haven't heard, there are no Code Jams this year. After four of them last year, the organisers are a bit exhausted and needed a break. With this break, some of the coaches discussed the possibility at the Google ACM meeting last week of Google starting a new, very different contest. The idea spawned from the Extreme Challenge, while they though extending it to 72 hours would be more exciting. The idea behind it is that the Code Jam is so short that it doesn't necessarily identify good software engineers, but rather those who can very quickly solve small problems. With this longer contest, planning is required as well as team work, which should provide a better of software engineering skills. Details are still very rough, but the idea definitely caught their interest. I think it's a great idea! So who knows, we might just have started a new Google contest!! :)

Those are just a few contests I have competed in. If you have another favourite, I'd love to hear about it. As I said, I only recently found out about the Extreme Challenge and it sounds like one I should have heard of long ago. Also, if you have anything to add about my analysis of these contests I'd love to here them too. This is one thing I'd really like to get your feedback on.