Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Friday, March 1, 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, i.e., a can of spam (with full acknowledgements for this concept to Ran L.-Hadas). To reach the spam by the shortest possible path will require implementing breadth-first search, as well as some helper functions to enable the search.

To implement BFS you will need to use the Queue class you wrote for assignment 4. (If you would like, you can use the solution Queue class in the file /cs/cs60/as/a5/Queue.java.) The other half of this assignment will be to extend your Queue class into a Deque (double-ended queue) class. This will serve as an introduction to inheritance, which is used extensively in Java's AWT (Abstract Windowing Toolkit) library. The extra credit problem this week involves creating a graphical (applet) representation of the maze-solver. Assignment 6 will focus on graphics programming in Java.

Submitting your code

For this assignment, you will need to create two files, named Maze.java and Deque.java.

To submit the files, you will need to run

cs60submit Maze.java
cs60submit Deque.java

As usual, you'll need to indicate that this is assignment #5. Be sure your files are named as indicated above, because our scripts that sort the files into appropriate places will depend on that name to determine which file you are submitting.

Reading

This assignment continues through the book's Chapter 7. As in the previous assignment, Chapter 6 is not necessary. Also, most of the material needed to do this assignment will be presented in class.

Testing your code

Test cases for each of the (two) classes you're writing in this assignment appear in the directory /cs/cs60/as/a5 . As usual, they're named Test#.java . Tests 1-10 are for the Maze class; Tests 11-20 are for the Deque class.

There are no .out files for the Maze tests! This is because there are several different shortest paths for many mazes, so printing one correct solution would be misleading -- there are actually lots. We will check the output of these tests by eye (and you should also...).

For the Deque tests, there are Test#.out files for comparing your outputs, as in previous assignments. See the "Testing your code" section of assignment 4 for complete instructions on using the test files.

Be sure to include your Queue class in your Deque.java and your Maze.java files, so that it will be available when we grade each of these! (They both require the Queue class.)

The Problems (again, only two of them...)

1. A solver for the `Maze` class

In the /cs/cs60/as/a5/Maze.java file, you will find two classes:

MazeCell: This class has a number of data members and a constructor already -- you will need to add "setter and getter" methods that access the data members in appropriate ways. Because they're declared private you will not be able to directly access MazeCell's datamembers from within your Maze class.
Maze: This class is a data structure of a maze, i.e., a two-dimensional array of MazeCells. The class is complete except for one nonstatic method, solve, with the following signature:
```
       void solve()
       
```
Thus, solve needs no arguments and returns no value. What it does is find a shortest path (there may be more than 1) from the start to the goal, using breadth-first search. Then, it changes the contents of the MazeCells along that path (except the start and the spam) to asterisks ('*').

The Maze class already has a toString method and an empty solve method. In addition, it reads the description of a maze from an array of strings. You can compile and run /cs/cs60/as/a5/Maze.java to get a sense of what the mazes look like. The critical features are
- The walls of the maze are represented by one of two different characters: the vertical bar '|' or the hyphen '-' .
- The starting point of the maze is represented by the character 'S' .
- The finishing point of the maze -- that is, the can of spam -- is represented by the character 'X' .
You will need to use these facts as you write your maze-solving code inside the solve method.

Output

Your task is to write solve so that it finds one of the shortest paths from the start ('S') to the spam ('X') within the maze. It must change the path from blank spaces to asterisks ('*'). Thus, suppose the initial maze looks like

    |--------|
    |   |    |
    | S |  | |
    |   |X | |
    |   |--| |
    |  |   | |
    |  |   | |
    |  | --| |
    |        |
    |--------|

After the solve method is run, one possible correct output is

    |--------|
    |   |****|
    | S |* |*|
    | * |X |*|
    | * |--|*|
    | *|   |*|
    | *|   |*|
    | *| --|*|
    | *******|
    |--------|

Notes and Hints

If there is no path from the start to the spam, your solve method should recognize this fact and print the message

Maze not solvable!

The ouchMaze example (see the Maze.java file) tests this.

Typically, a Queue is used to implement breadth-first search. If you use your Queue class, be sure to paste the code into your Maze.java file. You can also use the code in /cs/cs60/as/a5/Queue.java or copied from the solution posted on the assignments page.

You will need to add methods to the MazeCell class in order to access/change the data members of each maze cell. Feel free to add any public methods you'd like, but do not change the access level of the data members (keep them private).

Since you're writing solve as a method of the Maze class, you should feel free to use Maze's data members explicitly, even though they're private.

2. Deque: a "kind-of" a Queue

For this problem, you will need to implement a Deque data structure. Deque is short for "Double-ended queue," and since a Deque is a kind of a Queue, this data structure can be implemented as a derived class of Queue as an introduction to class inheritance.

Basically, a Deque allows adding elements (enqueuing) to the back and removing elements (dequeuing) from the front, like an ordinary Queue, but also allows enqueuing to the front and dequeuing from the back!

To implement a Deque as a derived class from Queue, you will need to use a DCell (short for "Deque cell") class, which is derived from the QCell class. The DCell class and a start of the Deque class is provided for you in /cs/cs60/as/a5/Deque.java.

