CSCI325 Data Structures

Updated 2017.10.28

Stacks and Mazes

Problem description

One way of finding your way out of a maze is to follow the "right-hand rule." That is, move through the maze, always keeping your right hand on a wall. Another way of stating this rule is: "Turn right when you can, and turn left only when you must." This rule will eventually get you out of the maze, even though it may cause you to do some backtracking. You are to write a program which will find a path through a maze using the right-hand rule but without any backtracking. Backtracking can be avoided by using a stack.

Input

Ask the user for the file name. You may assume that the file will be in the root level of your project (so you don't need to include any path info).After getting the file name, read the file into a 2-dimensional array of characters. Then use the "right-hand rule" to find a path through the maze. File input will be in the following format: (1) line #1: a number telling the number of rows and columns in the maze (it's always a square, so we only need one number here), (2) line #2: a number telling the column of the entry point to the maze (a number from 1 to the size of the maze-2 (there's a wall in column 0 and a wall on column size-1), (3) lines #3 through size + 2: a row of characters. Blanks represent a path through the maze, and non-blanks represent walls in the maze. For example, a 5 x 5 maze could be represented as follows (note that the blanks have been represented as hyphens to make it easy to count the number of blanks—the actual file would have blanks). Note also that the arrow in the bottom row is not part of the maze—it is indicating the robot's starting position:

5

2

XX-XX

X---X

XX-XX

X---X

XXXX

