Programming Competition Post-Mortem

Every year the ACM-sponsored International Conference on Functional Programming holds an elite Programming Competition for international recognition (and a $1000 cash prize). Essentially, a problem is posted on their website on Friday at noon and each team has all weekend to complete and submit a solution in whatever programming language they choose. This was the first year I’ve competed and I’m pretty much hooked forever.

The International Conference on Functional Programming is a conference geared to promote functional programming languages, such as Haskell, Lisp and Scheme. For those of you who are unfamiliar with functional programming, it’s a completely different mindset from regular programming. One has to “think recursively”, or as “Lambda geeks” would say: think “purely”. In recent years, the ICFP Competition has become more and more accepting of “general purpose” languages such as Java to make the competition more approachable to mainstream developers. (To illustrate my point, try doing a Monster job search for “Scheme” and “Java” to see the extreme difference in numbers).

This year’s problem was very interesting: our job as the competitors was to create a pathfinding algorithm for a Mars rover simulation, which included obstacles such as Craters and Boulders and intelligent martians (though at times NOT too intelligent) who would destroy your rover on contact. This wasn’t a simple “just-implement-A*-pathfinding-and-be-done-with-it” problem because you had to take into account turning radius, radial acceleration, drag, martian avoidance AND desired location – not just desired location.

Our team (NAU ACM and facebook group) decided to program our solution in Abe Pralle’s gaming language, Slag, not only to promote Abe’s language but also because this was a *perfect* problem to show off Slag’s strengths. Pathfinding is not a new concept to game development and most of our collision detection routines were already written for us in the Plasmacore framework.

Our first lightning solution algorithm was as rough as rough can be: the rover would just make a bee-line for the homebase, damning the consequences and obstacles. We had discovered a bug in our first implementation that forced the rover to “wobble” which actually ended up being a remarkably effective obstacle avoidance technique! Our lightning round solution (within 24 hours) used this basic method with a simple “avoid the closest crater to you” intelligence.

Our final solution algorithm was two-part, working together and sharing information:

1. The first part of our algorithm was taken from our original rough lightning round design – the rover wants to go “home”. If there was an obstacle in the way, the controller would “move” the home base location until the obstacle was no longer blocking our path. We then calculated the rover direction necessary to make that non-obstructing path a reality.
2. Then the path was sent to the “emergency response system”. Our rover had 5 “view fingers”, which were essentially linear vector paths in five different directions (Hard Left, Left, Middle, Right, Hard Right). The rover would determine the linear direction that would get him closest to the “home base” and then determine whether this direction was safe to travel (with line/circle collision detection). If the direction was safe, he would travel there. Otherwise, we had a complex system for him to determine the closest path he can take whilst avoiding the obstacle in front of him. Dr. Palmer came in and explained to us the the closest path around a circular obstacle (craters, boulders, martians) is actually by “hugging the obstacle as close as possible”, so we used that method.

Throughout the experience, we had a sister competitor team we would occasionally call at 3AM to discuss strategy and progress. It felt more like a scientific collaboration than a competition – everyone was trying to find the best solution and working together rather than keeping information under wraps. There were about 350 team submissions to the regular competition and 170 lightning round submissions, according to the competition organizers. During the competition, the IRC channel had close to 350 people all conversing about strategy and rules together. It did seem in this competition, collaboration really did seem to pay off over competitiveness. But you know, hope we win! Sadly, we don’t get to see the results until September!