Assignment 5
Type: Individual Assignment
Due: by 9:30 PM on Tuesday, October 9, 2018
Introduction
This assignment is a continuation of the Maze assignment, i.e., Assignment 3. Whereas before, we were just concerned with printing the maze, this time we will be using a stack to actually solve the maze! There are many maze-solving algorithms out there, but in particular you’ll be implementing a stack-based algorithm generally known as depth-first search and a description of the algorithm is included later in the assignment description.
Starter Code
Below is a zip file containing the starter code for the assignment.
You will need a working solution to Assignment 3 before starting the assignment. If you were pleased with your solution to that assignment, feel free to modify it directly! We have also included a sample solution in the zip above, which you are welcome to use as a starting point or for inspiration.
Note: A key piece of the sample solution is the ability to track the presence of all four walls surrounding each MazeSquare
. 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 the sample solution (or at least read through it and see how that extra information is retrieved).
In this assignment, you are not required to implement a stack—instead we provide you with a working implementation named LLStack
. We also include a summary of the Stack ADT it implements in the The LLStack Class section below.
For your convenience, below is a summary of all of the files included in the zip file:
-
Maze.java
- This is the sample solution to the original maze assignment.- The
MazeSquare
class is implemented as a private inner class rather than a public external class.
- The
-
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. Note that not all of these mazes are guaranteed to be solvable.
Depth-First Search
Below we give a description of the depth-first search algorithm you will be implementing in prose.
- Mark every square in the maze as “unvisited.”
- Create an empty stack of MazeSquare objects.
- Push the start square onto the stack, and mark the start square as visited.
- Loop:
- If the stack is empty, then you are done and the maze is unsolvable.
- Otherwise, peek at the top of the stack–let’s call it T.
- 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).
- 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.
- 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
.
Your Assignment
Your assignment is 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 theMazeSquare
class. This should be initialized tofalse
by theMazeSquare
constructor. - Add associated methods
isVisited()
(which checks to see if theMazeSquare
is visited) andvisit()
(which changes the visited instance variable totrue
) to theMazeSquare
class. - Write a helper method to the
Maze
class calledgetNeighbor(MazeSquare s, String direction)
which takes in a givenMazeSquare
and a direction (“left”, “right”, “top”, “bottom”), and returns a reference to theMazeSquare
in that direction in the maze. This will be helpful to have when writinggetSolution()
. - Implement the
getSolution()
method, following the algorithm written above. - Call
getSolution()
in the beginning of theprint()
method, storing the stack it returns in a variable. - For each
MazeSquare
that you print out in theprint()
method, check to see if it is contained in the solution (using theLLStack
’scontains()
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.
Submission and Grading
You’ll submit all your files to your Hand-in
directory under a folder named assignment5
.
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!
- Start early, ask lots of questions, and have fun! The instructor, the lab assistants, and the prefect are all here to help you succeed—don’t hesitate to ask for help!
- Acknowledgments
- This assignment was originally written by Jeff Ondich, with modifications by Eric Alexander and Titus Klinge.