11:59.59pm, Sunday, March 2
Jesse Bradford created some large mazes you might want to try out: lab3-extra-mazes.zip
Two good friends, Susie Queue and Hay Stack, found themselves trapped in an underground cavern. They need to find their way out of the cave, or determine if an exit is impossible so that they can radio for help.
Despite being the best of friends, Susie and Hay disagree on how they should look for the exit. Hay thinks that they should keep track of their path using a list of possible paths and always using the most recently seen ones first, while Susie thinks that they should also keep a list of possible paths but should use the ones seen earliest first.
They decide to go their own ways and plan to meet up at the exit. Having studied computer science, they know that both methods should eventually reach the exit if it is possible.
For this assignment you will be writing a program that is capable of solving a maze using two different algorithms -- one using a Stack and one using a Queue.
You will be creating a class MazeSolver that will find a path from the start to the exit of a maze using both a Stack and a Queue ADT to store the worklist (the list of paths to try).
You will also need to create a file called "README" that contains some answers to the questions listed below.
java MazeSolver filename
Methods are specified in the interface files supplied. Be sure to throw the correct exceptions.
Include a main() method in MyStack and MyLinkedQueue that performs testing on your data structures. Don't forget to test the exceptions too.
I've supplied starting point code, including the mazes here: lab3.jar
The maze files have the following format. The first line of the file contains two integers. The first indicates the number of rows (R), the second, the number of columns (C).
The rest of the file will be R rows of C integers. The value of the integers will be as follows:
0 - an empty space
1 - a wall
2 - where Susie and Hay start
3 - the exit
If you encounter a problem while reading in the file, you should print out a message and exit (System.exit() will quit your program).
In terms of coordinates, consider the upper left corner to be position [0,0] and the lower right to be [R-1,C-1].
Also in maze-2
7 13 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 2 1 0 0 1 3 0
Your program should present the following output:
_ - empty space
# - wall
S - Start
E - Exit
Also in maze-2.output
The maze to solve is:
---------------------
_ _ _ _ _ _ # _ _ _ _ _ _
# # _ # # # # # # # _ # _
_ # _ _ _ _ _ _ _ _ _ # _
_ # _ # # _ _ # # # _ # _
_ _ _ # _ _ _ _ _ # _ # _
_ # # # # # _ # _ # _ # _
_ _ _ _ _ _ S # _ _ # E _
Solving with a stack:
---------------------
Found a path of length 20:
[ 6, 6] -> [ 5, 6] -> [ 4, 6] -> [ 3, 6] -> [ 2, 6] ->
[ 2, 7] -> [ 2, 8] -> [ 2, 9] -> [ 2,10] -> [ 1,10] ->
[ 0,10] -> [ 0,11] -> [ 0,12] -> [ 1,12] -> [ 2,12] ->
[ 3,12] -> [ 4,12] -> [ 5,12] -> [ 6,12] -> [ 6,11]
The path is shown by X's below:
_ _ _ _ _ _ # _ _ _ X X X
# # _ # # # # # # # X # X
_ # _ _ _ _ X X X X X # X
_ # _ # # _ X # # # _ # X
_ _ _ # _ _ X _ _ # _ # X
_ # # # # # X # _ # _ # X
_ _ _ _ _ _ S # _ _ # E X
Solving with a queue:
---------------------
Found a path of length 20:
[ 6, 6] -> [ 5, 6] -> [ 4, 6] -> [ 3, 6] -> [ 2, 6] ->
[ 2, 7] -> [ 2, 8] -> [ 2, 9] -> [ 2,10] -> [ 1,10] ->
[ 0,10] -> [ 0,11] -> [ 0,12] -> [ 1,12] -> [ 2,12] ->
[ 3,12] -> [ 4,12] -> [ 5,12] -> [ 6,12] -> [ 6,11]
The path is shown by X's below:
_ _ _ _ _ _ # _ _ _ X X X
# # _ # # # # # # # X # X
_ # _ _ _ _ X X X X X # X
_ # _ # # _ X # # # _ # X
_ _ _ # _ _ X _ _ # _ # X
_ # # # # # X # _ # _ # X
_ _ _ _ _ _ S # _ _ # E X
You should implement the following algorithm for finding the path
You should first check to see that the user supplied an argument on the command line. The parameter "args" in the main method is where all command line arguments are passed.
You then should read in the maze from that file. I would suggest using a pair of Scanner objects to do so. Be sure to catch the exception that is raised if the user specifies an incorrect file and print out an appropriate error message when this occurs. Don't just let the program crash dumping the stack trace to the user.
For the LinkedQueue implementation, you might want to make a protected class to handle the nodes. You don't need to create a separate file to do this, instead just have the class description in the same file as MyLinkedQueue but without the "public" modifier.
I've included a number of sample mazes for you to try and included my output to maze-2 and maze-3
You should be using Javadoc style comments in your programs. You don't need to generate the HTML output, but you do need to be writing them.
You'll note that you need to keep track of the path that was followed. This seems to be a difficult proposition. However, there is a technique we can use to approach this.
In order to keep from wandering in a circle, you need to "mark" each square before you move into it. (I recommend doing this whenever you add it into the worklist.) Imagine if you were to mark it by putting an arrow in that square that points back to the square from which you added it to the worklist. (Might want to store the current location as part of the arrow too.) Then, when you are at the exit, you can just follow the arrows back to the start. You'll need to store these arrows someplace, and probably need one per square, so it might need to be the same shape and size as the maze itself.
Of course, following the arrows gives you the path in reverse order. If only you had a way to keep track of items such that the Last item In was the First item Out, then you could read all the arrows in one pass and write them back out in the correct order.
Don't forget to erase your arrows between Susie and Hay's attempts on the maze. You can always just pretend that they write with different colored chalk.
Look through your programs and make sure you've included your name at the top of all of them.
You need to create a file called "README" that contains the following information:
If you adhered to the honor code in this assignment, add the following statement to your README file:
I affirm that I have adhered to the Honor Code in this assignment.
You now just need to electronically handin all your files. Assignment is 3.
Don't forget to run lshand and verify that things were submitted.
This lab is intended to: