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%).