blog.poucet.org Rotating Header Image

June, 2008:

ICFP Contest 2008

For those that are unaware, in exactly one month the 3 day ICFP contest will be held again. This contest has been held for 10 years already and has seen a steady increase in participants, especially in the last two years. Curiously, this ties in with my previous post as it seems that this contest has reached critical mass in 2006 to become really big in 2007.

For those wondering what the contest is about, it is hard to specify a specific challenge since the contest is so different each year.  The idea is that a problem gets put online and that you have 72 hours to solve it. Each year, a different university designs the problem.  Usually this involves one or more professors, a bunch of phd-students and a plethora of master students slaving away for 6 months trying to make sure the problem is not too trivial, nor too hard, and is, of course, interesting.

This contest has several plus points when compared to more traditional programming contests of shorter duration. Unlike other contests, this contest is not simply about pure programming or trivial problem solving, but additionally requires algorithmical insight, creativity and good engineering principles.  Nonetheless, clever programming is then required to solve the subproblems of the final solution.  Another aspect that I personally prefer over other programming contests is that typically the solution is not just an aha-erlebnis, but usually involves tweaking of the solution to optimize the final outcome. In essence, the final scoring function for the participants is a smooth gradient instead of a sudden step function.

Some typical example problems from the past include:

  • Writing a solid-geometry ray-tracer that is scripted by a postscript-like language. (2000)
  • Finding optimal driving instructions for a little race car driving over a race-track with a semi-realistic physics model. (2003)
  • Finding smart collaborative algorithms for a nest of ants that fight against in an artificial environment against another nest of ants, and then pouring that into a very convoluted “ant-assembly” language. (2004)
  • Determining good tactics for cops and robbers playing on a graph trying to outsmart each other. (2005)

The last two years, the focus has switched a bit:

In 2006, CMU came out with whole ‘umix’ system that they had compiled for a custom vm that the participants then had to write.  Once inside this ‘umix’ system, there were a bunch of really nifty puzzles to solve.  From a technological standpoint, the implementation of that umix system was very impressive. I think this might also be one of the reasons why 2007 saw such a boom in participants.

In 2007, given the success of the 2006 formula, a system was designed where DNA would map through RNA to a set of drawing instructions.  If one then executed these drawing instructions, pictures would emerge that contained different types of puzzles.  To be honest, I think the 2007 contest was greatly an attempt to outdo the 2006 one, and by doing so, they undermined the fun of the competition a bit.  If one looks at the gradient of the scores of this contest, it shows a very flat and low beginning, and then a sudden ramp up in the top 17 positions.  This means that 852 teams all had nearly the same score.

I hope that this year they will have a more traditional style of contest.  While puzzles might be fun, they are too much of a yes/no answer and thus allow people little room to tweak and optimize their algorithms to get better scores, which I have found is always the funnest part of the contest: tweaking with the solution in the final day or two days after having built the necessary code and tools to get started.

I also wonder how many people will participate this year.   Last year there was a big jump in the number of registered competitors, where registration is completely optional and can be delayed until the final day.  Due to the way the competition turned out, there was also a huge letdown compared to 2006, so I wonder whether the people that joined due to the 2006 hype will look past the singular fluke to the fun this competition has brought 10 years now.

This will be the fifth year I participate and the third year as my team Lazy Bottoms.  The members of the team this year are nearly all different from last year’s, but I’m definitely confident in their abilities and look forward to collaborating with them on this challenge.

There are several tactics that I have found to be useful for this contest:

  • Come prepared.

This one should be obvious.  Make sure you have decided what tools, compilers, libraries you will use.  Make sure that everyone is using compatible libraries.  Determine what you will use for source code management, personally I use darcs on a external machine with a singular account and several allowed public keys (one for each team member).  Also make sure that everyone is able to connect to the box in question and that all permissions are set up correctly.

  • Communicate effectively.

One of those obvious mantras that is mentioned in every management and GTD book.  If your team is distributed accross the globe like mine is, make sure to have reliable and efficient means of communication.  Typically, we use irc for communicating since that is were actually met and since it is a reasonably efficient means of communicating in a group.  While one might opt for more fancy means, such as video-conferencing, that is not always an option if not every member has those facilities. Additionally, IRC is easier to ignore when working on a problem, and easier to read up on once we wish to find out what is being discussed.

  • Be organized.

While IRC works well for the different communicating threads that occur while working on a problem, it does not work well from an organizational perspective.  Due to the short time that the competition offers and the sometimes serious software engineering that is required to get the necessary tools in place, it is important to have everyone on one page.  For this I prefer using some collaborative editor, for instance gobby, or this year we’ll go for google-docs.  That way the meeting becomes each one writing their part of the meeting notes and then going down over it together to hash out any inconsistencies.  This could potentially also work with one note-taker, but given the limited size of ICFP-teams (4-6 people, usually), it does not harm to have multiple people writing in the same document.  The advantage of this model is that you do not have to reiterate 10 times over a discussion, and you’re sure nothing will get missed by the one person having to write up the meeting notes after the meeting, since they are written and discussed as part of the meeting.

  • Know when to cut your losses.

In a time schedule it’s important to know when to cut losses.  In 2007, part of our team spent a whole day on one particular problem, namely the DNA compiler.  In the end, they could not get it to work and were completely stuck on it.  Another team member (in this case me) then stepped in and took a completely fresh stab at the problem, using a working implementation in python we had and solved it in in several hours.  I do not consider myself particularly smarter than the other team members, on the contrary, we had some very smart people in the team.  The major problem here was that a set of people was so stuck on getting an implementation working while instead we should’ve started fresh and let someone else work on it. This eventually happened, as mentioned, but should’ve occurred a lot earlier. A pair of fresh eyes or a new attempt at a problem from scratch can work miracles at times.

If one looks over the previously mentioned techniques, it quickly becomes obvious that they are also useful in a general software engineering environment.  After all, the ICFP contest is like a small software project with a very tight time-schedule.

Anyways, I’m very excited about the upcoming contest and hope the style will be more like the earlier contests instead of the ones of 2006 and 2007.