Lab: Mazes
When posted, download StackQueueMonster.java if you dare! It tests ArrayStack, LLQueue, and getBottom (but not solving mazes).
When posted, download maze4.txt and MazeMonster.java to check off your completed lab.
Download mazelab.zip, which contains all the files you will need for this assignment. Complete the following exercises to earn 90%.
Reference
Stack<E> Interface
void push(E obj) // adds obj to top of stack
E pop() // removes element from top of stack and returns it (precondition: stack is not empty)
E peek() // returns element at top of stack (precondition: stack is not empty)
boolean isEmpty()
Queue<E> Interface
void enqueue(E obj) // adds obj to back of queue
E dequeue() // removes element from front of queue and returns it (precondition: queue is not empty)
E peek() // returns element at front of queue (precondition: queue is not empty)
boolean isEmpty()
Location Class
Location(int row, int col)
int getRow()
int getCol()
boolean equals(Object otherLocation)
java.awt.Color Class
Color(int red, int green, int blue) // 0 - 255
int getRed()
int getGreen()
int getBlue()
boolean equals(Object otherColor)
GridDisplay Class
GridDisplay(int numRows, int numCols) // top-left corner is row 0, column 0
int getNumRows()
int getNumCols()
Color getColor(Location loc)
void setColor(Location loc, Color color)
static void pause(int milliseconds)
// some other methods in GridDisplay you will probably not use
boolean isValid(Location loc)
void setTitle(String title)
String getImage(Location loc) //null if empty
void setImage(Location loc, String image) // null to remove image
Exercise 1: ArrayStack
Take a look at the Stack interface defined in Stack.java. Now open ArrayStack.java, which will implement the Stack interface. When an ArrayStack is constructed, no arguments are provided, and the ArrayStack is initially empty. Inside, ArrayStack stores its data values in an ArrayList. Complete the ArrayStack class so that it correctly implements a stack whose methods all run in constant time. (Note that we can add to and remove from the end of an ArrayList in constant time. On the other hand, adding to and removing from the beginning of an ArrayList requires linear time. Given that, which end of the ArrayList should correspond to the top of the stack?)
Exercise 2: LLQueue
Take a look at the Queue interface defined in Queue.java. Now open LLQueue.java, which will implement the Queue interface. When an LLQueue is constructed, no arguments are provided, and the LLQueue is initially empty. Inside, LLQueue stores its data values in a linked list, and maintains a reference to both the first and last ListNodes in that list.
(What does an LLQueue look like when it has only 1 element? What does an an LLQueue look like when it has no elements?)
Complete the LLQueue class so that it correctly implements a queue whose methods all run in constant time. (Which node should correspond to the front of the queue?)
Exercise 3: getBottom
Open Maze.java. Complete the getBottom method, which takes in a non-empty Stack and returns the element that appears at the bottom of the Stack. For example, if Stack s contains [A, B, C], with C at the top of the Stack, then getBottom(s) returns A, and s still contains [A, B, C] (with C at the top) when getBottom returns. (In your code, you may construct another Stack, but you cannot construct any other data structure.)
Exercise 4: solveRecursive
Open Maze.java. Compile it and run the main method. You will see a maze appear on the screen.
Now look at the code for the main method. The first line loads a maze into a GridDisplay object:
GridDisplay grid = load("maze1.txt");
Notice the Color constants defined at the top of the file. The maze's path is drawn in PATH_COLOR while the walls of the maze are drawn in WALL_COLOR.
After loading the maze, the main method calls solveRecursive to solve the maze starting from location (1, 1). Right now, the solveRecursive method does nothing. You must complete the solveRecursive method so that it uses recursion to solve the maze. (You cannot use any for- or while-loops.) For this assignment, "solving" the maze means changing the color of all squares that are connected by a path to the starting location. Here's how:
1. Write if.
2. Handle the simplest case: Do nothing if the color of the given location does not match PATH_COLOR.
3. Write the recursive calls: You will need four recursive calls--one for each of the four directions (up, down, left, right). However, you'll need to make the problem slightly simpler before making any recursive calls, and that means you'll first need to change the color of the given location to VISIT_COLOR. Also call GridDisplay's pause method immediately after changing the color. (This will slow your code down so you can watch it solve the maze.)
4. Assume the recursive calls work: How do they help you? They solve the maze from each neighboring square, and so there's nothing left for you to do!
Test that your code can solve maze1.txt. Now try solving maze2.txt and maze3.txt. Yes, your correct code will crash when solving a bigger maze. That is ok. (But why does that happen?)
Exercise 5: solveStack
It may be hard to imagine how we can solve a maze without the power of four recursive calls. And yet, our code crashed, and thus recursion let us down.
Here's an algorithm for solving a maze without recursion. It maintains a collection of places called toVisit containing the places in the maze that the algorithm plans to visit.
Complete the solveStack method, which must use this algorithm to solve the maze. Store the places to visit in an ArrayStack. Your code should solve the maze starting from location (1, 1).
Test that you can use solveStack to solve all three test mazes, including maze3.txt.
Exercise 6: solveQueue
Now use the same algorithm to complete the solveQueue method, but this time store the places to visit in an LLQueue.
Test that you can use solveQueue to solve the test mazes. Be sure to slow your code down enough so that you can see that it's solving the maze in a fundamentally different order than solveRecursive or solveStack. (How would you describe the behavior of solveQueue?)
Additional Credit
Here are some suggestions you might explore to earn additional credit (above 90%).
Modify solveStack and solveQueue so that they use a gradient instead of a solid color when visiting squares. The chosen color should depend on when the square was visited. For example, if you decide to make a gradient from blue to red, then the top left square would be blue, and the last square reached would be red, and all the squares in the middle would be some shade of violet.
Write a solve method that uses an ArrayList instead of a stack or queue. Your method should always remove the location that is closest to the end of the maze (bottom-right corner). For example, suppose your ArrayList contains [(7, 14), (11, 13), (8, 19)] and the bottom-right corner is (19, 19). Then you would measure the Euclidean distance from each Location in the ArrayList to (19, 19). For example, the distance from (7, 14) to (19, 19) is 13--the square root of (19 - 7)² + (19 - 14)². Because the distance from (11, 13) to the bottom-right corner is lower than the distance for any other point int the ArrayList, you would remove (11, 13) from the ArrayList and visit it.
Write a solve method that uses two stacks to solve the maze from the top-left corner and bottom-right corner at the same time (using two different colors), and stops as soon as the two paths meet.
Make a copy of solveQueue and modify it to show the shortest path from the start to the finish (bottom-right corner).
Hint: Maintain a 2-D array so that array[row][col] contains the location visited immediately before (row, col) on the shortest path from (1, 1) to (row, col). Here's how that array might appear after running the algorithm on a simple maze:
Write a method that takes in a number of rows and columns and returns a GridDisplay with those dimensions containing a randomly generated maze. Here's how. First fill the entire grid with walls. Then begin the path from the finish (the bottom-right corner, not including the very edge of the grid). Repeatedly extend the path in a random direction until you reach a dead end (i.e. you can't extend it any further without connecting to the existing path and creating a loop). In that case, backtrack along the path (toward the finish) until you reach a square that allows you to extend the path again in a random direction. You'll need to maintain a Stack of the squares along the path from the finish to the current square, with the current square on top.
For example, the top-left picture below shows the initial state of a sample run. We have already changed the bottom-right corner (3, 5) to be path color, and we pushed (3, 5) onto an empty stack. The top of the stack tells us we're currently looking at (3, 5). We now consider the 4 neighboring squares that are 2 spaces away: (1, 5), (3, 3), (3, 7), and (5, 5). Only 2 of these are valid locations of walls. Of those 2, we randomly choose (3, 3). We change both (3, 3) and (3, 4) to be path color and we push (3, 3) onto the stack. In the second picture (below the first), the top of the stack tells us we're currently looking at (3, 3). We now consider the 4 neighboring squares that are 2 spaces away: (1, 3), (3, 1), (3, 5), and (5, 3). Only 2 of these are valid locations of walls. Of those 2, we randomly choose (1, 3). We change both (1, 3) and (2, 3) to be path color and we push (1, 3) onto the stack. We eventually reach the situation shown in the fourth picture (top right). Here, there are no valid locations of walls 2 spaces away from (1, 5). We therefore simply pop (1, 5) off the stack. In the fifth picture, the top of the stack tells us we're currently looking at (1, 3) again. Only one of its neighbors is now a valid location of a wall, and so we must visit (1, 1) next.