CSCI 151 - Lab 3 - Spring 2009 Trapped in a maze!

11:59.59pm, Sunday, March 1

Backstory

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.

Task Description

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.

Classes to create

MyStack
An implementation of a Stack built around a LinkedList that is capable of storing an arbitrarily large amount of data. 
public class MyStack<T> extends LinkedList<T>
You will need to implement the following methods:
push(T data)
Add the element data to the top of the stack
T pop()
Remove the top element from the stack.
Throws a NoSuchElementException if stack is empty (you should just allow the one from LinkedList to pass through)
T top()
Examine the top element on the stack.
Throws a NoSuchElementException if stack is empty (you should just allow the one from LinkedList to pass through)
MyQueue
An implementation of a Queue interface that is capable of storing an arbitrarily large amount of data. This should also be extending a LinkedList as in MyStack.
You will need to implement the following methods:
enqueue(T data)
Add the element data to the back of the queue
T dequeue()
Remove the first element from the queue.
Throws a NoSuchElementException if queue is empty (you should just allow the one from LinkedList to pass through)
T front()
Examine the first element in the queue.
Throws a NoSuchElementException if queue is empty (you should just allow the one from LinkedList to pass through)
MazeSolver
A class that contains the main() method that is used to drive all of the other operations. It will be called from the command line as follows: 
java MazeSolver filename
where "filename" is the name of a file that contains a maze description. See below for a more information.

By extending a Collection class, the classes you create are also collections. This means that you'll have access to all of the standard methods like isEmpty() and size().

Include a main() method in MyStack and MyQueue that performs testing on your data structures. Don't forget to test the exceptions too.

Starting point code

I've supplied starting point code, including the mazes here: lab3.jar

Jesse Bradford created some large mazes you might want to try out once you have your program working: lab3-extra-mazes.zip

Input format

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]. The x-coordinate is going down, and y-coordinates go to the right.

Sample input

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

Output

Your program should present the following output:

  1. After reading in the maze, it should print the maze to System.out using the following notations: 
        _ - empty space
    # - wall
    S - Start
    E - Exit
  2. Next, your program should attempt to find a path through the maze using a stack based implementation. This should be a non-recursive implementation, and should terminate when the first path to the exit is found or it determines that no such path exists.
  3. Your program should then either print out a message indicating that no path through the maze exists or
    1. The length of the path found,
    2. The path as a list of coordinates [i,j] from the start to the exit,
    3. The maze as described above, but with "+" characters on the path used.
  4. Repeat steps 2 and 3 but use a queue for the worklist instead of a stack.

Sample output

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 +'s below:

    _ _ _ _ _ _ # _ _ _ + + + 
    # # _ # # # # # # # + # + 
    _ # _ _ _ _ + + + + + # + 
    _ # _ # # _ + # # # _ # + 
    _ _ _ # _ _ + _ _ # _ # + 
    _ # # # # # + # _ # _ # + 
    _ _ _ _ _ _ S # _ _ # E + 

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 +'s below:

    _ _ _ _ _ _ # _ _ _ + + + 
    # # _ # # # # # # # + # + 
    _ # _ _ _ _ + + + + + # + 
    _ # _ # # _ + # # # _ # + 
    _ _ _ # _ _ + _ _ # _ # + 
    _ # # # # # + # _ # _ # + 
    _ _ _ _ _ _ S # _ _ # E +

Path finding algorithm

You should implement the following algorithm for finding the path

  1. Create an empty stack (later queue) of points to use as a worklist. The worklist represents the set of points that are reachable from the start, but for which the adjacent points haven't been tried yet.
  2. Add the start position to the worklist.
  3. Try to remove a point P from the worklist.
    1. If the list is empty, there is no path to the exit.
    2. If this is the exit, then you've found a path out.
    3. Otherwise, for each valid point Q adjacent to P, add it to the stack and mark it in the maze with a letter indicating the direction from Q back to P. (You might use Up, Down, Left, Right or North, South, East, West.)
    4. Now repeat step 3.
  4. If you've found the exit, you can use the direction letters in the maze to list the points in the path. Create a new stack and then traverse the path in the reverse order, pushing each point onto the stack as you proceed. When you get back to the start, you can then display the path by popping points from the stack and displaying them.
  5. Some of the squares in the maze will have been labeled with a direction letter even though they are not part of the path. You'll either have to clean them up (or print them as empty spaces) before redisplaying the maze.

Programming notes

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.

In the jar file, I've included three classes for you to use. The MyStack and MyQueue classes are for your implementation. The Point class is a subclass of the java.awt.Point with only a change to toString() to make the outpu nicer. A point has an x and y coordinate, both of which are integers. Both are public fields, so you can access them directly.

I've included a number of sample mazes for you to try and included my output to maze-2 and maze-3

Comments

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.

Bonus - Recursive Backtracking

In class we talked about the recursive backtracking strategy. If you have the time, you can try it out on the maze. (Help the third friend Rick Ursive find his way through the maze!) You can use a LinkedList of Point objects to keep track of the path through the maze.

  1. If the start is equal to the end, then the path consists of only one point.
  2. For each unmarked point P adjacent to the start, do the following
    1. Mark it in the maze with a '+' character.
    2. Find a path from P to the exit.
    3. If such a path is found, then add start to the front of the path and return it. Otherwise, unmark P.
    4. If every adjacent point has been tried without finding a solution, return null to indicate that no path exists.

handin

Look through your programs and make sure you've included your name at the top of all of them.

README file

You need to create a file called "README" that contains the following information:

  1. Your name and your partner's name
  2. Any known problems or assumptions made in your classes or program
  3. The Big-O complexity of each of your search algorithms and some explanation as to how you computed it. Be sure you explain what n represents in your Big-O expression.
  4. One or two sentences explaining which version of the search algorithm is "better" and examples of why. If you know it, give the "real name" of each of these algorithms.

Honor code

If you adhered to the honor code in this assignment, add the following statement to your README file:

I have adhered to the Honor Code in this assignment.

handin

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.

Lab Goals

This lab is intended to:

Last Modified: February 21, 2009 - Benjamin A. KupermanVI Powered