Assignment 5

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

"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 create a Deque (double-ended queue) class. This will serve as an introduction to interfaces, which are 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 appears as on the left. Then on the right is one possible correct output from the solve method.

    |--------|                             |--------|
    |   |    |                             |   |****|
    | S |  | |                             | S |* |*|
    |   |X | |                             | * |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: implementing `DequeInterface`

For this problem, you will need to implement a Deque data structure. Deque is short for "Double-ended queue," that is, a linked list in which elements can be inserted and removed at both ends.

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, along with the static methods you will also need, are more fully described below. Depending on how you implemented your Queue, you may be able to use inheritance to implement Deque. The file /cs/cs60/as/a5/Deque.java provides a start in that direction. However, you may implement your Deque class in any way you'd like, as long as its methods meet the following specifications:

All Deque methods

Your `Deque` class should have

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)
       
```

3. Using Inheritance (Extra Credit)

A Deque can be viewed as a specialization of a Queue (since a Deque adds more functionality to that possessed by a Queue). Thus use of inheritance is possible. It is also possible to use inheritance in the construction of a Deque: If a Queue is constructed from a QCell, then a Deque can be constructed from a DCell, a cell in a doubly-linked list. A DCell can inherit from a QCell, because it extends the functionality of the latter. Extra credit is offered if you implement the inheritance form of the solution. Keep in mind that this is an exercise; it is not necessarily suggested that you would tend to use inheritance at this level in actual practice.

4. The Graphical SpamSeeker (More 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