HW5: Mazes Part 2 [PAIR]

HW5: Mazes Part 2 [PAIR]
This assignment should be done with the pairs I assigned you, or alone if you elected to go
that route. It is worth 16 points, and is due at 1 PM on Wednesday, February 7.
The setup
The intended starting point for this assignment is a working solution to the Maze: Part I
assignment. If you were pleased with your solution to that assignment, I encourage you to
modify it directly! I have also included my solution, which you are welcome to use as a
starting point, or inspiration.
Note: A key piece of this solution to Part I is the ability to store all of the walls of
each MazeSquare in the MazeSquare class. If you only included the left and bottom walls
in your implementation (or if you only included the associated string character), then you
may want to use my implementation (or at least read through it and see how that extra
information is retrieved).
The problem
Whereas before, you were just concerned with printing the maze, this time you will be
using a stack to solve it! There are many maze-solving algorithms out there, but in
particular you'll be implmenting a stack-based algorithm generally known as "depth-first
search."
Here is the algorithm (in prose):
1. Mark every square in the maze as "unvisited."
2. Create an empty stack of MazeSquare objects.
3. Push the start square onto the stack, and mark the start square as visited.
4. Loop:
i. If the stack is empty, then you are done and the maze is unsolvable.
ii. Otherwise, peek at the top of the stack--let's call it T.
iii. If T is the finish square, then you are done and the stack contains a solution
to the maze (with the start square at the bottom of the stack and the finish
square at the top).
iv. If all of the squares that are adjacent to T in the maze (i.e., the squares up,
down, left, or right from T--no diagonals) are either blocked by a wall or have
already been marked as visited, pop T off of the stack and continue on.
v. Else, select a square that is adjacent to T, unvisited, and not blocked by a
wall. Mark it as visited and push it on to the stack.
The LLStack class
The stack implementation you'll be using for this assignment is given to you in the zip file.
It is called LLStack (for "linked list stack"), and allows you to create stacks with the
following methods:
Method Return
type Description
push(E item) void Add a given item to top of stack
peek() E Return the item at the top of the stack (without removing
it).
pop() E Return and remove the item at the top of the stack.
size() int Return the number of items in the queue.
isEmpty() boolean Return whether or not the queue has no items.
contains(E
item) boolean Return whether or not the stack contains the given item.
Note: the contains() method will be particularly useful when you want to decide
whether or not to print a * character for a given MazeSquare.
What you'll need to do
You need to modify Maze.java to support solving mazes using the above algorithm, and
printing the solved version. Specifically, you need to add a method to Maze.java with the
following 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 LLStack 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).
*/
public LLStack<MazeSquare getSolution()
This method should then be called by the print() method so that each square in the
maze that is part of the solution is marked with *. For example, if the following is input
as maze.txt:
6 5
0 0
0 4
L-_|_-
|L--|_
|-_-|_
|L|L||
L__L__
Then the following should be print out to the console:
+-----+-----+-----+-----+-----+-----+
| | |
| S * | |
| | |
+-----+ +-----+ +-----+ +
| | | |
| | * * * | |
| | | |
+ +-----+ + + +-----+
| | |
| * * * * | |
| | |
+ + +-----+ + +-----+
| | | | | | |
| * | | | | | |
| | | | | | |
+ +-----+ +-----+ + +
| | |
| F | |
| | |
+-----+-----+-----+-----+-----+-----+
Apart from these constraints, and the requirement that you use the algorithm specified
above, how you implement this is up to you! However, here are the steps I might consider
taking:
• Add a visited instance variable to the MazeSquare class. This should be
initialized to false by the MazeSquare constructor.
• Add associated methods isVisited() (which checks to see if the MazeSquare is
visited) and visit() (which changes the visited instance variable to true) to
the MazeSquare class.
• Write a helper method to the Maze class called getNeighbor(MazeSquare s,
String direction) which takes in a given MazeSquare and a direction ("left",
"right", "top", "bottom"), and returns a reference to the MazeSquare in that
direction in the maze. This will be helpful to have when writing getSolution().
• Implement the getSolution() method, following the algorithm written above.
• Call getSolution() in the beginning of the print() method, storing the stack it
returns in a variable.
• For each MazeSquare that you print out in the print() method, check to see if it
is contained in the solution (using the LLStack's contains() method). If it is, then
write a * character in the middle.
There are other ways to go about solving this problem, but I believe that the above steps
will be a good way of approaching it.
Files included
There are a few files that are included to help you with this assignment:
• Maze.java - This is my solution to the original maze assignment. You can use it as
a starting point for this assignment if you would like.
• LLStack.java - This is the stack class that you will use to carry out the above
stack algorithm. You should not need to edit this code at all. Rather, you should
be able to simply rely on the methods described in the ADT.
• maze1.txt, maze2.txt, maze3.txt, maze4.txt - These are sample maze files
that you can use to test. You may want to make some of your own, as these aren't
the only files I'll be testing on. Not all of these mazes are guaranteed to be
solvable.
Submission and Grading
You'll submit all your files to Moodle as a zipped file. One one partner from each pair
needs to submit the assignment. Specifically, put these files into a directory
named [your\_last\_name\_your\_partner's\_last\_name]HW5, zip this
directory, upload it to Moodle.
This assignment is worth 16 points. Below is a partial list of the things that we'll look for
when evaluating your work.
• Does your program print out a correct solution to a given maze?
• Are you able to handle mazes that have no solution (by drawing them without a
solution marked)?
• Do you properly implement the stack algorithm to return a solution to the maze?
• How efficient is your code? Are you looping unnecessarily through the stack data
structure, or are you making good use of its constant-time operations?
• Do your classes exhibit good organization and commenting? Don't forget to follow
the Style Guidelines on Moodle.
Start early, ask lots of questions, and have fun! Eric, the lab assistants, and the prefect are
all here to help you succeed - don't hesitate to ask for help!