Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Thursday, February 24, 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/a4/Queue.java.sols. 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 Maze.java

and

cs60submit Deque.java

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.

In each case, be sure to input that the assignment number is 5.

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 . In the files Maze.java and Deque.java there are main functions with a number of print statements that will test your Maze code and your Deque code. If your Java code successfully passes all of the tests (matching the output in /cs/cs60/as/a5/Maze.out and /cs/cs60/as/a5/Deque.out), you can feel confident that your code works correctly.

To test your java code, you can simply run it and compare your output with the correct output in either Maze.out or Deque.out. Or, you can let the machine compare the outputs for you with

% java Maze | diff - /cs/cs60/as/a4/Maze.out

% java Deque | diff - /cs/cs60/as/a4/Deque.out

If you see nothing (that is, no "differences" occur), you know your code is producing the correct output. If you do see lines beginning with "<", they are output lines that your program printed , but do not appear in the answers file. Lines beginning with ">" appear in that file, but not your program's output.

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 the file /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 solve the maze.

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.

You will want to use a Queue in your solve method. Thus, copy the code of the Queue class (and the necessary QCell class) into your Maze.java file. Use your Queue solution, if you're confident in it -- you're also free to use the solution in /cs/cs60/as/a4/Queue.java.sols.

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. However, you certainly may 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 enqueuing to the back and dequeuing from the front, like an ordinary Queue, but also allows enqueuing to the front and dequeuing from the back of the linked list of cells.

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.java.

The /cs/cs60/as/a5/Deque.java file contains an implementation of the Queue class (appropriately commented), as well as the DCell class, derived from QCell. You will need to write into the file a Deque class that extends the Queue class. 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 a 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 is_empty() method, because it holds 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 with the main method provided.

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 will be available soon at http://www.cs.hmc.edu/~dodds/Applets/GraphicalMaze.html . 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 will be 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 Thursday, February 24, by midnight