The new Estragon-class Martian explorers are rather advanced. They can explore indefinitely using solar energy, and can move in one of eight directions (N, S, E, W, NE, SE, NW, SW) at any time. However, this advanced design comes with a price. Due to the weight of the explorer, a location that has been traversed twice by the explorer becomes impassable.
Your job is to program the explorer so that you can visit as much of the Martian surface as possible. The surface is modelled as a two-dimensional grid of unknown size. Each grid square visited scores a point, and the total score is the number of squares visited before the explorer becomes blocked. Visiting a square a second time does not increase the score. (In the event that the explorer stumbles into an impassable square, the score is halved as a penalty for losing the craft.)
As mentioned above, when a square has been visited twice, it becomes impassable. There may be other impassable squares in the terrain, corresponding to natural obstacles. In fact, even though you don't know how big the area to be surveyed is, you may assume that it is bounded on the perimeter by impassable squares, and is finite. (The surface does not wrap around; the portion to be explored is small enough that you can approximate it as flat.)
The explorer can sense its immediate neighbors to determine if they are passable or not. The result is an 8-bit value (one bit for each direction) where a 0-bit means that the square's impassable, and a 1-bit means the square is passable. The order of the bits is (SW,S,SE,W,E,NW,N,NE). You may assume that you always start on a passable square. This square will be randomly chosen from among the passable squares in the terrain, since it is difficult to predict exactly where the explorer will land. (The score starts at 1, since you've visited the starting square.) Because the starting point is random, you won't be able to hard-code any terrain-specific traversals.
As it moves, the explorer can keep track of the state of the world. For example, the simulator does not distinguish between squares that have not been visited and squares that have been visited once: both give a 1-bit indicating that they are passable. If you want the explorer to be able to distinguish them, you need to record the explorer's path. The explorer obtains only local information, but over time it can accumulate a global picture. The explorer must try to avoid getting stuck despite having limited knowledge of what's ahead.
Once the explorer reads the 8-bit value, it must respond with a number between 0 and 9 inclusive. The numbers 1 through 9 correspond to the compass directions as on a numeric keypad: 1 is SW, 6 is E, 8 is N, etc. The direction 5 instructs the explorer to stay put for one move. This will never increase the score, but will have the effect of making the current square impassable if it was not already. (A passable square becomes impassable the moment the explorer steps on it for the second time. The explorer can move off the impassable square on the next move, but cannot stay put. A ``stay put'' move when on an impassable square is equivalent to moving onto an impassable square.)
The ``0'' command is a termination signal, and should be used when there is no further work for the explorer to do, such as when it is surrounded by impassable squares. Since the only other way to terminate is to move onto an impassable square, which halves the score, the explorer will typically finish with a 0 command.
After each legal move (other than a 0), a new 8-bit value is returned, and the process continues. The driver program will keep track of the score and will determine the legality of moves. For a given terrain, a program will be run many times and the scores averaged, since the starting position may have an impact on the explorability of the terrain. Your programs may not keep any persistent data between runs; each exploration must start from scratch.
Your program will read the 8-bit value as a number (in base 10) from standard input. The program's move should be written as an ascii digit to standard output, followed by a newline. The next 8-bit value can then be read, and so on.
We will provide a simulator that reads in the terrain from a file, and then interacts with your program. The simulator will also allow you to visualize the progress of your program, either with or without a complete map of the terrain. Further, the simulator will have an interactive option to allow humans to explore a terrain using a keypad.
There will be many terrains to explore. At the end of the project, your programs will be run both on terrains you have previously seen, and on terrains you have not seen before. (Your programs will not know the identity of the terrains.)
You are also encouraged to generate terrains yourself for the class to use for testing. The format for a terrain file is a pbm file (portable bitmap; do a man pbm for details), in which 1 means passable and 0 means impassable. Regions outside the bitmap are implicitly impassable, so that moving off the edge of the bitmap is effectively moving onto an impassable square. A valid terrain must be connected. In other words, every passable square should be reachable from every other via passable squares only.