Note that you always enter from the bottom (you may assume that you are in the doorway – in this case, your starting row is 4 (size–1—thearray is zero-based) and the starting column is 2 (3-1 -- the array is zero-based). So you will always start out in the "doorway". Your first step will always be north.

Processing

Dynamically set the size of a two-dimensional array to the size of the first number in the file (so your program will work with any size array). Read in the data and store the maze in a two-dimensional array. Use the right-hand rule to determine a path through the maze without backtracking. Create a stack (you may use the Stack class from java.util that implements a generic stack) and use a stack to store your progress through the maze, by pushing the direction of each step on the stack.

Below are the data structures for this assignment. I have completely written the Direction enumeration (not a class) file for you. The other classes are also relatively simple. Once you have them written, your main program almost writes itself (almost).

Data Structures: the Direction

Use the following code for your Direction variables. Create an enumeration, not a class (File | New File | Java Enum):

public enum Direction {

North { public Direction getOpposite() { return South; }},

East { public Direction getOpposite() { return West; }},

South { public Direction getOpposite() { return North; }},

West { public Direction getOpposite() { return East; }};

public abstract Direction getOpposite();

}

This will give us values for our direction variables. If you use this, you can declare a variable like this:

Direction dir;

And you can assign it values like this:

dir = Direction.North;

And you can find its opposite like this:

dir.getOpposite()

And you can print it out like this:

System.out.println (dir);

In this case, it will convert the value to a string (e.g. North will be printed as "North").

Data Structures: the Maze class (part 1)

Create a Maze class that has the following private variables:

  • A 2-dimensional array of char for holding the maze.
  • A size. An int. This is the number of rows and columns in the maze (it is always a square maze).
  • A starting column. An int. This is the column in the bottom row of the maze which a traveler will use to enter the maze. That is, there is a gap in the wall. It will be a number from 0 to size – 1.

The Maze class should also implement the following public methods:

  • Constructor –Maze(String filename):This is the only constructor. The string is the name of the file that the constructor is to read to get its data from. It will read the size of the maze, the starting position in the maze, and read the data into a 2D array of char.
  • boolean wallAhead (int row, int col, Direction dir): This is a boolean method that accepts a row and a column and a direction. If a person were located at the given row and column and facing in the given direction, then the method returns true if a wall (non-blank) is immediately ahead (the next square) and it returns false if a space is immediately ahead.
  • boolean outOfMaze(int row, int col): This is a boolean method that returns true if the given row and column value represent a position that is "out" of the maze. You are "out" of the maze whenever you step into a doorway. For example, if the maze is 10x10 (rows and columns are numbered from 0 through 9) you are out of the maze whenever you are in row 0 or row 9, or whenever you are in column 0 or column 9.
  • String toString(): This returns the 2D array of char as a string, with carriage returns (new line characters) at the end of each line. This makes it possible, in the main program, to write out the maze with a single command.
  • int getRows(): This returns the number of rows (and columns) in the array. This is needed so the robot knows where to start.
  • int getDoorCol(): This returns the column that the door is in (using the zero-based column number). This is needed so the robot knows where to start.

Data Structures: the Robot class (part 1)

Create a Robot class that has the following private variables:

  • A row and column (both ints) indicating the robot's location in a maze.
  • A Direction indicating which direction the robot is facing.

The Robot class should also implement the following methods:

  • Constructor. Robot(int startingRow, int StartingCol, Direction startingDirection). This is the only constructor and it initializes the robot at a given row, column, and direction.
  • int getRow(): returns the robot's row.
  • int getCol(): returns the robot's column.
  • DirectiongetDirection(): returns the robot's direction.
  • void turnRight(). This method changes the robot's direction. If he is currently facing North, his direction is changed to East. If he is currently facing East, his direction is changed to South, if he is currently facing South, his direction is changed to West, and if he is currently facing West, his direction is changed to North. His location is not changed.
  • void turnLeft(). This method also changes the robot's direction to reflect the result of a left turn. His location is not changed.
  • void step(). This method looks at the robot's direction and takes a step in that direction. North will decrement the row number and South will increment it. West will decrement the column number and East will increment it. The direction is not changed.

Test your code (part 1)

Write code that will thoroughly test your program. Your test code will be half of your grade on part 1.

Data Structures: the Stack (part 2)

Use the built-in generic Stack class of the Java Collections Framework to create a stack of Direction. The Stack class has the following methods:

  • E push(E) – a method that pushes the parameter (a Direction in our case) onto the stack. It also returns the item that was pushed on the stack, although you will probably not need this.
  • E pop() – returns an element of the generic type (a Direction in our case) – the top element on the stack.
  • E peek() – returns the top element without actually popping it off of the stack.
  • boolean isEmpty() – returns true if the stack is empty, false otherwise.

Getting rid of backtracking (part 2)

Use your stack to eliminate backtracking by peeking at the top of the stack before pushing a new direction. If the top of the stack is the opposite direction of the direction that you are going, then you are backtracking, and instead of pushing a new direction on the stack, pop the current item off of the stack. For example, if you are preparing to take a step south, and the top of the stack has the value north, you are backtracking, and instead of pushing the south value, pop the north value.

Output (part 2)

You should print out a copy of the maze followed by a list of "instructions" for getting out. Each instruction should be one of the following: North, South, East, or West. Print all of your instructions one per line. Note that the directions that are on the stack will be in reverse order from the way that you want them printed out. There are two possible ways to get the data to print out in the correct order: (1) pop the entire stack contents onto another stack and then pop those elements and print them, (2) use a recursive(!) routine to print the stack items in reverse order.

Assumptions

You may assume that line 1 of the data file will always hold a valid integer (>=3), and that the number on row 2 will always be from 1 to size -2(can't start out in either the east or the west wall!). For example, if the number on the first row is 10, you have a 10x10 array with columns numbered 0 through 9, and the beginning position may be any column from 1 to 8.

You may also assume that all of the remaining data (the x's and blanks) are valid. Your entry point into the maze will be in the bottom row, and your first step will be north (up).

Strategy suggestion

Forget about the stack until everything else is working. Get your robot to walk through the maze with backtracking. When he can get through the maze, then add the stack to remove backtracking.

Since the robot can only turn left, turn right, and take a step, and the maze can only tell us if there is a wall ahead (not to our right or left), the only way our robot can determine if there is a wall to his right is to first turn right, and then ask the maze if there is a wall ahead.

Prog14--CH22.xx--Stack-Maze.docx111/30/2018