August 1996 Programmer's Challenge

A-Maze-ing

Mail solutions to: progchallenge@mactech.com

Due Date: 1 August 1996

Deep underground in an abandoned mine. No lantern. No rope. Not much air. Or something like a lack of air that makes you want to leave in a hurry. This month you find yourself lost in an underground maze with nothing except your trusty Challenge solution to help you quickly find your way out.

The prototype for the code you should write is:

typedef Boolean /* found exit */ (*MoveProc) (
  long xMove,    /* amount of attempted move in x direction( 1,0,-1) */
  long yMove,    /* amount of attempted move in y direction (1,0,-1) */
  long zMove,    /* amount of attempted move in z direction (1,0,-1) */
  long *newXPos, /* new x position after attempted move */
  long *newYPos, /* new y position after attempted move */
  long *newZPos  /* new y position after attempted move */
);
 Boolean /* found exit */ Maze (
  long xPos,          /* x component of initial position */
  long yPos,          /* y component of initial position */
  long zPos,          /* z component of initial position */
  long xSize,         /* size of maze in x dimension */
  long ySize,         /* size of maze in y dimension */
  long zSize,         /* size of maze in z dimension */
  MoveProc MakeAMove, /* callback to attempt a move */
  char *mapStorage    /* one byte for each position in the maze */
);
 

Your Maze routine will be called with your initial position (xPos, yPos, zPos) and the address of a callback routine you can use to attempt to move within the maze. Your code should make sequential calls to the MakeAMove callback until the callback returns TRUE, indicating that you have found your way out of the maze. All exits are on the boundaries of the maze (i.e., at least one coordinates equals 0 or [xyz]Size-1). With each move, you can attempt to move up to one unit in each dimension (x, y, and/or z). The callback will return your new position (*newXPos, *newYPos, *newZPos) after the attempted move. If a passageway exists in the desired direction, the new position will be offset from your previous position by the desired amount. If no passageway exists, the new position will be the same as the previous position (and you will be slightly bruised from walking into solid rock). One slight complicating factor is the combination of darkness and gravity &endash;if you walk into a position where a vertical shaft is open below you, the callback will return a position where the vertical (z) coordinate is reduced the distance you fell. For this reason, moves in a z-only direction are never needed, as a purely downward move will always fail (you will already have fallen), and a purely upward move would be futile (you would fall back to your previous position).

The callback will obviously know which positions in the maze are filled with rock and which are open. In the event you wish to construct a map as you grope around in darkness, the mapStorage parameter will point to xSize*ySize*zSize bytes of storage for your use, initialized to zero by the caller. Once the callback indicates that you have found an exit for the maze, you should return TRUE. If you have cannot find an exit, you should return FALSE (rather than loop forever), although this should not happen, because a path to an exit will always exist.

Selection of the winning solution will be based on total execution time of the Maze routine, including the time spent in the callback. The same callback code will be used to test each solution, providing a fixed time penalty for each attempted move.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. To keep the contest focused on code efficiency (rather than compiler efficiency), all solutions will be scored using the Metrowerks compiler for the appropriate language.

POST PUBLICATION NOTE: In response to a question on the Challenge mailing list, you may allocate up to 10MB of additional storage, provided you deallocate it before you return.

• Download test data for the Maze Challenge