CS 201: Data Structures (Spring 2017)

HW04: Maze solver

Due: Monday, 04/17 at 22:00

1. Goals

To use the Stack ADT to solve a maze.

2. Setup

This is a pair programming assignment. Check Moodle for new partner pairings.

The code that you write for this assignment will build on top of two ADTs (List and Stack) and their implementations. Recall that the way Java has dealt with Stacks is rather odd: Stack is a class rather than an interface, and the documentation recommends that you use a Deque instead. Rather than using Java's built-in Stack methods, I've provided you with a Stack interface (Stack.java) and an implementation (CarlStack.class). The stack implementation is just a class file, because you don't need to see how it is implemented in order to use it. For this assignment, you must use the Stack interface and implementation that I have provided; you may not use the built-in Java Stack or Deque. View the Javadoc for CarlStack.

3. Specification

In this assignment, you will build on existing code that I have written in order to solve a maze. Download the starter code for this assignment. My code has most of the implementation of a load method and a method that will print the maze once you complete the load method. The first step in this homework is practicing your code reading skills to understand what I've written. I suggest that before meeting with you partner, you look through the code and the assignment, and then discuss the organization of the code at your first meeting.

The maze file format

Mazes are stored in text files and follow a particular format. We assume that our mazes are rectangular, and that they have walls along the entire outside of the maze, with no gaps in these outer walls. We will also specify a “start square” (S) and a “finish square” (F) to indicate the goal of the maze-solver: to get from S to F.

Maze files should have the following structure:

<Number of columns> <Number of rows>
<0-based column number of the start square> <0-based row number of the start square> 
<0-based column number of the finish square> <0-based row number of the finish square> 
<Row 0 description>
<Row 1 description>
...

Each row description includes a single character for each square in that row, and each character describes the left and bottom walls for its square. Specifically:

• L (letter L) means that the square has both a left wall and a bottom wall
• | (vertical bar or pipe) means that the square has a left wall, but no bottom wall
• _ (underscore) means that the square has a bottom wall, but no left wall
• . (dot) means that the square has neither a bottom wall nor a left wall

Putting this together in a small example, if the input file contains the following:

3 2     [The maze has 3 columns and 2 rows]
0 0     [The start square is at the upper left]
2 0     [The finish square is at the upper right]
L.|     [(0,0) has left and bottom walls; (1,0) has neither left nor bottom; (2,0) has just left]
L__     [(0,1) has left and bottom walls; (1,1) has just bottom; (2,1) has just bottom]

which yields this maze:

+---+---+---+
| S     | F |
+---+   +   +
|           |
+---+---+---+

Note that we specify only the left and bottom walls for each square, and not the top and right walls. This is sufficient to describe the whole maze (why?).

Loading and printing the maze

The first part of the assignment is to finish the load method in Maze.

• Read through what's in Maze and MazeSquare in order to understand how the current code is organized.
• Decide with your partner how you'll be storing the squares of the maze. Modify Maze to include one or more instance variables for storing the squares, and finish the load method. The load method should return false if there are any squares that don't have L, |, _, or . as a descriptor, or the number of squares is inconsistent with the number of rows or columns specified at the beginning of the file.
• Complete the method getMazeSquare. A "stub" for this method is already provided in the Maze file.

Now, you're ready to try out whether your methods function correctly. You'll be loading and printing a maze. Modify main so that with the following command line:

java Maze maze.txt

the file maze.txt is loaded and printed. This should just involve constructing the maze and calling the load and print methods: it requires very little code. (Look in Maze.java for a print method: this method will work correctly once you have a working getMazeSquare method.)

Before you move on, draw a maze on paper, and then make a maze file that represents that maze. Try loading the maze and printing it using the following command:

java Maze <mazeFile>

where <mazeFile> is replaced with the name of your maze file.

Solving the maze

Now it's time to solve the maze using the following algorithm. I'm giving you the steps in prose; your job is to turn them into code. Please use this specific algorithm.

1. Mark every square in the maze as unvisited.
2. Create an empty stack of maze squares.
3. Add the start square to the stack, and mark the start square as visited.
4. If the stack is empty, you're done and the maze is unsolvable.
5. If the top item is the finish square, you're done and the stack contains a solution to the maze.
6. If all squares adjacent to the top item (i.e., the squares up, down, right, or left from the top item; no diagonal adjacency) are either blocked by a wall or are marked visited already, pop the top item from the stack and go to step 4.
7. Otherwise, select a square that is adjacent to the top of the stack, unvisited, and accessible from the top of the stack (no wall between them). Mark this square as visited and push it on the stack. Go to step 4.

You should implement this method in Maze. Specifically:

