Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Monday, October 10, by midnight

"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 interface for all of the funtions
 * a Queue should implement
 *
 * If a class implements this interface, it can
 * then be used as a Queue...
 */

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

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

class Queue implements QueueInterface
{
  ... 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 use in Stack.java, in which the Stack class implements StackInterface.

More generally, you might want to use Stack as a good starting place for your Queue class. The source code for Stack and StackInterface are available, and we will cover/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 class:

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

Writa 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(Object 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
```
       Object 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
```
       Object 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.

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 ompile 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 *
**********

The difference would be that, in the latter example, the maze-solving "mouse" searches North before searching East; in the former example, the opposite is true.

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 and NEWS

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.

NEWS option...

For additional completely optional extra credit (of +10 points), implement the capabiility to input a command-line parameter that takes, after the maze's filename, a String whose characters are a permutation of NEWS. Then, when searching for the Maze's goal, your code should pursue neighbors in the order of the characters in that input string.

For example, if you were to run


>  java Maze test4.maze SEWN

then the result should be


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

On the other hand, a command-line input of NEWS would yield the original results shown further above.

Harvey Mudd College Computer Science 60 Assignment 5, Due Monday, October 10, by midnight