This page describes our entry for the 2004 ICFP Programming Contest.
Update: We won the contest! It was great to hear the judges confirm what we already knew, namely that "Haskell is the language of choice for discriminating hackers!" Our thanks to the organisers for a great and meticulously organised contest.
Our submission as a .tar.gz (untars to . as the specfication requires) and unpacked.
If you want the ants with more unique names, they are dunkosmiloolump-1.ant and dunkosmiloolump-2.ant
Our team consisted of Ian Lynagh, Andres Löh, Duncan Coutts and Ganesh Sittampalam; our entry was written entirely in Haskell. We used Darcs (also written in Haskell) for our revision control.
We used a monadic combinator library to construct our ants, and then compiled the result into optimized ant code.
Our basic strategy is to leave 7 ants at home in a "keeper" structure to protect our food and themselves, and to have everyone else wander off leaving a trail pointing back to base. When they find food they walk back to base marking the trail as one pointing to food, thus helping other ants find the food. Once a food supply is exhausted, the food markers are deleted.
We use 3 bits to encode directions. Bits 0-2 are the path home - every ant looking for food leaves a marker pointing back the way it came on any space that doesn't already have a marker. In this way we hope to have fairly good paths home, and in practice they seem to work fairly well.
Bits 3-5 are pointers to food. When an ant picks up food it follows the trail home, marking a food pointer in reverse. We need the separate marker because of the different behaviour at corners, though we could probably have had a better encoding given more time.
You can see the slides of a talk on the contest and our ant.