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

• Part 1 may be done individually or in pairs - it's entirely up to you.
• Parts 2 and 3 are to be done only individually.

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 instance variables (data members) are appropriate in lieu of magic value. However, you should keep the number of these variables as small as possible.
• 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 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 on the top-level assignment page. 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. The game is won when there are no more cans of Spam remaining to find.

To get you started, download the files Boardcell.java and Gameboard.java from the main assignment page. 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 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 commandLine.java on the main page.
• You've seen how to read input from the console in class. However, a documented example of how to read input from the console and convert the input string to an integer is given in 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.
• As one possible way to implement this "auto expose" feature, consider creating a helper method in your Spamsweeper class that implements the recursive depth-first search for "exposable" cells. One possible signature for such a method would be

      public static void expose( int row, int col, Gameboard GB )
    

  In this case, the Gameboard, GB, is needed so that this method can access the neighbors!

Part 2: A Queue Class (30 Points, Individual only)

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 QueueInterface.java file from the main assignment page 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();
}

class Queue implements QueueInterface
{
  ... rest of the Queue class here ...

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

For uniformity of display, please use the following code for the toString method in your Queue class:

{
  String result = "<FRONT> ";           // making the order explicit
  QCell current = this.front;
  while (current != null)
  {
    result += "" + current.data + " ";
    current = current.next;
  }
  result += "<BACK>";                   // we've reached the back
  return result;
}

• 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:

• Include the toString method as described above.  This will be useful for debugging your code.



• Write a nonstatic equals method with the following signature:
  
         public boolean equals( Object o )
  
  This method should return true if o is a Queue object with the same contents (in the same order) as the calling Queue object.  You should assume that each of the objects in the Queue have implemented their own .equals methods correctly (i.e, you should use .equals to compare objects within the Queues).
  


• 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 your Queue class thoroughly: write a main method that creates a Queue object and then calls all of your methods on it, printing the results to ensure that your data structure is working correctly. You'll probably want to include tests at several points in the enqueuing and dequing process.

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!). 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!

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

This problem should be done individually.

In the provided MazeFiles.zip file you will find a file called Maze.java. In that file, we have provided two 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  *
**********

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)
   

1. 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
2. realize the maze is unsolvable and announce that fact by printing Maze not solvable!.
3. 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()

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

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 *
**********

**********
*S*      *
*o*ooooo *
*ooo **o *
*    *Do *
**********

Want More? (10 Point Optional Bonus Problem, Individual)

If you'd like to extend your maze-soler's behavior, consider adding a wrap-around capability that can pass through one side of the maze and come out the other (the topology of a donut).

This can be done by modifying your basic BFS method (though you should make sure not to break that functionality!)

Here is an example:

10 10
* ******  
*        *
*        *
*  *******
***      *
 S*       
***   ****
*     *D *
*     *   
* ******* 

10 10
*o******oo
*oooooooo*
*        *
*  *******
***      *
oS*ooooooo
***o  ****
*ooo  *Do*
*o    * oo
*o*******o

Even More? (10 Point Optional Bonus Problem, Pair or Individual)

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 not suffice (in fact, you'll more likely run out of memory before running out of patience...!).

Still Want More? (Up to 15 point optional bonus problem, Pair or Individual)

Getting the applet compiling, running, recompiling, and rerunning

Make sure that you can compile the provided "starter" applet with javac *.java. There are two ways to test your applet. (Appletviewer) You can run appletviewer SpamsweeperApplet.html from the directory containing your code, or (browser) you could use a new tab in an open browser and choose "Open ... File" from the menu. Choose the local copy of SpamsweeperApplet.html from the folder in which you just compiled. The applet should start in either case.

Getting debugging information from the Java console

If you're using appletviewer, the print statements in your code will appear in the terminal window from which you started the viewer.

If you're using a browser, in order to see output from print statements (or any errors), you should open the Java console. On the PC, this can be done by right-clicking the little Java icon from the lower right of your screen and choosing "Open Console." On the Mac, you may need to go a bit further. Some browsers have a menu option that simply states "Java Console." Other require you to activate the console first: go to "Applications - Utilities - Java - J2SE 5.0 (or your version) - Java Preferences," and then go to the "Advanced" tab, the "Java Console" options, and select "Show Console." You may need to restart your browser or at least reload the page after this sequence of commands.

If you run into troubles with these low-level details, please seek help -- they're not worth spending much time over. But it is important to be able to debug your code through print statements... .

Making sure you get the NEW applet after making changes

If you're using a browser, you can make sure you get the NEW applet to which you've made changes (do remember to recomplile, too!) by typing an 'x' in the Java Console window. It's also a good idea to clear the window so that you know which output is from the latest run of your applet. Then, when you hit the "Reload" button in the browser, the new applet should be loaded and run. The appletviewer should always reload the most recent version.  If you are having trouble, try quitting and restarting your browser.  This should ensure that you get the new applet.

Writing the applet

• Be sure to create, in init and/or in reset, a Gameboard and make sure it is in a suitable starting configuration. We have provided code that will create a default gameboard, but you may want to change this to allow custom sizing.  


• Draw the contents of the Gameboard within the drawEnvironment method already provided. This will require writing a nested loop to create the 2d array of pixel squares that represent the board. This drawEnvironment method will be called every time the user clicks the mouse. You can represent hidden squares, marked squares, and exposed squares using colors, images or text.  It's up to you.  But make sure that each type of square is clear.  See the examples for how to display each type of object.
  
  
• Most of the work will be done in the mouseClicked function.  In this function you need to figure out what square the user clicked, whether it's a left click (free square) or a right click (spam), and take the appropriate action.  If the user exposes a free cell with no neighboring spam, your program should expose all surrounding cells, recursively, just like in part 1.  The basic functionality of how to work with mouse events is demonstrated in the provided code.
  
  
• You'll need to detect a win or a loss and display the appropriate message (and board) to the user.  You should probably expose all the cells regardless of a win or a loss, but it should be clear if the user has won or lost.

As you write your code, please compile and rerun the applet often to make sure you're on the right path. Use the appletviewer (or a web browser with a Java Console) to help with debugging and error-detection. Basically, this means many iterations of the compilation, copying, and testing steps above.

Submitting your code