CS 201: Data Structures (Winter 2018)
HW04: Maze solver
Due: Wednesday, 01/24 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
andMazeSquare
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 theload
method. Theload
method should returnfalse
if there are any squares that don't haveL
,|
,_
, 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 theMaze
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.txtthe 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.- Mark every square in the maze as unvisited.
- Create an empty stack of maze squares.
- Add the start square to the stack, and mark the start square as visited.
- If the stack is empty, you're done and the maze is unsolvable.
- If the top item is the finish square, you're done and the stack contains a solution to the maze.
- 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.
- 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, ifmaze.txt
is:6 5 0 0 0 4 L._|_. |L..|_ |._.|_ |L|L|| L__L__
thenjava 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 | | +---+---+---+---+---+---+
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 inMaze
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.
- The
.class
file provided is compiled using Java 8 and you cannot use it with an older version of Java. Please upgrade or use a lab computer.
5. Submission and grading
Submit to Moodle azip
archive containing:
Maze.java
,MazeSquare.java
, if you modified it, and- the test mazes you created in the final part of the assignment.
- do not submit
.class
files, extraneous directories, or unmodifed starter files such asStack.java
, zip
file naming convention, and- one submission per pair.
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 returnstrue
andfalse
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.