Assignment 6

Harvey Mudd College
Computer Science 60
Assignment 6, Due Sunday, March 1, by 11:59pm

This assignment is proudly brought to you by Spam, the official canned meat product of CS 60. We strongly recommend that you do the three parts of this assignment in the order presented below. Parts 1 and 2 can be done individually or in pairs. Part 3 is individual only.

A Reminder on Style

Please keep in mind that at this point in the course some of the assignment points will be awarded based on your programs' commenting, formatting, and design -- under the heading of style.

Any readable and well-commented style is OK. These are some of the things to look out for when writing programs for yourself (or others) to read:

Design

For large programs, be sure to design your program on paper before you sit down at the computer. Think about what functions you will want and how they will interact with one another.
Each function should be fairly short and should have a clear "mission". Use helper functions of your own design, as needed or desired. Large, convoluted functions are difficult to read and understand -- more importantly, however, they're very difficult for the original programmer to modify and debug!
Avoid MAGIC VALUES! Recall from lecture that global variables are appropriate in lieu of magic value. However, global variables should otherwise be used only where truly necessary.

Formatting

Please use ample whitespace: blank lines between functions, spaces within expressions to make them readable and separate component parts.
This also includes a clear and clear structure to your code, and indenting that indicates that structure.
You should use meaningful variable and function names. For example, use row rather than r and current rather than c.
You should keep your lines of code to less than 80 characters -- this helps to make it readable from within all kinds of programs, and avoids wrapping issues.

Comments

We ask you to include a top-of-file comment with your name, partner (if any), time spent, and any other comments for the graders (or instructors)
Each function, even your own helper functions, should have at least a short top-of-function comment documenting its purpose, inputs, and outputs.
Comments within functions are welcome, but not required unless something tricky is going on. Many people find them helpful to write because they keep the flow of the program in mind.

Part 1: Spamsweeper (40 Points, Individual or Pair)

First the utterly gratuitous story... You've been hired by Spamsoft, a major software company. Spamsoft would like to implement a "retro" version of the famous Minesweeper game which they call Spamsweeper. (By "retro" we mean that the game will be played on the keyboard and using text-based graphics rather than with a mouse and fancy graphics.)

Spamsoft is a big company, and one division of the company has already developed a few Java classes that will be of useful in your game. However, writing the actual game is your job. (In real software development projects, many people are usually involved and different teams will develop different pieces of the project. Therefore, this part of the assignment exposes you to the idea of using existing classes to write more sophisticated programs.)

The objective of the Spamsweeper game is to safely "defuse" all of the hidden cans of Spam. You will find a compiled version of our game at /cs/cs/60/hwfiles/a6/Spamsweeper.class. You can play the game there by typing java Spamsweeper. If you want to play with a board of different dimensions and different number of spam cans, run java Spamsweeper 4 10 5 which will, for example, construct a board with 4 rows, 10 columns, and 5 cans of spam hidden. At each iteration, you are asked for the row (number) and then column (letter) that you wish to play. Then, you are asked if it is Spam ('s') or free ('f'). If you choose 's' for Spam, there had better be a can of Spam at that location! If so, the cell is exposed and the Spam counter is decremented by one. If not, you lose. If you choose 'f' for free, there had better not be a can of Spam at that location. If there is a can of Spam there, you lose! If not, the cell is exposed. You win when there are no more cans of Spam remaining to find.

To get you started, copy the files Boardcell.java and Gameboard.java from the directory /cs/cs60/hwfiles/a6. These are the classes that have been provided for you by "another team" at the company. In a nutshell, the Boardcell class defines one cell of the board of a game. The cell keeps track of not just whether it is "mined" (i.e. contains a can of Spam) but also whether or not this cell should be exposed to the player (initially all cells are unexposed but they become exposed as the player selects them during the course of the game), and the number of surrounding cells that contain mines (Spam). Please read through these files carefully. Read the comments and the code and make sure that you understand what each class provides. Not only will you use these classes in your game, but some of the implementation ideas in this code will be useful to you in later parts of this assignments.