As you start to write your Deque.java file, you will need to extend the Queue class. To do so, the class signature begins as follows (but there's more, too -- see the following paragraph):

class Deque extends Queue

Guaranteeing a full deque!

Because users of your Deque class want to feel assured that it implements all of the functionality they might expect from a double-ended queue, it is important that your Deque implement the following interface:

/*
 * file: DequeInterface.java
 *
 * A set of methods that a Deque must implement to
 *   ensure that it has all the expected capabilities
 *   of a double-ended queue.
 */

interface DequeInterface
{
  public boolean isEmpty();
  public Object peekFront();
  public Object peekBack();
  public void enqueue(Object o);
  public void enqueueFront(Object o);
  public Object dequeue();
  public Object dequeueBack();
}

These methods are more fully described below. Your Deque class will thus have a complete signature that looks like the following (already in Deque.java):

class Deque extends Queue implements DequeInterface
{
  ...

Does it have to be implemented that way?

In fact, no. You may implement your Deque however you like, but it does need to implement DequeInterface as shown above.

In addition, your Deque class should have the static methods corresponding to the nonstatic ones listed in the interface (DequeInterface), above.

All Deque methods

Your `Deque` class should have

No additional data members. The Queue class has a reference to a front and a back QCell. The Deque doesn't need more than these two references.
A constructor that creates an empty Deque (with a null front and back). It should have signature
```
       public Deque()
       
```
A static and nonstatic method enqueue that does for a Deque the same thing that it does for a Queue, i.e., they place a new DCell, containing the input data o, at the back of the Deque. The signatures:
```
       public void enqueue(Object o)
       public static void enqueue(Object o, Deque D)
       
```
A static and nonstatic method dequeue that does for a Deque the same thing that it does for a Queue, i.e. remove the frontmost cell and return its data. If the Deque is empty, this method should print an error message and return null. The signatures:
```
       public Object dequeue()
       public static Object dequeue(Deque D)
       
```
A static and nonstatic method enqueueFront that enqueues an Object to the Deque in the front, rather than in the back of the list. The signatures:
```
       public void enqueueFront(Object o)
       public static void enqueueFront(Object o, Deque D)
       
```
A method dequeueBack that dequeues a cell from the back of the Deque and returns its data. If the Deque is empty, this method should print an error message and return null. The signatures:
```
       public Object dequeueBack()
       public static Object dequeueBack(Deque D)
       
```
A method isEmpty that indicates whether a deque is empty or not. Note that by using inheritance, you need not write this method at all! The signatures:
```
       public boolean isEmpty()
       public static boolean isEmpty(Deque D)
       
```
A method peekFront that does not change the deque at all. Rather, it simply returns the data at the front of the deque (to "peek" at it). If the Deque is empty, this method should print an error message and return null. The signatures:
```
       public Object peekFront()
       public static Object peekFront(Deque D)
       
```
A method peekBack that does not change the deque at all. Rather, it simply returns the data at the back of the deque (to "peek" at it). If the Deque is empty, this method should print an error message and return null. The signatures:
```
       public Object peekBack()
       public static Object peekBack(Deque D)
       
```

Hint on casting

When inheriting from Queue, your code will be using the front and back data members of the Deque class inherited from the Queue class. In doing so, remember that the compiler thinks they are QCells, not DCells. Thus, whenever you use front.prev or back.prev, you'll have to cast front or back to a DCell. For example,

 
	      ((DCell)front).prev = null; // or = some other DCell
	   
	      ((DCell)back).prev = null;  // or = some other DCell

You won't have to do this with front.data or front.next, since "data" and "next" are fields in the QCell class.

3. The Graphical SpamSeeker (Extra Credit)

For completely voluntary bonus credit (up to 20% or more...), write an applet that displays the mazes -- both before and after they are solved -- from the Maze class used in Problem 1.

In particular, for the usual extra credit, you can adapt the file ExampleApplet.java in /cs/cs60/as/a5 so that

The applet user can choose the maze to display, either using a pop-up menu or a text box that names the maze.
The applet should be able to display a maze of size up to 30 rows by 40 columns. (A good size for each square in the MazeCell array is 10 pixels by 10 pixels.)
The user can solve the maze by pushing a "solve" button. The solution should be displayed in the applet.
The applet should display the length of the shortest solution to the maze somewhere in the visible window.
The user should somehow be able to clear the solution, perhaps with a "Reset" button.

An example of one possible implementation is available at http://www.cs.hmc.edu/~dodds/Applets/ . However, you should feel free to design your own display and layout.

To get started, you should copy the files /cs/cs60/as/a5/ExampleApplet.* to your public_html directory, which is your own webspace on turing. To do this, go to public_html and then copy and set permissions:

cd ~/public_html
cp /cs/cs60/as/a5/ExampleApplet* .
chmod 644 ./ExampleApplet*

Then, compile the code with

javac ExampleApplet.java

You will have created an applet viewable from any (Java-supporting) browser at

  http://www.cs.hmc.edu/~<yourloginname>/ExampleApplet.html

You can then alter the ExampleApplet.html code to solve mazes... . The ExampleApplet.java code has all of the components you need (but not the organization of them...)

If you are interested in using mouse interactions in your applet, you may add the capability to change the maze by clicking/dragging the mouse over walls to add/remove them. This (or any other custom features of your own choosing) can be added for additional credit (or, if you prefer, simply for fun).

Harvey Mudd College Computer Science 60 Assignment 5, Due Friday, March 1, by midnight