Assignment 4: Deques ("Decks"), Rex, and a Minefield of Spam!
Due Monday, February 13 by 11:59 PM.

Please start this assignment early. It is fun and challenging! This assignment is definitely a step up in challenge from the last assignment. Parts 1 and 3 of the assignment are based on Wednesday's lecture. Part 2 (the rex part) is based on Friday's lecture.

First, a few words on the mini macs in the Beckman CS lab: The mini macs and turing share files. This means that any file that you create on turing is accessible on the mini macs and vice versa. That's nice, because it means that you can do your java programming on the macs (which are very fast). However there are a few things that you must be aware of:

• You must be logged on to turing to use cs60submit or cs60submitall. However, once you log on to turing, the files that were created on the macs are already there and ready to be submitted. Pretty sweet!
• Although the macs share files with turing, they do not share rex (or some other languages such as prolog). To use those languages, you must be logged onto turing.

And now back to this week's assignment!

Part1: Playing with a Full Deque! (30 Points)

In this part of the assignment you will have a chance to use inheritance and polymorphism to build a deque. You'll use this deque to build your Spampede game in Assignment 5 next week.

First, we have provided some files for you which you will find in the directory /cs/cs60/assignments/assignment4/Deque. Copy all of these files into your own directory.

One of these files is Queue.java, a fully-functioning implementation of a polymorphic queue using linked lists. You do not need to modify this file. Notice that the polymorphism simply allows the queue to contain any Object. The Node class used by this queue is at the top of the Queue.java file. (Java permits multiple classes to be defined in the same file.) You'll notice that this Queue class has some of it's methods renamed from the usual names. Specifically, dequeue has been renamed dequeueFront and enqueue has been renamed enqueueBack. There is also a method called peekFront which returns the element at the front of the queue without removing it.

Your mission is to implement a polymorphic double-ended queue, or "deque". A deque is like a queue except that data can be inserted (enqueued) at the front or at the end and, similarly, data can be deleted (dequeued) from the front or end. Your deque will be polymorphic: It will be able to deal with any types of objects. Since a deque is an abstract data type, it must implement a provided DequeADT interface which you will find in the file /cs/cs60/assignments/assignment4/Deque/DequeADT.java which looks like this:

// DequeADT.java

// A set of methods that a Deque must implement to
// ensure that it has all the expected capabilities
// and a few special capabilities as well!

interface DequeADT
{
  public Object dequeueFront();        // Also in Queue
  public Object dequeueBack();         // New!  Remove element at back

  public void enqueueFront(Object o);  // New!  Add element to front
  public void enqueueBack(Object o);   // Also in Queue

  public Object peekFront();           // Also in Queue
  public Object peekBack();            // New!  Return element at back

  public Object peek2Front();          // New!  Return 2nd to front element
  public Object peek2Back();           // New!  Return 2nd to back element

  public boolean isEmpty();            // Also in Queue
  public String toString();            // A good thing to have

  public void reverse();               // New!  Reverse the order of elements
}

Here are the details of the Deque methods you need to implement this week:

• A constructor that creates an empty Deque (with a null head and tail). It should have signature:

         public Deque()
         

• Methods dequeueFront and dequeueBack that remove one DNode from your Deque from the appropriate side. They also return the Object that had been stored in the removed node. The signatures:

         public Object dequeueFront()
         public Object dequeueBack()
         

• Methods enqueueFront and enqueueBack that add one DNode to your Deque in the appropriate direction: they create and link a new cell containing the input data o. The signatures:

         public void enqueueFront(Object o)
         public void enqueueBack(Object o)
         

• Methods peekFront and peekBack that do not remove any DNodes from your Deque, but simply "peek" into the appropriate one and return its contents. If the deque is empty, these methods should return null. The signatures:

         public Object peekFront()
         public Object peekBack()
         

• Methods peek2Front and peek2Back that do not remove any DNodes from your Deque, but simply "peek" into the appropriate one (second from the front or second from the back, respectively) and return its contents. If the deque has fewer than two nodes, these methods should return null. The signatures:

         public Object peek2Front()
         public Object peek2Back()
         

• Methods isEmpty and toString that return appropriate information! The signatures:

         public boolean isEmpty()
         public String toString()
         

• The method reverse should change the Deque that calls it, so that the elements are in the opposite order than they were before the call. There are many ways to do this; try to keep your code as simple and elegant as possible. The signature:

         public void reverse()
         

Inheritance:   Even though there are eight methods in the above DequeADT interface, you will not have to implement all of them! The reason for this is that you are provided a Queue class (in Queue.java). Since a deque is a kind of queue, you will use inheritance so that your Deque class extends the capabilities of the existing Queue class.

