Project 2 - The search for a-MAZE-ing donuts!

IIIa. Phase A: DFS and BFS

Your task for Phase A is to implement a stack, a queue, a depth-first search maze runner and a breadth-first search maze runner, according to the interfaces provided. Your data structure implementations should automatically grow (if interested you may also make them shrink—this is optional) as necessary. You should test these implementations to be sure they are correct before proceeding to Phase B. We'll also ask you to design and implement a collection of unit tests to verify that your code works properly.

Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution; if you use arrays, try to come up with a more time-efficient solution. You may reuse any code you wrote for Project #1 for this purpose but be sure that you implement the interfaces provided for this project.

You are free to implement the stacks and queues as you wish, although arrays are as simple as anything. Our usual rule prohibiting use of the Java class libraries to do the actual work remains. You should also take this opportunity to get an understanding of how the three graph search algorithms described here work for a general graph.

You should also implement unit tests for your data structures and verify that your code passes the tests. You should turn in a TESTING.txt file with an informal description of your test plan. Summarize the tests you implemented and explain how they provide comprehensive test coverage for your classes. This should not just be a dump of the test names and comments from the code file—we can read that. What we want is to get an idea of the thinking behind what you did. We recommend use of JUnit, but this is not a requirement. The testing strategy you discuss in TESTING.txt will be evaluated as a part of the project, but the code of your actual unit tests will not.

IIIb. Phase B: Priority Queues and Best-First Search

For Phase B you will write several implementations of the Priority Queue ADT and a best-first search maze runner to use them. Specifically, you will write a binary heap, a three heap, a d-heap, and a pointer-based heap (one of: skew heap, leftist heap, or binomial queue). You will also need to modify MazeRunnerLauncher.java to accept command line arguments appropriate for each type of maze runner or priority queue. Finally, you'll need to answer the questions from the write-up and turn them in in README.txt.

All of this is more work than it sounds, so do not leave it to the last minute.

IVa. Clarifications

• In your implementations of Queue and PriorityQueue, you should throw a NoSuchElementException (java.util.NoSuchElementException) if dequeue, peek, findMin, or deleteMin are called on an empty queue. Obviously, this means it's OK to import java.util.NoSuchElementException in your code.

• Your d-heap class should implement the PriorityQueue interface.
• When writing your additional pointer-based implementation (either a LeftistHeap or a SkewHeap or a BinomialQueue) of a PriorityQueue, do not use implementations of these that you may find on any web site - including the web site for our text book! Such use will be considered a violation of our collaboration policy. You are free to refer to skeleton code provided in our text book or in other course materials; however, the code you turn in should be your own.

• Your priority queue implementations must accept Comparable objects.

  Many classes such as String and Integer implement the Comparable interface. In Phase B you will need to modify/create some more classes that implement the Comparable interface (in other words, writing your own compareTo method). Then you will be able to have priority queues containing those objects. Unlike your stacks implementations for Project1 that were hardcoded to use doubles, your implementations of the Stack, Queue, and PriorityQueue interface need to use generics. Your implementations need to use compareTo when comparing elements so the code will work on any Comparable object. More information about Java's Comparable interface may be found at Sun's website. In addition, you might find this description from CSE 143 of Fall 2006 to be useful. Both generics and the Comparable interface are discussed in section 1.5 of the Weiss text, and there is a good tutorial on Sun's web site. The tutorial is based on this paper by Gilad Bracha, one of the Java language designers.

IVb. Input and Output

INPUT:

• You are required towrite MazeRunner classes for BFS, DFS, and BestFS. Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which search algorithm to use:

  	-BFS	use BFS
  	-DFS	use DFS
  	-BestFS	use BestFS

• You should assure that all of your PriorityQueue implementations work with MazeRunner.  Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which priority queue implementation to use when needed:  

  	-bin	use Binary Heap
  	-three	use Three Heap
  	-dheap #	use a d-heap, where d = #
  	-ptr	use your pointer-based heap (Leftist, Skew or Binomial)

