Dennis Shasha

Omniheurist Course

Computer Science



We had heard of Dr. Robert Hatchett. A world authority on bioterrorism and toxic waste disposal, he exuded a sense of ironic good humor at the over-hyped technology he heard about every day.

``Nanomachines in science fiction play the role of magic,'' he said with a smile. ``If one needs a super-flexible robot, a swarm of nanomachines fits the bill. If one needs extra-sensory perception, nanomachines can do that too. The forseeable reality however suggests that nanomachines have pico-intelligence.

``In fact the {\em nanomunching} machines we are planning to deploy for hazardous waste disposal will follow a trivial program of the form:

eat at start position
if there is something to eat to the left then go there and eat it
if there is something to eat above then go there and eat it
if there is something to eat to the right then go there and eat it
if there is something to eat below then go there and eat it
end loop

``We abbreviate such a loop as left, up, right, down. Because the nanomuncher gets its nutrients from what it eats, it won't visit a node that it has already eaten or that another nanomuncher has partly eaten. The nanomuncher will not even go through that node. All it will do is keep following the loop on the graph it is assigned to until it can't continue.

``Note that the loop keeps its `program counter' position after each move. So, if you start at A and go left to B, you will first try to go up from B. If not possible, then right, if not possible, then down if not possible then left. If none are possible, then B is called a black hole and the nanomuncher will disintegrate. The goal is to eat at every node in a given graph before entering a black hole. If you succeed, then you have `munched' the graph.

``You are allowed to choose the first node and to choose the order in the loop. So a loop might be right, up, left, down, for example.

``You will be presented with a graph to be munched and your job is to determine how many synchronous nanomunchers you need and where they should start in order to munch the whole graph. The goal is to munch the whole graph using the minimum number of nanomunchers and, within that minimum, to use as little time as possible. Thus, a solution A is better than B if it requires fewer nanonmunchers. If they use the same number of nanomunchers, then A is better if A does this faster.''

edge(nodeid, nodeid)

If several nanomunchers all land on the same node, then only one lives. The one that that moves up has highest living priority, then left, then down, then right. If a new nanomuncher lands on the same node as an existing one, then it lives as opposed to the existing one.

You may start some of your nanomunchers later than at the beginning, but then you are charged for the number of starters.

The architecture group gets a description of a grid which locations have eatable nodes and where there are edges. Each person will give you a list of nanomuncher descriptions consisting of when it starts where it starts its loop program. You simulate as follows. At time zero, each nanomuncher eats its start position. Synchronously, each nanomuncher tries to move and the first place it can move to (has an edge to it and has not been eaten), it moves to. Death may happen. Remember to keep the program counter, so if the last move was the third in the loop, then the first attempt from the next position will be the fourth in the loop. For example, if the program is left, up, right, down and you succeeded in moving using right, then you will next try down then left then up....

There will be a bit more than 100 nodes in a 20 (x ranges from 0 to 19) by 10 (y ranges from 0 to 9) grid and some number of edges. The nodes will be in the format: nodeid,xloc,yloc and the edges: nodeid1,nodeid2. Edges will always be listed from smaller nodeid to larger, though all edges are two-way. Here is some typical data .

And here is a nice graphical interface for the game.