Team 4am is Evan Simpson, and vice-versa. I use Python.
Every year this thing catches me by surprise, and every year I don't really have time to get into it. This year was no exception, since as always I have to scurry around getting ready for the Sylvan Annual Conference the week after Labor Day.
When the challenge was posted, I had to read it even though I didn't expect to join in. I kept thinking about it all weekend. Sunday night I couldn't stand it any more and decided to do at least a stupid minimal entry. I ended up coding twelve hours straight, submitting an entry 9:30 Monday morning. As an early birthday present, my wife took care of the kids and let me sleep all day :-)
The way I saw it, the challenge had essentially three elements:
This is the only part I did much work on. My robot runs in a simple command loop:
This is a little like the travelling salesman problem; given a list of packages and destinations, what is the optimal delivery sequence? Until you visit a given pickup point, you don't know how many packages are there, or where they need to be delivered, so the problem isn't straightforward.
I punted on this. I carefully track the current location of the other robots, but don't bother to use the information.
... is 543 lines, 17,902 bytes of Python 2.2, available here. It was named out of sheer exhaustion.
The entire map is presented up front, including package pickup locations but not information about the actual packages. Only horizontal and vertical movement are allowed. Based on this, I was sure I could get a win from pre-processing the map.
I looked at A*, but decided instead to use an algorithm that divides a map into rectangular or L-shaped regions of open ground. Path finding within a region is trivial, since the optimal path always involves taking a single step towards your goal. Finding the optimal path between squares in different regions can be done with Dijkstra's algorithm on the graph of regions, and the number of regions is usually small enough to make the search speedy.
For each line of the map, I records pickup locations in a set. I initialize an array of region numbers to zeros. Then I use a regular expression to find the runs of accessible terrain. For each square in each run, I set the region based on the corresponding square in the prior line and its left neighbor. If they are the same, copy my left neighbor, otherwise copy the prior line. If any of this results in a zero region, increment the global region counter and use it instead. Once the line is done, convert the array into a binary string encoding and discard the line.
While processing the map, I also build a graph of region boundaries. Each time a square is colored, if its left or prior neighbor has a different non-zero region, I make or extend a graph node for the two regions that records the range of boundary squares.
Using the graph, I then prune out regions that are unreachable from my starting point, in case some packages are undeliverable, or the world is partitioned.
With graph and converted map in hand, it's a trivial lookup to find the region number for a given location and to find the neighboring regions. Whenever the robot takes a step, it looks up the region of its current location (it might have been pushed). If it has a travel plan that includes this region and ends at the goal's region, it looks up the nearest boundary square of the next region in the plan and takes a step towards it. Otherwise, it generates a new plan.
A travel plan is a list of regions to be traversed. It is generated by Dijkstra's shortest path algorithm, with the cost to traverse an arc being the simple distance to the boundary of the next region.
In order to stay within the CPU usage limit, I keep track of the
starting time and the number of moves. time_to_burn()
checks whether the number of moves exceeds the number of seconds by ten.
I did a half-brained solution to the second part. In a pinch, I pick up all the packages I can carry, in increasing order by weight. I then deliver them in order.
If I have time_to_burn, I score packages based on weight divided by delivery time and pick up as many high-scoring packages as I can carry. After each delivery, I re-rank the remaining packages using the delivery time from my current location.
It uses generators to lazily process server messages. It will probably crap out if faced with a map that takes more than 65,535 regions to color -- unlikely at 1000x1000 and below, but possible.
Given more time, I would have wanted to: