The ICFP 2008 Programming Contest (or, My Abject Failure)
Well I tried my hand at the 2008 ICFP Programing Contest. I had fun, but man oh man did I fail. FAIL.
But first, a quick video of success!
Let me get this out of the way first. After many hours spent feverishly coding, testing, coding, testing, submitting trial builds, etc, I left a debugging flag in my code and submitted it. This particular gem instructed my program to quit after 1 run. The trials go 5 runs. My program won’t make it that far, and so I will be disqualified. For all that is holy in this world why did I do that?!
Ok, that’s better.
I didn’t have a lot of time for the contest. They let us know the problem at 3:00 pm (US Eastern) on a Friday and it’s due Monday at 3:00 pm. Given that 7:00 am to midnight on the weekends is family time means there isn’t a lot of time for fun like this. Now I’m not making excuses, at all, but it’s clear that next year I’ll need to disappear to a hotel somewhere for the duration. Get some energy drinks, some Power Bars, and just crank away.
I originally wanted to use OCaml for this since I’m in the process of getting into the language (and into functional programming in general) but I slipped into Python due to the limited time constraints. I also came up with a bastardized OO / functional / procedural style. Doing this in OCaml in a nicely functional style would be cool. I might keep going at this.
Getting my new rover talking to the sample servers was pretty quick. The following bit of code connects to the server and starts a loop:
server = socket.socket(socket.AF_INET, socket.SOCK_STREAM) server.connect((hostname, port)) server.setsockopt(socket.SOL_TCP, socket.TCP_NODELAY, 1) run = 0 buff = [] fragment = None while run < runs: # get more from server data = server.recv(PACKET_SIZE) # if there was a fragment from the last message then put that in front if fragment: data = fragment + data # split by ; buff.extend([x for x in data.split(';') if x != '']) # handle any messages in the buffer buff, fragment, end_of_run = _process_buffer(buff) if end_of_run: run += 1 if verbose: print "end of run, %d, %d" % (run, runs)
So, I get the server messages off of the wire, make sure I get any fragments from the previous go, and then process the messages. In practice this was fast enough so that I usually only had 1 message, but occasionally the server would cause a delay. I think they did it on purpose.
In my _process_buffer() function I use a dictionary to dispatch the correct function:
_message_handlers = { 'I' : _handle_init, 'T' : _handle_telemetry, 'B' : _handle_boulder, 'C' : _handle_crater, 'K' : _handle_killed, 'S' : _handle_success, 'E' : _handle_end } end_of_run = False fragment = None for i in range(len(buff)): if verbose: print "HANDLING MESSAGE:%s" % buff[0] msg = buff.pop(0) if msg != '' and msg[0] in _message_handlers: try: _message_handlers[msg[0]](msg) except IndexError: # it's a fragment fragment = msg return buff, fragment, end_of_run if msg[0] == 'E': end_of_run = True break else: # it's a fragment fragment = msg break return buff, fragment, end_of_run
Ok, so far so good. I’m able to read off the wire and handle the messages accordingly. Note here the use of a Python dictionary for function dispatching. You’d use a switch in a lot of language, but you’d use pattern matching in OCaml or Haskell. Pattern matching is elegant and simply can’t be beaten even by this cool Python hacking, but it’s the best I could do to stay with the spirit of the competition.
Here’s where I got blasted though. Instead of developing the correct pathfinding solution I just roughly steered the rover away from craters and boulders and generally towards home. It’s hilarious to watch because it looks like the thing is drunk–it’s all over the place!
Here’s the code that watches out for craters:
if 'c' in t.nearby_objects: nearest_crater = t.get_closest('c') crater_location = (nearest_crater.object_x, nearest_crater.object_y) a_crater = calc_angle_to(current, crater_location) dist_crater = calc_straight_distance(current, crater_location) # if there's a crater nearer than home then get away from it if verbose: print "CRATER is %f meters away at %f" % (dist_crater, a_crater) if dist_crater < dist_home and dist_crater < 10: # notice this is the inverse turning direction _brake(15); if a_crater < t.vehicle_dir: _turn_left(accelerate=True) else: _turn_right(accelerate=True) return
Anyway, it avoids most of the craters except when it really wants to drive straight into one from 20 meters away, making no effort to avoid it. I’m laughing as I type that but damn was this hard.
Had a great time and I built a rover that can find home base in about 1/2 of the maps I created. All in all not a bad way to spend time.
Read more from the OCaml, Python, Uncategorized category. If you would like to leave a comment, click here: . or stay up to date with this post via RSS, or you can
Trackback from your site.
Leave a Comment
2 Comments so far
We had started with the “avoid nearest crater” solution, but our avoidance algorithm had an “OMG mode” where it would turn hard left to avoid a crater in its way - subsequently hurling himself into the nearest crater, lol. He didn’t do so well until we took into account *all* the craters in his his little viewing circle.
I feel your pain. I did the whole “disappear from the world” thing and spent 46 hours almost entirely devoted to four-five different routefinding algorithms, each of which sucked harder than the previous one. I put almost zero effort into the “not running into things” aspect. In retrospect I should have simply aimed for “not trying to win but not crashing” rather than “trying to win at a high risk of crashing”. Robot does fine on the 3 sample maps they gave out (which, face it, are all very similar to each other) — but is certain to die on any marginally pathological map. There’s a good chance that my lightning round entry probably would beat my final entry.