• The MazeFactory class reads a maze from a text file specified on the command prompt. The file format is a picture of the maze. There is also some header information at the front that gives the dimensions of the maze (width, then height). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the start, and 'O' for the donut. (Note: start and donut can be in any cells in the maze, not just the corners.) Once you find the donut, you get to chow down and then exit out of the maze. For example, the following is a legal maze : 

                  7 5
                  +-+-+-+-+-+-+-+
                  |*|   | | |   |
                  + +-+ + + +-+ +
                  |   |   |     |
                  + + + +-+ +-+ +
                  | |   |     | |
                  + +-+-+ +-+-+ +
                  |       |     |
                  +-+ + +-+-+ +-+
                  |   |        O|
                  +-+-+-+-+-+-+-+
              
  

There are some sample input files in the starter files mentioned above that you can use to test your program. You are highly encouraged to write (and share with your classmates!) other test mazes to run your MazeRunner on. Send them to us or post them on the message board (preferred).

OUTPUT:

After solving a maze, your MazeRunner should output the name of the search algorithm used followed by the solution path calculated by the search. The path should be given on a single line and should consist of the printed cells from the start to the exit, separated by single spaces. On the next line should be the length of the solution path, and on the following line should be the number of cells visited in the search, including cells that were not completely explored (i.e., marked "Visit in progress" when the search completes).  For example, the output for the above maze might be:

                Random search:
                (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (5,4) (6,4)
                Length of path: 10
                Number of cells visited: 15
            

Please note that the start and end cells are both included, but the length of the path is the number of edges traversed ( one less than the number of cells visited). Please do not include extraneous output. For the other search algorithms, use text "Breadth-first search:", "Depth-first search:" and "Best-first search:".

The solution displayed above corresponds to the solution path shown below with dots:

                +-+-+-+-+-+-+-+
                |*|   | | |   |
                + +-+ + + +-+ +
                |.  |   |     |
                + + + +-+ +-+ +
                |.|   |     | |
                + +-+-+ +-+-+ +
                |. . .  |     |
                +-+ + +-+-+ +-+
                |   |. . . . O|
                +-+-+-+-+-+-+-+
            

Note that your MazeRunner does not need to output a text-graphical solution such as the one displayed above.

Note also that a search very likely involves visiting many nodes that are not on the final solution path. You will have to explore ways of keeping track of the solution path from the collection of nodes you visited. RandomMazeRunner gives an example of how this might be done. You will need to modify this technique to work for your algorithms.

IVc. README.txt Questions

Your README.txt should contain the following information and answer the following questions:

1. The names of your team members and your team's name
2. A breakdown of the work - a brief who-did-what description.
3. How much time did you spend on this project?
4. Acknowledgement of any assistance you received from anyone but your partner, the course staff, or the Weiss book.
5. Did you do any extra credit?  If so, describe what you did and give instructions on how to run your code.
6. Why is it more important for DFS than BFS to check whether a cell has been visited yet?
7. If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster, BFS or DFS? (Any reasonable answer—as long as it is justified—will be accepted.)
8. In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
9. Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
10. Why is BFS guaranteed to find the shortest path? Are the other two algorithms guaranteed to find the shortest path? If yes say why, if not, give a counter example.
11. What are the tradeoffs between a pointer vs. array-based heap? In particular, what are the tradeoffs between a binary heap, a threeheap, and a pointer-based heap? Some possible topics to cover include runtime, coding complexity, and memory usage. Did you observe any differences (for example in runtimes or memory use) between using these three for the larger maze inputs?  (Just note if you noticed anything, it is fine if you did not.  You are welcome to explore this question in more detail (timings, measurements, calculations) for extra credit.)
12. In general (not necessarily in the context of this project), why could it be better to use a sorted array implementation of a priority queue versus a binary heap? Why could it be worse?
13. What did you enjoy about this assignment? What did you hate? Could we have done anything better?

IVd. Grading Breakdown

The amount of code required for this project is actually very small. A significant part of your grade will be based on your program design and your README.txt.

• Correctness - 40%
• Architecture/design - 30%
• README.txt - 30%

Look at the course grading policy for a more detailed explanation on grading guidelines.

       % java MazeRunnerLauncher -r sample-inputs/maze2.txt