Note that one method (a function defined inside a class is called a "method") of particular utility is printBoard. This method displays the board for the user, hiding the contents of all of the cells that have not yet been exposed by the player and revealing all of the exposed cells. There is also a cheatPrintBoard method that exposes everything! This is useful when debugging your program. It will be handy for you to know where the Spam is located and what the neighor count values are so that you can see if your program is working correctly.

Your job is to write the Spamsweeper game in a file called Spamsweeper.java. Here are the requirements of the game and the implementation:

You should use the provided Boardcell and Gameboard classes without modification. Spamsoft has invested considerable energy developing and testing those classes and wants them to be used in their games.
The game should have the same functionality as the provided sample in /cs/cs60/hwfiles/a6/Spamsweeper.class. In particular, please make sure to print the current status of the board and the number of spam cans remaining. Similarly, the game should report a win or loss appropriately.
The user should be able to specify the number of rows, columns, and spam cans on the command line (as described above). The user either supplies all three of these values on the command line or none at all. If none at all, then the default values should be a 12x12 board with 20 cans of spam. A documented example of how to get input from the command line is given in /cs/cs60/hwfiles/a6/commandLine.java
You've seen how to read input from the console on Assignment 5. However, a documented example of how to read input from the console and convert the input string to an integer is given in /cs/cs60/hwfiles/a6/input.java
An important part of your game is the "Auto Expose" feature. Here is how it works: If you select a cell and correctly defuse it as Spam or select a non-Spam cell and correctly identify it as "free", that cell should be marked as exposed (recall that the printBoard method only displays the contents of exposed cells). Moreover, if a free cell is exposed and it's neighbor count is 0, we know that none of its neighbors contains Spam. Therefore, there is no information revealed in exposing all of the neighbors of that cell, since the player would have done this her/himself. Each cell will have 8 neighbors in general, but possibly fewer if the cell is at an edge or corner of the board. The program therefore automatically exposes those neighbors. Moreover, if any of those cells are themselves ones with 0 neighbor count, then the automatic exposure recursively continues from there. Use recursion for the auto expose mechanism and try to keep that code as clean and simple as possible. It's possible to implement in just a few lines of code! In particular, try to avoid having a separate line of code for each of the eight possible neighbors that need to be looked at.

Submit your code as Spamsweeper.java. You do not need to submit the Boardcell.java and Gameboard.java files since we will use the ones that we've provided.

Part 2: A Queue Class (20 Points, Individual or Pair)

In this second part of the assignment, you will build a class that defines a queue. This will be used in Part 3 of the assignment to find the shortest path between two points in a maze.

In order to guarantee that your Queue class supports the appropriate Queue capabilities, you should first copy the file /cs/cs60/hwfiles/QueueInterface.java which consists of the following code:

