I took a stab at completing the task presented in ICFPC 2012 a couple of weeks back. The task was to guide a miner in collecting as many lambdas as possible from an underground mine while avoiding falling rocks and expending the least amount of energy (quite like the old Digger video-game). As usual, this task had to be completed within three days and once again, I was far from done by the time the deadline arrived. It was however a fair amount of fun for me.
Since it was simpler and provided instant-gratification, I spent the first day creating an SDL-based visualizer that allowed you to navigate and solve a given map using the arrow keys. This implied simulating the rules of the game correctly and verifying that the scores I obtained in various scenarios matched those produced by the web-based validator provided by the organizers. The given set of maps revealed some of the complexities of the task at hand, including having to proactively prevent an already-falling rock from blocking the miner's exit from the mine.
On the second day I had a very bad case of “programmer's block” - I just could not come up with an algorithm good enough to properly complete the given task while scoring the maximum. To side-step this issue, I tried to reduce the complexity of the task by implementing a mode where rocks remain pinned instead of falling down and creating problems for the miner. I also created a set of test-cases to verify that the simulator worked correctly under various scenarios as I modified it.
On the third day I implemented a naive approach based on the A-Star algorithm to find and navigate to the nearest lambda and then the exit when all had been collected, but only if all the rocks remained pinned. (I modified it later to find the lambda with the shortest path to it at each step, as the miner had to some times go around walls to reach the nearest lambda.) This is all I had time to implement in the end.
I chose C as the implementation language because I don't get to program in it any more and I wanted to refresh my programming skills in C. This however proved to be a little counter-productive as I spent a few hours debugging subtle errors in my heap-based priority-queue implementation and in my A-Star algorithm implementation that a higher-level language would have exposed much earlier. As usual you can see the source-code for my attempt here.
This was yet another instance of a task in ICFPC requiring an algorithm that could be described as “a heuristic-based path-planning algorithm minimizing costs in a dynamic environment”. Every time I encounter such a task, I resolve to read about possible approaches and implement some of them before the next year and every time I end up not doing it by then. I hope this time I actually keep my resolution. I plan to start with the excellent overview paper A Guide to Heuristic-based Path Planning (PDF).
By the way, as has been the case in recent years the response from contestants once again seemed somewhat muted this year. I am not sure if it was because the task wasn't novel enough, especially after the high-point reached in 2006, which in my opinion was the very best.
If you want to read other write-ups on this year's contest, check out the ICFPC sub-reddit.