It’s now been almost two weeks since the ICFP Contest ended, and I just haven’t taken the time to write about the experience. Heath and I worked together this year on the solution, which was to design an AI to communicate with a “Mars” rover as it attempted to navigate a boulder and crater stricken landscape to find its way home Oh, and there are Martians who want nothing more than to smash your delightful little rover to pieces.

The problem spec is fairly simple, but in its simplicity there is an amazing amount of depth in the ways to pursue the problem. We opted (or I did, and Heath followed) for a Python implementation, as I love Python for prototyping, and the problem was less constrained to raw performance and memory efficiency than the last few years problems.

I began by writing multi-threaded app, where one thread would read data from the socket, and parse out informational packets from the server, updating a global world object with things like obstacle locations and current speed and heading. This left our control thread plenty of time to do all the analysis it wished regarding current state for its decision making. Luckily, we had plenty of time to make decisions.

Unfortunately, we never did much with it. We’d talked about implementing a predictive system which would attempt to ‘guess’ where the rover would be at roughly the halfway point between updates, as this would allow sending sensible commands more often. We didn’t get that far though.

It was a good problem, though it’s been years since I’ve had to concern myself this much with trigonometry. We were constantly revisiting the math, trying to ensure that our calculations were correct and sensible, and trying to reconcile Python’s expectations with the server’s expectations. In the end, we had a decent solution that did pretty well avoiding craters and boulders, but was ignorant of Martians.

This leads me to another issue I had. We were only given three test cases, though we could generate JSON to create our own. The test cases we had were fairly thorough, but a part of me wishes there had been more. My more fundamental issue, was that the reference server we were developing and testing against, was likely somewhat gimped compared to the one scheduled to be used in the tournament to be held to determine a winner. Particularly that we were mostly safe to ignore the Martians on the demo server as they were really, really foolish. In the tournament, this could go either way.

Still, it was a great challenge. Simple, but not too much so, and I was glad to see a challenge where I didn’t spend most of Saturday rewriting my engine because it had originally been just too damn slow. Now, we have to wait until the ICFP (which I may try to get to this year) for the results.

Now, we have Google’s Code Jam. I qualified in decent position in the Qualifier, having only done two of the three problems for the qualifier. The problems were nice and simple, but again not trivially so, and I feel that Google’s data sets do an excellent job of testing. They really love to hit the fringe cases, like ‘no data’ and ‘worst-case’ data.

The first problem was given a list of search engines, and a list of search engines to search for, what would be the minimal number of ‘context switches’ needed given the assumption that a search engine should never be used to search for itself. My initial solution to this, a recursive brute force method, was painful. Mostly because one of the test cases involved two search engines, and the search terms just flipped back and forth between the two.

My final solution was to take the list of search engines, and for each member of that list, check the distance before the first appearance of that engine in the terms, and try to find the one with the longest distance. Use that one, and then perform a context switch by removing all the terms up to the offending one, and doing it again. Nice, simple and fast.

The second problem was one of trains traveling between two stations, and how many trains would be needed to make a sequence of trips. This was much easier. I built a list of trips: departure times, arrival times, and departing station. This list would be sorted by departure time, and then I would just take each element in the list, see if a train was available at the departing station by the departing time, and if one was, removing that train from the list of trains, and adding a new train to the destination station with a ready for departure time of the arrival time plus the turnaround time. If a train was not available, I’d note that one needed to be created at the given station, and do the same appending to the destination station list. Clean and simple.

The third problem was a probability problem that I couldn’t remember what to do with. The question was, what is the likelihood of a tennis racket of a given size (expressed in inner and outer radii), with strings of a given radius a given distance apart, of hitting a circular fly of a given radius. No time element is involved.

Given that, I finally decided that this was likely a function of determining first if the fly could be anywhere in the limits of the racket without getting hit (fly bigger than racket, or bigger than space between strings), and then determining the relationship between the area consumed by the racket and the area consumed by the fly. I didn’t get this done before the time limit, and never did finish it, but I decided that it would be an easy issue of determining the area of the ring, a fairly straight forward equation, as it’s just the area of the outer circle minus the area of the inner circle, and then the area of the strings for one quarter of the racket, then multiplying this second area by four.

I got caught up in implementation details on this, as I worried about things like the area under an arch, and derivatives and the like, but I really ought to finish that code…

But, I qualified, and Round 1 is this weekend. I compete first on Friday, and if I fail to make the top 800 in Round 1A, my second chance is Saturday morning. Wish me luck; if I do well here, that’s just one step closer to a trip to Google!