/*
 * 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 was used in our implementation of a stack that we saw 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 private 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.

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:

Write 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 data members set to null since a new queue is empty!
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.

As an aside, you might point out that data is plural, and you'd be entirely correct. Indeed, the input parameter data will hold a good deal of data when it is of type MazeCell in the second part of this assignment.

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 a reference to 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 a reference to the 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.

Testing your code is important! Be sure to test all of your Queue methods using a main method within your Queue class! That main method can make a new queue, do some enqueueing and dequeueing, and use the toString method to print out the contents of the queue to show you that it is working correctly. When we test your queue, 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!

Submit your code as Queue.java. Please include all other classes that the queue needs within Queue.java.

Part 3: A Breadth-First Maze Solver (aka "Spamseeker") (40 Points, Individual Only)

This problem should be done individually. If you worked with a partner on the previous parts, you may use the Queue implementation that you wrote together.

In /cs/cs60/hwfiles/a6 you will find a file called Maze.java. In that file, we have provided two simple classes to get you started:

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?

Please read carefully through the provided Maze.java file. 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!.
You may wish to implement one or more helper functions as well. These should be private since the outside world has no business knowing about them.

What should BFS return?

Nothing! BFS is void, so it may not return a value.

Rather, the idea is that once your search has found the destination, it should have set each cell's parent reference. Before returning our of the BFS method, run a loop to change the contents of the MazeCells on the path from 'D' to 'S' to the lowercase 'o' character.

Note that this means running through the path in reverse (since you'll be following references to parent cells. In addition, remember that the char in Java is a primitive data type. Thus, you can (and should) use == to compare chars.

Some IMPORTANT tips...

Remember that breadth-first search (BFS) uses a queue to keep track of the MazeCells that are waiting to be explored. To support this, you'll need to use your queue implementation from Part 2. The queue will contain references to MazeCells that are waiting to explore their surrounding cells. Initially, the queue will be populated with just one reference - namely to the MazeCell corresponding to the starting element. You'll just enqueue this MazeCell onto your initially empty queue to get started. Then, while the queue is not empty, repeatedly dequeue the next MazeCell to be processed, mark all its non-wall unvisited neighbors, and enqueue them for later consideration!

Do I need to make new MazeCells to enqueue? You could, but this would be messy! Notice that the maze is already made up of MazeCells! Therefore, the queue need not make new MazeCells - it can just keep references to the MazeCells that are already making up the maze!

Notice that your queue implementation can happily enqueue any kind of Object, so it will be happy to enqueue MazeCells in particular! However, consider the following line of code that might appear in your program (assuming that myQueue is the name of a queue that you constructed earlier):


  MazeCell current = myQueue.dequeue()

Java will "object" to this at compile time. Why?! The reason is that the dequeue method in your Queue class is declared as returning an object. Howerver, current is rightfully declared as a MazeCell. Java will complain because not every Object is necessarily a MazeCell. The solution to this is to use "casting" - a technique that we've seen earlier in the semester. Specifically, by changing the above line to:


  MazeCell current = (MazeCell)myQueue.dequeue();

we are telling Java: "Hey, trust me, I know what I'm doing! I put MazeCells into the queue so what's going to come out is not any old Object but actually a MazeCell."

Finally, bear in mind that the perimeter of the maze is not necessarily entirely made of walls. Be careful not to fall of the edge of the maze - this will inevitably cause a null pointer exception error.

Other notes and details...

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 in the directory /cs/cs60/hwfiles/a6 that you can copy and try out!

You need only submit the Maze.java file.

Want More? (15 Point Optional Bonus Problem)

If you want to have more fun with the BFS program, here's an optional bonus problem. There is more thinking here than coding!

Your objective now is to emulate the kind of service that several direction-finding websites provide. Specifically, your breadth-first search should be modified to find the shortest path with the fewest number of turns. That is, among all shortest paths, we want one that turns the fewest number of times. The reason is that paths with fewer turns are easier for humans to follow and are easier to describe.

Specifically, you should make a copy of your Maze.java file and call it MazeBonus.java. (The Maze class inside the file will also need to be renamed to MazeBonus.) This program should take a maze as input and should display a shortest path with the least number of turns. In addition, it should report the length of the trip, the number of turns required, and then give English instructions on how to get from the start to the destination following this shortest path with fewest turns. For example, instructions might look like:

  Trip length:  14 cells
  Number of turns:  2

  Go north 5 cells.
  Turn to the west.
  Go west 6 cells.
  Turn to the south.
  Go south 3 cells.
  You have arrived at your destination.

You may wish to modify some of the code that we've provided in Maze.java. In any case, please test your code carefully to make sure that it really is giving the absolute minimum number of turns among all shortest paths. Of course, your program must still be very fast: We'll test your program with large mazes and allow your program only a couple of seconds to find the solution. Thus, using a brute-force approach will suffice.

Submit this file as MazeBonus.java.