The Mercury Mercurians' ICFP 2004 programming contest entry
This page describes our team's effort in the
2004 ICFP Programming Contest.
The team members
This year the Merry Mercurians team consisted of three
members of the
University of Melbourne
Department of Computer Science and Software Engineering
:
-
Ralph Becket
- A research fellow with the Mercury
and HAL programming language groups.
-
Julien Fischer
- A doctoral research student
investigating automatic proof of termination in
Mercury programs (it works, too!)
-
Ian MacLarty
- The newest member of the group, a
masters student working on declarative debugging for
Mercury programs.
And
here
you
can see a rather unflattering team photo. Julien is on the left,
Ralph is in the middle, and Ian is on the right.
Mercury
Mercury
is a highly efficient, purely declarative
logic/functional programming language. It might lack
the syntactic brevity of Haskell, but our error
messages are a joy to behold. Unlike some declarative
languages, you don't need a Rosetta Stone and a twisty
mind to understand what the Mercury compiler tells
you. This was a great help building our tools for the contest:
the simulator ran perfectly first time, if you can believe
such a thing!
We constructed a number of tools.
-
The simulator
- Pretty much a direct translation
of the specification in the Task Description.
-
A text-based graphical viewer
- Handy for
early testing while the graphical viewer was being
developed (you had to run this one in a huge window
with a tiny font; not recommended for users with
poor eyesight). Here's a
sample
of the output
showing
star.ant
at work, with visible trails
for the red ants.
-
A graphical viewer
- What can we say?
Invaluable. Written by Julien using the Mercury OpenGL
binding.
-
Compilers for two different
`high level'
ant programming languages
- Ralph and Ian
disagreed slightly on what a good language would look
like, and both ended up with something slightly
horrible. Here's a
sample
of
Ralph's language, giving the code for
star.ant
and here's a
sample
of Ian's
language, giving the code for
ian5.ant
. Julien
even implemented a simple optimizer for Ralph's
language.
trailer.ant
was primarily Ralph's effort. On the sample
worlds,
trailer.ant
and
ian5.ant
performed
equally well. Which Ralph felt was a shame because
trailer.ant
is the more sophisticated of the two.
trailer.ant
uses four kinds of ant:
-
Ants initially on the periphery of the anthill
perform a random walk looking for food, leaving behind
a trail of markers
a b c d e f a b c
... When
these ants encounter food, they run their trail through as much
of it as possible before moving on to look for more food. The
length of the trail sequence makes confusion between trails
much less likely -- this was a genuine issue, and ultimately
even required that trails not be allowed to cross one
another.
-
Ants not initially on the periphery of the anthill
disperse slowly and at random (to avoid congestion) and
follow the trails from the nest to the food. When they
find food they pick it up and follow the trail back. If
a returning ant bumps into a friend, it drops its food
item, turns around and goes to get more. This led to a
kind of `bucket chain' behaviour.
-
Three ants in the nest identify themselves at the start
of a run. One `fortress' ant sits still and just sits on any
food placed in front of it. Two `hoover' ants would wander
around the nest at random picking up food left by the
gathering ants and bring it to the `fortress' ant. This
worked reasonably well as a safeguard against theft by enemy
ants.
-
Random ants -- well, it's a simple strategy for getting
out of tight spots!
ian5.ant
was Ian's baby:
-
Initially a 3 ant triangular fortress is formed with each
ant in the fortress continually looking for food in surrounding
cells and bringing any food it finds into the fortress. Since
no ant in the fortress can be surrounded by more that 4 ants,
the fortress is impenetrable.
-
All other ants leave home and wonder randomly around the
map looking for food. They leave behind a home trail that
randomly runs out.
-
When an ant discovers food it marks the surrounding area
with food markers, then it returns home by randomly wondering
until it reaches a home marker. It will try to stay with a
home-marked area until it finds its home. When inside its base
camp an ant will stay there until it finds the fortress at
which point it will drop it's food. A fortress ant will then
detect and collect the food.
-
When an ant finds a food marker, it tries to stay in the
food area until it finds food.
-
That's it.
A truly voracious ant
(but too late):
star.ant
As is often the case with ICFP contest, the best ideas don't
occur until after the deadline. But for your edification, we
present
star.ant
, an ant of truly frightening
efficiency. Ralph's rather proud of this one, but then a
sense of timing was never his long suit.
star.ant
works like this:
-
The foremost triangle of ants identify themselves at
the start of the run and form a `fortress' where all food
will be stored and which, barring unbelievable bad luck,
is invulnerable. The front two fortress ants just remain
stock still for the rest of the run, while the rear one
(eventually) lays out a trail of
c
markers before
returning to its `home' spot in the fortress:
+ + + + + +
+ + + + + + +
+ + + + + + + +
+ + + + + + + + +
+ + + + + + + + + +
c c c c c c c c c R R
+ + + + + + + + + R
+ + + + + + + + +
+ + + + + + + +
+ + + + + + +
+ + + + + +
Returning ants wander around in the nest until they hit a
c, whereupon they bounce back and forth until they can
drop their food in front of the rear `fortress' ant, who
quickly snaps it up and returns it to his spot.
-
Every other ant around the periphery then starts laying
a trail
[blank] a b [blank] a b
... which
returning ants will follow when bringing food back to the
nest:
. . .
. . . .
. b b b
. b a a a
. a
. b b b b
. a b a a a
b a
a b + + + + + + a b a b a b a b ...
a + + + + + + +
b + + + + + + + + a b a b a b a b ...
a + + + + + + + + +
+ + + + + + + + + + a b a b a b a b ...
c c c c c c c c c R R
.. b a b a b a + + + + + + + + + R
+ + + + + + + + +
... b a b a b a + + + + + + + +
+ + + + + + + a
... b a b a b a + + + + + + b
a
a a a b a
b b b b
a .
a a a b .
b b b .
. . . .
. . .
Returning ants just wander around at random until they hit an
a
or
b
, orient themselves, and
charge straight back to the nest.
-
All the remaining ants start out as hunters: a hunter
performs a random walk across the board looking for food.
If if finds a clump of food, it marks the centre and lays
out a star of trails
[blank] d e [blank] d e
...
extending out in all directions:
. .
. .
e e
d d
e e
d d
5 5 5 5
...e d e d 5 5 5 5 d e d e ...
5 5 5 5
d d
e e
d d
e e
. .
. .
Other hunter ants that stumble upon a
d
or
e
quickly orient themselves and charge straight
towards the food.
-
Once the food at a spot has been exhasted, ants will
randomly erase the food trails in order to avoid wasting
useful foraging time.
-
It's a beautiful thing to watch: after a short while
there are paths leading to all the food clumps and paths
leading straight back to the nest. The ants form orderly
convoys to pick up food and then order themselves again
to return it to the nest. It's fast, efficient, and
really simple. I wish I'd thought of it two days ago...
|