What about Node?   Inside the provided Queue.java file, there is a Node class that implements a singly-linked list node. Because your Deque class will require doubly-linked list nodes, we will need to create a DNode class, which extends and inherits from the Node class. The start of both the Deque and DNode classes are available in the file Deque.java.

• Copy all of the files from /cs/cs60/assignments/assignment4/Deque to the directory in which you're working.


• The only file you will need to change is Deque.java, which will include both the Deque and the DNode classes. Please do not modify the file Queue.java.


• You may use any code that we wrote in class.


• For full credit, keep your code as simple and clean as possible. In particular, do not reimplement a method in Deque if you can inherit the implementation from Queue. Even if you can't inherent the entire method, try to invoke Queue methods where possible to minimize the amount of new code that must be written in Deque.


• There is a file for testing your Deque class named DequeTest.java. Be sure your Deque passes those tests, but also realize that our final testing will be even more thorough. Writing your own testers is an important part of programming.

Submission   The easiest way to submit is to send us all of your .java files with the command

  >  cs60submitall

Problem 2: Playing with Rex! (10 points)

In this (very short) part of the assignment, you will have a chance to write some rex functions! (Remember, you must be logged onto turing to use rex.)

On turing, type rex at the prompt to enter the rex interpreter. You can exit rex at any time by pressing CTRL-D (control key and D). (By doing this, you will lose all of the functions that you defined while you were in the interpreter.) Play around with rex and get the feel of how it works. For practice, try typing in some of the functions that we wrote in class and try them out. For more documentation, see the rex reference guides available from the "Reference Guides" link on the course homepage.

Exit rex and use your favorite editor (emacs, vim, etc.) to create a file called hw4.rex. You'll write your functions for this assignment in this file. After you write each function, we recommend that you save and close the file. Then, test those functions in rex. Remember, you can start rex with a file by typing rex hw4.rex or you can just type rex and once you are there you can include a file by typing *i hw4.rex at the rex prompt.

1. A function called twiddle(L) which takes as input a list L and returns a list that is just like L except that the first two elements have been swapped (or "twiddled"). If the list contains fewer than 2 elements, then your program can behave any way you wish. For example, here is some sample input and output:

     rex > twiddle(["i", "like", "the", "number", 42]);
     [like, i, the, number, 42]
     

2. supertwiddle(L) returns a list identical to L except that every pair of successive elements has been swapped. If the list has an odd number of elements then the last element is untouched. For example here is some sample input and output:

     rex > supertwiddle([1, 2, 3, 4, 5, 6]);
     [2, 1, 4, 3, 6, 5]
   
     rex > supertwiddle([1, 2, 3, 4, 5]);
     [2, 1, 4, 3, 5]
     

Part 3: Spamsweeper! (60 Points)

Now for the Spamsweeper applet! There are two ways to run an applet: Either through a web browser (such as Safari, Mozilla, Netscape, etc) or through an appletviewer or Applet Launcher program. More on this shortly...

First, click here to see what the Spamsweeper applet will look like when you're done. You will need to click on the "reload" (or "refresh") button on your browser each time you want to start a new game after the first game.

Your program should have the following features:

• The game is played on a 12 x 12 board with 20 hidden cans of Spam. Give readable names to these values so that there aren't "magic values" throughout your program.
  
  
• If the user clicks on a cell that does not contain Spam, the program indicates how many of the neighboring cells (a cell has up to 8 neighbors) contain Spam. If this number is zero, the program uses recursive depth-first search to recursively expose all of the neighbors as described in class. (Please use recursion here - it's the cleanest and simplest approach.)
  
  
• If the user clicks on a cell that contains Spam (without holding the SHIFT key down) then the game ends. At this point, a message is displayed near the bottom of the applet screen with the message "GAME OVER. THAT WAS A CAN OF SPAM!". The applet continues running (stopping the applet is best done manually by leaving the web page or, if using appletviewer, typing CTRL-C) but it does not respond to any subsequent input from the player. The applet can be restarted by pressing the "reload" button on your web browser or by stopping and restarting the appletviewer.
  
  
• If the user clicks on a cell that contains Spam while holding down the SHIFT key, the letter "S" is exposed at that location. The number of remaining cans of Spam is displayed at the bottom of the applet screen.
  
  
• If the user clicks on a cell that does not contain Spam while holding down the SHIFT key, the game ends with the message "GAME OVER. THERE WAS NO SPAM THERE" displayed at the bottom of the applet. Again, the applet need not end, but there should be no response to subsequent user input.
  
  
• If all 20 cans of Spam are successfully defused, the player is congratulated with some sort of effusive compliment printed at the bottom of the screen. The applet doesn't end but it does not respond to subsequent user input.

We've left the basic components of Spamsweeper, as described in class, in the directory /cs/cs60/assignments/assignment4/Spamsweeper/. We've also left you the MicroMouse.java and MicroMouse.html files demonstrated in class, so that you can look these over, modify them, etc. to get more familiar with how applets work.

Copy all of these files into your own directory. Also, copy the file /cs/cs60/assignments/assignment4/copyFiles into your directory. (More on this later.)

You will be writing all of the interesting code for this program! In particular, you will need to write the constructor for Gameboard.java and all of the interesting methods in Spamsweeper.java. You should compile Spamsweeper.java in the normal way.

OK, now back to running your applet! Option 1 is to use an appletviewer or Applet Launcher (these are different names for the same kind of program). These programs are invoked on html files such as MicroMouse.html or Spamsweeper.html. For example, if you are using the mini macs in the Beckman CS lab, life is very easy! You don't even have to login to turing (your files are visible on the macs and on turing - they are shared!). You can develop your applet on those macs and then run the applet using Applet Launcher. (You can find Applet Launcher by clicking on the "Searchlight" magnifying glass icon at the very top right of the screen and typing "Applet Launcher". Once you open Applet Launcher you will see an Applet Launcher panel on the screen. Use the "Open" button to navigate through your directory for the file that you want to run. You need to select a file ending with .html such as MicroMouse.html or Spamsweeper.html. These html files will then launch your compiled applet. Of course, you need to make sure that you've written and compiled your applet. We've provided the MicroMouse applet already compiled and ready to run!)

Option 2 is to run your applet from a web browser (which is fun because then you can tell your friends and family to check it out over the web!), you can do this as follows:

• By running ./copyFiles from the directory in which you have your compiled java files and the html files, you will copy and set permissions for the class files and html files needed to run the applet. Note the period and forward slash in front of copyFiles.
• The copyFiles program copies the relevant files to ~/public_html, which is your webspace on turing. You can cd ~/public_html to that directory and check it out!
• Point your browser to www.cs.hmc.edu/~yourusername/MicroMouse.html or www.cs.hmc.edu/~yourusername/Spamsweeper.html, and the applet will load and run. (~yourusername refers to your turing login name preceded by a tilde symbol (~) in front of it.)
• On some browsers, after you copy a new updated version of your game into your webspace, the browser will still run the old version. This can be very annoying and confusing. On some browsers you can press Option and click the "reload" button or Control and "reload". Others allow you to type a particular letter at the Java console, e.g., if you use Safari on the Mac, type an 'x' within the Java console and it will flush its cache of .class files so that you can reload from scratch the next time. If all else fails, quit the browser and restart it.

Debugging:   We strongly recommend that you write your program incrementally, and test it for correctness as you go. From our experience, this can reduce the debugging time very substantially. For example, after writing the constructor for the Gameboard class, write a simple tester program to make sure that it's working. Similarly, make sure that your applet can draw the grid before worrying about filling it in.

What happens to my System.out.println commands? Printing out "stuff" is a key debugging tool. However, System.out.println commands will not be displayed in the same window in which your applet is running. You will need to "ask" your web browser to display these print statements in something called the "Java console". This is a little window which appears next to your browser window and contains the printed out text from the System.out.println commands. Here's how to do this:

• If you are using a Macintosh (OS X), go to Applications, then Utilities and double-click on the Console application. Now start your browser or the Applet Launcher and the console will display the text generated by your program.
• If you are using a PC, you will need to have the Java runtime environment installed (java.sun.com). Go to Start, then Settings, then Control Panel, and then Java Plug-in and choose "Show console". Hit "Apply" and then launch your applet.

Please sumbit ALL of the files associated with your solution, including all files ending with java and html. Your best bet is to use cs60submitall so that you don't overlook submitting any file. That command will make sure to submit everything you need!

For Totally Optional Bonus Credit create an implementation called Bonussweeper.java applet (and any other auxilliary files) which augments Spamsweeper with one or more of the following features (up to 2 bonus points for each feature, up to a maximum of 6 bonus points):

• A feature which ensures that the player's first probe never detonates a can of Spam (that Spam can is just moved if the user's first probe is at that location).



• A feature which displays a picture of a Spam can rather than the letter "S". You can easily find an image of a can of Spam on the web and then use Java methods to plunk this image at the appropriate cell on the gameboard. Surf the web or a good Java book to figure out how to do this!



• You might consider adding sound to the applet... again, this would require some research into how to play sounds in Java. Sun's Java API and tutorials are good places to start.



• Any single additional feature that you think would be cool.