Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Friday, October 6, 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 also 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 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 . You can use the tests individually by copying one of those test files (and the associated Test#.out file containing the correct output) to your directory. Be sure to copy your Queue.java file (or the solution file) to your assignment 5 directory -- you'll need that code! Also, for your Deque class you'll need to first compile the Queue.java file with

javac Queue.java

before deque.java will compile (if you start seeing errors like the following

Deque.java:11: Superclass QCell of class DCell not found.
class DCell extends QCell

it's most likely because Queue.java needs to be compiled.

Once all of the files are in place, testing is identical to that in the previous assignment. Compile with

javac Test#.java

and, if it compiles (it will compile any .java files it needs from your directory, run the test with

java Test#

Don't forget about the shortcuts (aliases) jc, je, and jx.

You can compare the output you see with the expected output in the file Test#.out either visually, by typing

cat Test#.out

or using the unix diff command (see assignment 4 for an explanation on how to use diff).

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 few methods and one constructor. You will need to add more 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.

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 does this. Please be sure to print just that line (and exactly that line), so that the grading program's will know that you've solved (or, rather, not solved) the maze correctly.

Keep in mind that you do need to use a Queue class to implement breadth-first search. Thus, you should either copy your Queue.java code or the solutions in /cs/cs60/as/a5/Queue.java .

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 refer to the data members directly (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 directly, even though they're private. Alternatively, you may certainly write static or nonstatic helper functions, if you want.

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 should be implemented as a derived class of Queue. 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!

You will need to use the DCell (short for "Deque cell") class, which is derived from the QCell class. The DCell class is provided for you in /cs/cs60/as/a5/Deque.examples.

As you start to write your Deque.java file, you will need to extend the Queue class. To do so, the class signature begins

class Deque extends Queue
{

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 with signature
```
       Deque()
       
```
that creates an empty Deque with a null front and back.
A static and nonstatic method enqueue with signatures
```
       void enqueue(Object o)
       static void enqueue(Object o, Deque D)
       
```
that does for a Deque the same thing that it does for a Queue, i.e. place a new DCell at the back of the Deque with the input data.
A static and nonstatic method dequeue with signatures
```
       Object dequeue()
       static Object dequeue(Deque D)
       
```
that does for a Deque the same thing that it does for a Queue, i.e. remove the frontmost cell and return its data.
A static and nonstatic method enqueueFront with signatures
```
       void enqueueFront(Object o)
       static void enqueueFront(Object o, Deque D)
       
```
that enqueues an Object to the Deque in the front, rather than in the back of the list.
A method dequeueBack with signatures
```
       Object dequeueBack()
       static Object dequeueBack(Deque D)
       
```
that dequeues a cell from the back of the Deque and returns its data.

Hint on casting

Because your code will be using the front and back data members of the Deque class inherited from the Queue class, 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;
	   
	      ((DCell)back).prev = null;

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

Other notes

You will not have to rewrite the isEmpty() method, because it works as is just as well for a Deque as for a Queue. Similarly, you will not need to write a toString method for Deque.

As with the Maze class, you can test your Deque class by writing your own main method, or with the Test#.java files in /cs/cs60/as/a5.

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 you started, an applet with all of the components you need (but not the organization of them...) is available at http://www.cs.hmc.edu/~dodds/Applets/ExampleApplet.html . The source code for that applet will be in /cs/cs60/as/a5/ExampleApplet.java .

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, October 6, by midnight