Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Monday, February 27, by 11:59pm

"SpamSeeker"

Assignment 5 puts your code in the position of a laboratory mouse, seeking the shortest path from its starting point in a maze to an appropriate destination -- a destination containing, perhaps, a can of spam...! Reaching the spam by the shortest possible path will require implementing breadth-first search (BFS), as well as a Queue to help with that search algorithm.

Thus, the first part of this assignment is to create and test a Queue class -- using the class discussion and the example of Stack.java as a guide. Once your Queue is working, the second part of the assignment will ask you to use that information structure in the task of maze-solving.

Both parts of this assignment may be done individually or with a partner. If you choose to work with a partner, you should work with the same partner on both parts of the assignment, though you may choose to do part 1 with a partner and part 2 on your own, if you like. (Doing part 1 individually and part 2 with a partner is also possible, but more difficult because part 2 builds on part 1).

Submitting your code

For this assignment, you should submit two files under assignment #5:

Queue.java and
Maze.java

Problem 1. A `Queue` class (individual or pair)

50 points

This problem's task is to write a java class named Queue that implements a closed linked list that supports the standard Queue operations. Recall that a Queue is a list in which data are added (enqueued) at the "back" and removed (dequeued) from the "front."

In order to guarantee that your Queue class supports the appropriate Queue capabilities, you should make sure to download the file QueueInterface.java which consists of the following interface:

  /*
 * QueueInterface.java 
 *
 * provides an generic interface for all of the functions
 * a Queue of T's should implement.
 *
 * That is, if a class implements the interface
 * QueueInterface, it can then be used
 * as a queue of T's...
 */

interface QueueInterface
{
  public boolean isEmpty();
  public T       peek();
  public T       dequeue();
  public void    enqueue( T data );
  public String  toString();
}

Then, as you define your Queue class, you should declare that it will implement this interface, as follows:

class Queue<T extends Object> 
   extends Object
   implements QueueInterface<T>
{
  ... rest of the Queue class here ...
}

This technique uses the compiler to make sure that your code adheres to the contract set forth by the QueueInterface. A similar example is used in Stack.java, in which the Stack<T> class implements StackInterface<T>.

More generally, you might want to use Stack as a good starting place for your Queue class. The source code for Stack and StackInterface is given, and we have covered both in class.

Inner class: QCell

Similar to the way in which the Stack class used an inner class named StackCell, Your Queue.java file might use an inner QCell class that will be the type of each cell in your Queue.

Data members for Queue

The Queue class itself should have two data members:


  private QCell front; // the front of the Queue object - cells are removed from here
  private QCell back;  // the back of the Queue object - cells are added to here

Format to use for toString

In order to make testing your Queue class as uniform as possible, we ask that you use the following format for your toString method. Notice that <FRONT> and <BACK> always are printed, and <FRONT> always has a single space after it. When elements are present, they are printed from front-to-back, each with a single space after it, including the final element. <BACK>, however, does not have a space following it.

