So after spending around 16 hours (and writing about 700 lines of original code) on Saturday preparing an entry for The Eighth Annual ICFP Programming Contest, I thought I'd share my notes and some thoughts. A chunk of this is Python specific. (see this thread for metrics of entries using other languages.
It appears that our implementation is smaller than most listed in the thread (and ours even includes test code in the 700 lines, though our implemention isn't necessarily that smart). And it took less time than many others. Too bad we didn't have more time to put smarts in...) The problem consisted of writing robots that navigate a map to achieve certain goals. There are two types of robots to implement, a cop (whose goal is to catch a robber) and a robber (whose goal is to evade cops and steal money). That should be enough context to understand the rest of this post.
Parsing in Python
These robots are controlled by using a simple protocol described by a grammar. In order to parse the text that the games server sends back, we decided it might be a little more robust to use a lexer and parser (I haven't done this since my compiler class in school...), rather than dealing with a bunch or regexes or if/else looping over lines. After a pretty cursory search we decided to use ply. After checking out the example, it seemed that there was a very clear mapping between the grammar described in the problem and the PLY implementation.... But using ply was probably our biggest mistake (and time sink) of the day.
Don't get me wrong, maybe we are just stupid since the home page states "PLY is extremely easy to use and provides very extensive error checking", but we had a few issues that got us hung up for a while. Since we only had the day to program we didn't have the luxury of emailing the mailing list, and there didn't appear to be a FAQ anywhere.
I'm sure if we had had more time, we could've figured out our issues. Some more gripes about PLY is that is isn't "pythonic" (a quick attempt to use the lexer and parser in a more object oriented manner failed) and Mr. Beazley is doing some magic behind the scenes that made implementation debugging a little painful.
After realizing that we were wasting cycles my partner and I decided to each go and try and implement a new parsing solution (we had basically been pair programming til then). I ended up trying pyparsing. The initial drawback to pyparsing seemed to be that instead of having a straightforward copying of our grammar, we had to convert all of the grammar tokens into objects.
Also, my quick browsing of the examples provided seemed to not provide me with enough understand of pyparsing and its objects to implement our grammar. The examples found in the article by Dave Kuhlman, gave me the examples I needed.
In a few minutes we had an implementation to parse the most complicated message. A possible drawback to pyparsing is that it appeared to be rather generous in what it accepted (which didn't matter in our case since we were guaranteed that the server wouldn't send back invalid content).
Flush stdout
We were also having other communications issues including a broken development kit for windows (it worked on linux though). Our robots communicated with the server via stdout, and stdin. A small bug that bit us was forgetting to flush stdout to talk with the server. Rather than reading our message the server would time out because we didn't flush the buffer.
Old state machines
We first implemented a simple robber robot because he had very little state. The cop had a bit more state, but the transitions from state to state were pretty simple and there were few branches. We could implement a big switch statement (bunch of if/else in python) or try to use a state machine. After a quick google, we choose one out of the two we looked at. The two in question were one from the ActiveState Cookbook and one from a 10 year old email (written by Skip Montanaro). We choose the 10 year old one because the cookbook implementation had a comment to code factor of about 10 (which made it look really complicated). Skip's implementation was really simple and we probably only changed 3 lines of it and it worked.
Executable Pseudo Code
To implement some of the graph algorithms I brought my Cormen Algorithm behemoth along. The implementations proved very simple. I would dare say that there was a 1 to 1 mapping for pseudo code in the book to python code (1 line in the book translated to 1 line in python).
unit tests
Along the way we created unit tests using unittest. These proved to be valuable as we changed occasionally the interfaces to some of our classes, we could run the tests and see what broke.
Pair programming
For probably 13 of the 16 hours we were pair programming. I think that helped us is a few ways:
1) We were both able to understand all of the code
2) We could catch errors along the way before executing as the 2nd pair of eyes can become a virtual compiler.
3) Using python we could brainstorm and implement really quickly to try out our ideas.
4) Productivity and motivation. Having someone right next to you tends to make you pretty productive and in this case I feel that 1+1 > 2.
We still haven't implemented much of the brains, and that may prove to be pythons downfall in this whole exercise since the robot has a time limit to submit their move. But for implementing a basic robot, python and the existing code libraries for it proved invaluable.