• Your Maze class must include a method with the following behavior and signature:

  /** Computes and returns a solution to this maze. If there are multiple
      solutions, only one is returned, and getSolution() makes no guarantees
      about which one.  However, the returned solution will not include visits to
      dead ends or any backtracks, even if backtracking occurs during the
      solution process. 
  
      @return a stack of MazeSquare objects containing the sequence of squares
      visited to go from the start square (bottom of the stack) to the finish
      square (top of the stack). If there is no solution, an empty stack is
      returned.
  */
  public Stack<MazeSquare> getSolution()
  

  Note that this method is public, so anyone could call it. You should make sure that it works whenever someone calls it, e.g., if someone calls it twice in a row, it should still work. This algorithm is guaranteed to find a solution if there is one, although it isn't guaranteed to find the shortest solution (we'll learn about an algorithm to find shortest solutions in a few days).
• Your program's command line should follow the syntax:

  java Maze <mazeFile> [--solve]

  For example, if maze.txt is:

  6 5
  0 0
  0 4
  L._|_.
  |L..|_
  |._.|_
  |L|L||
  L__L__
  

  then java Maze maze.txt should print the maze with no solution:

  +---+---+---+---+---+---+
  | S         |           |
  +---+   +---+   +---+   +
  |   |           |       |
  +   +---+   +   +   +---+
  |               |       |
  +   +   +---+   +   +---+
  |   |   |   |   |   |   |
  +   +---+   +---+   +   +
  | F         |           |
  +---+---+---+---+---+---+
  

  However, java Maze maze.txt --solve should print the maze with the path of a solution marked:

  +---+---+---+---+---+---+
  | S   *     |           |
  +---+   +---+   +---+   +
  |   | *   *   * |       |
  +   +---+   +   +   +---+
  | *   *   *   * |       |
  +   +   +---+   +   +---+
  | * |   |   |   |   |   |
  +   +---+   +---+   +   +
  | F         |           |
  +---+---+---+---+---+---+
  

Thus, you'll need to decide how to print a maze solution with the solution marked. Try to avoid duplicating code as much as possible: can you modify my print method so that it can print a maze with or without a solution? If you modify print, make sure that the comment reflects what it does now.

Testing your solver

One of the most important steps in writing code is testing to make sure it works (and debugging it when it doesn't!). We'll talk about testing throughout the term, and many assignments will include a testing component. This is to help you verify that your solution really does work, and is something that I try to do whenever I write code (and that I generally regret if I don't spend enough time on!). For this assignment, you should create several maze files that differ in critical ways (e.g., one requires going left to find the solution, another requires going right). Test your program on these maze files: does it solve all of them? You should create at least 2 maze files, but you may create more: the important thing about tests isn't how many you have but how well the tests cover the space of possibilities. Try to think about situations that you think could cause your code to fail, and create mazes that will tell you whether your code actually fails in that situation.

4. Code notes

• This assignment is more complex than the previous ones, and you should absolutely develop your program incrementally. The outline above already gives you a good starting point, but it may be helpful to break down some of those steps even further.
• You're welcome to make any changes to the starter files that you'd like. You might find it helpful to add methods or variables to MazeSquare, and you'll likely want some helper methods in Maze rather than writing all of your code in one long method, which would be considered bad style.
• When testing your code on different mazes, try to isolate what method might be causing errors: print statements can help with this.
• When testing your code, it's also helpful to walk through it with a maze in front of you. I often draw out on paper what I think is happening in my code (variables, values for those variables, in this case a graphical version of the maze), and that allows me to walk step by step through my code to check whether what I think is true at each point is actually true. Writing things down helps you check your assumptions, and often slows you down enough to recognize mistakes that you wouldn't see if you tried to keep everything in your mind as you read through the code on screen.
• Remember to look back at the style guidelines for how to write understandable and maintainable code. One potential issue on this assignment is having lots of printing code twice: talk with your partner to brainstorm ways to avoid this.

5. Submission and grading

Submit to Moodle a zip archive containing:

• Maze.java,
• MazeSquare.java, if you modified it, and
• the test mazes you created in the final part of the assignment.

Follow the previously established guidelines, such as:

• do not submit .class files, extraneous directories, or unmodifed starter files such as Stack.java,
• zip file naming convention, and
• one submission per pair.

In the future, even if I do not repeat these guidelines, please abide by them whenever they seem applicable.

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work; it does not include expectations about style, which are detailed in the style guide.

• Correct command-line syntax and behaviour (two different possible usages).
• load method returns true and false based on whether the maze file is properly formatted; it should not throw exceptions.
• After load is called, the squares of the maze are stored in some way.
• getSolution works correctly in all circumstances, including:
  • returns a stack of maze squares containing a solution,
  • the solution is correct, with no repeated maze squares,
  • returns an empty stack if no solution is possible,
  • works correctly when called twice in a row, and
  • works correctly under other edge cases you can think of.
• Use the Stack interface and implementation that I provided.

Grading

• Assignment requirements [20 points]
• Comments, style, and design [5 points]

This assignment modified from one designed by Jeff Ondich.

Start early, have fun, and discuss questions on Moodle.