Feel free to use the toString method in Stack.java as a guide... (it's very similar):

printing an empty queue: <FRONT> <BACK>
printing a queue whose elements are the Strings a, b, and c: <FRONT> a b c <BACK>

What to include in your Queue<T> class:

Do use the QCell class in order to hold data. Your Queue class will be a linked list of QCells.

Write a toString method as described above so that you can test your code with System.out.println statements in main.

Write a zero-argument constructor with signature
```
       public Queue() 
```
This constructor should return an empty Queue, with both the front and back being null. Feel free to write other constructors if you'd like, but you do not need to.

Write a nonstatic method, enqueue. The method signature should be
```
       void enqueue(T data)       
```
This should appropriately add the data (first putting it within a QCell!) to the invoking Queue. You might point out that data is plural, and you'd be correct! In fact, the input parameter data will hold a good deal of data when of type MazeCell.

Write a nonstatic method dequeue. The method signature should be
```
       T dequeue()
```
This method should return null if dequeue is called by an empty Queue; otherwise, dequeue should remove the next QCell from the invoking Queue object and return the piece of data that QCell contained.

Write a nonstatic method peek. The method signature should be
```
       T peek()
```
This method should return null if it is called by an empty Queue; otherwise, peek should return the piece of data contained in the front QCell without altering the calling Queue at all.

Write a nonstatic method isEmpty with signature
```
       boolean isEmpty() {...}
```
that returns true when the invoking Queue is empty, and false otherwise.

Also, be sure to test all of your Queue methods using the main method within your Queue class! We will definitely add three or four elements to a Queue and then remove them all (and even one more!), printing the Queue after each time. Then, our tests will add several elements again. Be sure your Queue can handle this situation... there are a couple of tricky things that happen when adding the first element or removing the last one!

Problem 2. A `Maze` solver (individual or pair)

50 points

In the Maze.java file in the top-level assignment directory, you will find two classes:

MazeCell: This is an inner class representing one cell of a Maze. A MazeCell has a number of data members and a few methods and one constructor.

Maze: This class represents a maze, i.e., a two-dimensional, always rectangular array of MazeCells. The class has a couple of methods already implemented -- for reading in a maze from a file and for finding the starting 'S' and destination 'D' MazeCells.

What is already in Maze?

The Maze class has a method for reading a maze from a file. The format of the file should be something like this


6 10
**********
*S*      *
* *      *
*    **  *
*    *D  *
**********

where the first line has the height and width of the maze, and the subsequent lines contain the maze itself, as characters, with the asterisk '*' representing the walls, spaces are free space, and letters are special free space: 'S' is the start, and 'D' is the destination for the maze.

The Maze class also has a toString method, a method named findMazeCell that will return a MazeCell that is holding a particular character (S or D, usually), and a main method for testing.

What needs to be implemented?

The method that needs to be implemented is

   public void BFS(MazeCell start, MazeCell destination)

This BFS method does not need to return a value (it can't, in fact). However, it needs to either

find a shortest solution to the maze by breadth-first search and then add lowercase-o characters 'o' to indicate the path between the start and destination OR
realize the maze is unsolvable and announce that fact by printing Maze not solvable!.

We will discuss the BFS algorithm, along with a related algorithm called depth-first-search, in class to help guide your implementation. It will follow that you'll need to create a Queue<MazeCell> object to guide your search.

Notes and details...

The Maze class loads its mazes by taking their filenames as command line arguments. To pass command line arguments in Dr. Java compile your code in Dr. Java and then instead of pressing the Run button, in the interactions window type:

java Maze test0.maze

(where you can replace test0.maze with any of the maze files)

Here is what the Maze shown in the example above might look like when printed after calling BFS:


**********
*S*      *
*o* oooo *
*oooo**o *
*    *Do *
**********

There certainly may be more than one shortest path (a tie for shortest). For example, this is equally valid:


**********
*S*      *
*o*ooooo *
*ooo **o *
*    *Do *
**********

And, again, if there is no path from start to destination, please print out the statement Maze not solvable! and do not change what the maze will look like when printed.

There are several mazes on the top-level assignments page to try out... .

Optional Extra Credit: Maze-solving on a sphere

For completely voluntary bonus credit (up to +5 points), change your Maze class to handle mazes that do not necessarily have walls all around their outermost edge. In fact, you should interpret any edge as being connected to the corresponding "wrap-around" edge of the maze. This may lead to even shorter paths! For example, this is test4.maze, and is only slightly altered from above:


******** *
 S*       
* *      *
*    **  *
*    *D  *
******** *

but now the shortest path is potentially very different, wrapping around twice...


********o*
oS*     oo
* *      *
*    **  *
*    *Doo*
********o*

Another shortest path wraps only once, in the case that our mouse looks south before north.

Harvey Mudd College Computer Science 60 Assignment 5, Due Monday, February 27, by 11:59pm