Greg Heartsfield home

ICFP ’08 Contest

I gave the ICFP contest a try again this year, and had a really good time. The task was to write a controller for a martian rover, capable of avoiding basic obstacles like boulders, as well as enemy martians of unknown intelligence. Telemetry input streamed from a network socket to the controller, and basic control commands such as accelerate or turn left, had to be sent back.

Unlike previous years, where it took some time (several hours of implementing an interpreter spec) to really understand the scope of the problem, you knew what you were getting into after reading the very concise task description. I immensely enjoyed the previous formats, but change is good.

Haskell seemed as sensible a choice as anything else, so I went with it. Sending and receiving formatted data (a sample server was provided) over a network socket was the first task, and that was thankfully straightforward. 4 lines (connect, unbuffer, receive, send), and no more I/O to bother with.

Parsing messages from the server was a bit clumsy, I have promised myself I will learn Parsec soon. Sending messages was nicer though, since I just had to define the datatype, and make a simple instance of Show.

I was somewhat familiar with Yampa before the contest, but I could probably spend a whole weekend just fully understanding how it works, so I decided to stick to a simple turn-based strategy. For every telemetry message sent by the server, I would compute the command sequence to send to the rover, and then wait for new telemetry. The server latency was small enough (~100ms) to make this acceptable.

The biggest challenge was deciding how to structure the event loop, and create composeable strategies for the rover. Given the initial message, and a telemetry message, the controller could probably do a satisfactory job of deciding what commands to send. I had some grand plans of updating a global view of the map, as well as tracking acceleration/braking constants, so I wanted to keep track of some changing state for each turn. My simple solution, which I think was the right choice given the time constraints, was to create a datatype for the rover/world state, and write strategies as transformers of that state. The natural choice to handle this was the State monad. The world (init message), the rover (acceleration/turning state), and the current and past telemetry were encapsulated inside the monad, and the return value was a list of command messages. Each strategy would be able to inspect the telemetry and current rover state, and make changes, or do nothing. By ordering these strategies, I was able to make a rover that charged ahead towards the goal, until it detected something in its path (causing it to turn), or detected it was going to overshoot its goal (causing it to slow down). Strategies could be combined in order, with the last one able to override any previous decisions.

Strategies manipulated the desired state of the rover, which was represented as a state machine. Commands had to be sent that took the rover from its previous state (described in telemetry messages) to the desired state. Making each of the state components an instance of Enum made this transition simple. I just had to count how many applications of the succ or pred functions were necessary to move the state to the goal.

Finally, in the main program, the state transforming function was mapped over the parsed network input, and the result was evaluated, and sent back over the wire.

You can view my solution here: Darcs repo of icfp08

Cheers to the organizers, who did a really fantastic job creating the task (crazy difficult, but very approachable), manning IRC, and keeping track of issues/FAQ.

Validate XHTML Validate CSS