Escape From The Maze ------ ---- --- ---- You are stuck in a maze and need to escape. The maze is constructed from corridors laid out on a grid of squares. Each corridor is a straight line of squares. That is, corridors are 1 square wide and are straight between their ends. All corridors run either horizon- tally(East/West) or vertically(North/South). All corridor ends are also an end or middle of another another corridor. In other words, there are no `dead end's in the maze. There is a single monster in the maze pursuing you. If you and the monster end up on the same square, the monster will eat you. Here is an example maze: *********** ************Y*********** * * * * * * * * * * * * X *************** * * * * * * * ******** **** * **M*** * * ***** * * * * * ************************** Here X is the exit, Y is you, M is the monster. You CANNOT see the whole maze. In each of the four directions you see one of: W A wall of the corridor you are on. The wall is a boundary of the square you are on. E The end of a corridor you are on, which is just a wall that is the boundary of a square you are NOT on. X The exit. M The monster. You can move one square along any corridor you are in. After you move one square the monster moves one square, and then you can move again. When you move to the exit square you escape and the adventure is over. If you and the monster end up on the same square the monster eats you and the game is over. The monster never exits the maze. The monster is a bit skittish, and as a result, if you suddenly appear in front of it, having come around a corner, it will back away from you in its next move, and not eat you. Because of this you have `always escape' strategies available to you. Otherwise the monster is fairly purposeful, and will pursue you if it can see you. You are required to implement an `always escapes' strategy in a program called `escape'. The Maze Program --- ---- ------- Your program is named `escape' and runs as a subprocess of the `maze' program which is provided to you. The command to run this program is maze escape which invokes the maze program with the `escape' program as its argument. Additional arguments added at the end of this command will be passed to the `escape' program and may be of use for debugging. As an introduction to this problem, you are given a sample `escape' program named `sample_escape', which is described in some detail below. In this program you just move randomly, so the monster eventually eats you. To see what is going on, type maze sample_escape > d1 > m1234 > f30 > f > f > f > f1 1000 > b1 1 > b10 > f > f10 (where the line beginning `> ' is a prompt that you do NOT type). The `f' command runs time forward and the `b' command runs time backward: see below for details. Escape Program Input ------ ------- ----- The `maze' program writes lines to the `escape' program and reads lines written by the `escape' program. The lines written by `maze' and read by `escape' each have one of the following forms: -... A line beginning with `-' indicates the start of a new test case. nesw n, e, s, and w each denote one of the characters W, E, X, M described above which tell you what you see in the North, East, South, and West directions respectively. This line has exactly 4 characters. E.g., `WEMX' means there are corridors to your East, South, and West but not North, and in the corridor to the South you see the monster while in the corridor to the West you see the exit. p... A line beginning with the letter `p' contains parameters for your `escape' program. This is ONLY for debugging. `escape' program input ends with an end of file, at which point the `escape' program must terminate. Escape Program Output ------ ------- ------ For each `nesw' line input you must choose a direction in which to move and output it as the first character on a single line. The possibilities are `N' for North, `E' for East, `S' for South, and `W' for West. The rest of the characters on the line are ignored but may be used for debugging information. If you make an illegal move (either a line that does not begin with `N', `E', `S', or `W' or you try to move through a wall), the programs will crash. For debugging you may output lines beginning with `i' before you output the direction line above. These lines will be printed by the `maze' `f' command (see below), and are otherwise ignored. If you output a line longer than 80 characters, only the first 80 characters will be kept. WARNING: If you are programming in C you must execute fflush (stdio); after writing each line to the standard output, or your output will be trapped in a buffer and never get to the maze program. In C++ the `endl' IO manipulator flushes the buffer and in JAVA `println' flushes the buffer, so nothing unusual needs to be done for these languages. When you ran `maze sample_escape' as indicated above, just before the maze a line appeared which has the form escape-input-line >> escape-output-line giving the last input line to the `escape' program and the output line that program produced to cause the last move. Your `escape' program must be smart enough to escape the maze within 20,000 moves. Otherwise you will be `OUT OF TIME'. Maze Program Input ---- ------- ----- A sequence of command lines each of which contain one of the following: -... A line beginning with `-' indicates the start of a new test case. The line can be used to hold the name of the test case. m S This line creates a maze and starts the action. S is an unsigned integer that is the seed for a pseudo-random number gener- ator that is used to generate the maze and set the initial positions of you, the exit, and the monster. The pseudo-random number generator is also used to make choices for the monster during game action. S must be unsigned and should not have more than 9 digits. Different values of S produce different mazes, but because its a PSEUDO-random number generator, repetitions of this command with the SAME value of S always produce the same maze. If not in debugging mode, this command runs the game action to completion and then prints a single line containing just your fate: `ESCAPED', `EATEN', or `OUT OF TIME'. If in debugging mode the command prints the maze. Then the `f' and `b' commands below may be used to run the action for- ward and backward. p... A line beginning with the letter `p' is copied to your `escape' program input, and can be used to pass parameters to the `escape' program. This is for debugging only. d1 Turns debugging mode on. d0 Turns debugging mode off. f N M D Used when the `m' command was given in debugging mode. Runs forward N*M steps, where a step is a one square move on your part followed by a one square move of the monster. After every M steps, prints out- put, and then pauses D seconds, if D > 0. Running stops if you escape or are eaten or run out of time. Unlike all other numbers input, D is floating point. It defaults to the prev- ious value given in any `f' or `b' com- mand, or to 0.25 if there was no previous value. If M is also omitted it defaults to the previous value given in any `f' or `b' command, or to 1 if there was no pre- vious value. If N is omitted, it defaults to 1. For each group of M steps the following are printed. First some blank lines to separate things from previous output. Then for every step any `i' lines output by the `escape' program are printed followed by a line of the format: input >> output giving the input line to and output line from the `escape' program for the step. Next the maze is printed, followed by a status line that is often blank, followed by a line that is blank or that begins with a prompt for your next command. This command can be terminated prematurely by typing control-C. Typing control-C at any other time terminates the `maze' program. b N M D Just like the `f' command but moves back- ward in time instead of forward. However, does not print `i' lines or `input >> output' lines. Also, if going forward after going backward, these lines are not printed and the `escape' program is not involved until all previously run steps have been passed. When input is from a file, each input line is also output. When input is from a terminal, a `> ' prompt is output at the beginning of each input line. No input line may be longer than 80 characters. Input ends with an end of file (if you are typing input you can produce an end of file by typing control-D). Maze Program Output ---- ------- ------ If not run from a terminal, `maze' outputs a copy of its input. It also always outputs the information described under the `m', `f', and `b' commands above. Sample Escape Program ------ ------ ------- You are given a program, `sample_escape', that can be used to see what `maze' does. `sample_escape' just executes the following: loop: read an input line on end of file exit program if line is a `-' line ignore it if the line is an nesw line: pick a direction at random in which there is no wall (any non-W direction) output a line indicating the picked direction if a line is a `p' line, echo the line inside an `i' line, but otherwise ignore the `p' line Suggestions for running the `sample_escape' program are given above. Sample Input ------ ----- -- SAMPLE 1 -- m1234 Sample Output ------ ------ -- SAMPLE 1 -- m1234 ESCAPED Notes ----- If the monster is on the same square as the exit, you will see the monster and not the exit. Debugging displays will also show `M' for the square and not `X'. If you want to write your own version of `sample_escape' for fun or profit, you may find the following pseudo- random number generators useful: C: #include . . . int i = random(); C++: #include . . . int i = random(); Java: import java.util.*; . . . static Random r = new Random (123); . . . int i = r.nextInt(); File: escape.txt Author: Bob Walton Date: Thu Oct 14 04:38:06 EDT 2010 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2010/10/14 08:38:42 $ $RCSfile: escape.txt,v $ $Revision: 1.18 $