Project 2 Clarifications

• You are allowed to import java.io.PrintWriter (the MazeRunner interface takes a PrintWriter as an argument) and java.util.Iterator (needed if you use getNeigbors() from the Maze class).
• You are not required to use exactly the general search algorithm we posted, although you ARE required to use a stack for DFS, a queue for BFS, and a priority queue for Best first search. Note that you are using a stack in DFS, which basically simulates what you would get from the program stack if you used recursion - so you don't need both!
• If you implement your stack and queue using arrays then you may run into some trouble as you try to allocate an array of E. In fact you cannot just create a new E or array of E! Something like this WON'T work:

  E[ ] stuff = new E[MAX]; // Won't work.

  Instead use this:

  E[ ] stuff = (E[ ]) new Object[MAX]; 

  This will give you an unchecked cast warning, but that is o.k.

• The pop method for the Stack interface differs from what we had for Project 1. In this case it removes the top value without returning it. You are likely to encounter both ways of implementing pop. Note that top() still returns the value, so you should be able to accomplish the same thing as pop did in Project 1 by calling both pop and top.
• When you find the donut, you have found the exit. (The donut IS the exit.)
• We will assume that a maze can be as small as two cells (one for the start and one for the donut), but no smaller.

  Posted Feb 1:

• You can assume that each maze has one start and one donut, and that the donut is reachable from the start.
• For Part A you will turn in a TESTING.txt that describes your testing for the stack and queue. For Part B you will need to turn in a TESTING.txt that describes your testing for your priority queue implementations. The text file should be a summary of what you did for your testing in English. *Please also turn in your testing code for Part A and Part B for reference.* We won't be running or grading your testing code for style etc., so don't worry whether or not the file is perfectly commented, includes commented out code, etc.
• Finding the donut with DFS or BFS is part of what you need to do for this assignment. Printing out the solution path is really another problem to solve. While you must use the specified data structure for BFS (queue) and DFS (stack). You can use any data structure(s) you would like for printing out the solution path.
• You are not required to use JUnit for testing. If you would like to use JUnit, I have posted a few resources on the lectures page for Jan 28th that may be useful.
• Your BFS and DFS algorithms should print both the length of the solution path (remember that the path length is one less than the number of cells in the path) and on the following line should be the number of cells visited in the search. Cells visited means any cell that you "processed" in any way - either by completely exploring its neighbors or by merely adding it to the data structure in question (stack or queue) without ever removing it. Note that a cell should not be counted more than once in this total! (e.g. a 5 by 4 maze has a total of 20 cells, so the number of cells visited should never be more than 20.) For the random maze runner, it is possible to visit a cell more than once. Be sure that you do not count a cell more than once for your BFS/DFS/BestFS. *DO* count both the start cell and the donut cell in this count.
• Folks have been sharing some results on the message board. Here are a couple of results for comparison that should help clarify what is meant by length of path and cells visited. For maze1.txt:

  DFS search:
  (0,0) (1,0) (2,0) (3,0) (3,1) (3,2) (2,2) 
  Length of path: 6
  Number of cells visited: 16
  BFS search:
  (0,0) (0,1) (0,2) (1,2) (2,2) 
  Length of path: 4
  Number of cells visited: 14
  

  For bigmaze2.txt:

  DFS search:
  (0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (5,1) (5,0) (6,0) (6,1) (7,1) (8,1) 
  (8,2) (7,2) (7,3) (8,3) (9,3) (9,4) (8,4) (7,4) (7,5) (6,5) (6,6) (7,6) 
  (7,7) (7,8) (7,9) (8,9) (8,8) (9,8) (9,9) (9,10) (9,11) (8,11) (8,12) 
  (8,13) (9,13) (9,14) (9,15) (8,15) (8,16) (7,16) (7,17) (8,17) (8,18) 
  (8,19) (8,20) (9,20) (9,21) (9,22) (9,23) (9,24) (9,25) (9,26) (8,26) 
  (8,27) (8,28) (9,28) (9,29) 
  Length of path: 58
  Number of cells visited: 100
  BFS search:
  (0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (1,5) (1,6) (1,7) (2,7) (3,7) (3,8) 
  (3,9) (3,10) (3,11) (3,12) (2,12) (2,13) (3,13) (3,14) (3,15) (2,15) (2,16) 
  (2,17) (2,18) (3,18) (3,19) (3,20) (3,21) (4,21) (4,22) (5,22) (6,22) (6,23) 
  (6,24) (6,25) (6,26) (6,27) (6,28) (7,28) (7,29) (8,29) (9,29) 
  Length of path: 42
  Number of cells visited: 300
  

• Remember MazeRunnerLauncher options like -t to help you debug your searches.
• Phase A is due Feb 1st at 11pm. What you turn in at this point will be graded and worth 15% of your grade. Your entire project, parts A and B, will be graded when you turn in part B. In effect, this is a second chance at getting part A right, if you discover something wrong after you turn it in for phase A. However, as there is much work to do for phase B (and many fun extra credit options to consider!), we strongly encourage you to get phase all parts of phase A working NOW. Please remember to turn in all parts required for phase A including TESTING.txt and your testing code.

  Posted Mon Feb 8:

• Generics and Comparable: You can look at the example of the BinaryHeap in our text book (p. 204):

  public class BinaryHeap <E extends Comparable<? super E>> 

  then also the example on p. 212 of a constructor that allocates an array of Comparable:

  array = (E[]) new Comparable[MAX_SIZE];

• It is o.k. to use your d-heap/call your d-heap code inside of your binary and three heap code. Just be sure you actually have files named BinaryHeap and ThreeHeap and that you can create BinaryHeap and ThreeHeap objects directly (like by calling new BinaryHeap... etc.).
• It is reasonable to assume that the user will not pass an incredibly large value to your d-heap constructor. (It is always a good idea to check for invalid parameters, but you can assume that we will be giving well-formed input parameters to your MazeRunnerLauncher.)

  Posted Wed Feb 10:

• It is o.k. to assume that when we call MazeRunnerLauncher we will only pass valid arguments in an expected order. The reason we specified the parameters in the assignment was to make our testing easier. I don't want to have to describe in detail what should happen for every case of invalid input, nor do I want you to be spending lots of time trying to make a bombproof MazeRunnerLauncher - there are lots more interesting things for you to spend your time on for this assignment!
• Reminder to turn in your TESTING.txt file for part B, in addition to your testing code. If you have gone back and done different or more testing of your stack and queue feel free to include that in your TESTING.txt you turn in for part B.
• Basically for Part B you should turn in ALL files needed for all 3 maze runners (BFS, DFS, BestFS). This means turning in files you submitted for Part A as well as any new files. Please submit your copy of any files we gave you that you modified. If you don't turn a file in, we will use the version of it that we gave you initially. It is fine to bundle up all of this code into a single zip file, just give it a different name than extracredit.zip