Harvey Mudd College
Computer Science 60
Assignment 07

Double-Ended Spam-Cruncher Applet

Due Date: Midnight, morning of Monday March 31

This assignment is an application of searching and deques. Use your classes from the previous assignment, or if those don’t work, use the solutions provided to that assignment.

Requirement: Implement in Java the Double-Ended Spam-Cruncher, the basis for a graphic application to be described in the next assignment, its environment, and a main program controlling its actions, as described below.

A Double-Ended Spam-Cruncher (DESC) is an artificial life form that lives on a two-dimensional grid of squares, with the following additional properties:

• A DESC has two or more cells, each cell covering one square of the grid.
  
  
• A DESC has two heads, one at each end. Let’s refer to these as the front and back ends, respectively.
  
  
• A DESC always travels by having its cells follow the lead of one of its two heads, chosen by the DESC itself. The head being followed currently is called the dominant head.
  
  
• Each square in the grid might or might not contain spam, the favorite food of the DESC. A square can alternatively contain blockage, or could just be empty.
  
  
• When a DESC’s dominant head moves onto a square containing spam, it crunches the spam, leaving the square containing no more spam. Simultaneously, the DESC grows longer by one , so that the head opposite the one doing the crunching effectively stays put, while the spam square becomes the head, and the former head square becomes part of the DESC’s body.
  
  
• A DESC can only move one cell at a time, horizontally or vertically (no diagonals). When it moves, its head moves to the next square and the square on the end opposite is uncovered (unless the DESC has just eaten spam, in which case all squares remain covered, plus the square containing the spam).
  
  
• When a DESC turns, it does so by moving its head to its left or right from the current direction of travel.
  
  
• A DESC cannot leave the grid, e.g. by falling off the edge.
  
  
• A DESC cannot crawl over or across itself. Therefore, its own cells are be obstacles when it comes to getting food.

The purpose of this assignment is to program the class DESC, as well as an applet for the DESC, as described next.

Requirement for the applet:

Please make the DESC class inherit from the DLDeque class, to gain practice in using inheritance.

The applet is named DESCapplet (use this exact spelling, because that is what we’ll be testing).

The applet allows choice of a sample grid as in a06.

The DESC always begins occupying the leftmost two squares in the top row. It should be assumed that these squares do not contain spam. Spam should not be specified in the input for either of those squares; if it is, it will be ignored.

The DESC repeats the following cycle, until there is no more spam on the grid, or until the DESC has gotten itself into a position where the search can no longer reach any spam from either head in its current position:

1. Compute the shortest path from each head to the closest spam square. (Here is where you use a queue. Don’t forget that the DESC’s own cells are regarded as an obstacle.)
   
   
2. Move according to the first step on the shortest path from the closer head. There are at least two ways to achieve this effect:
1. Implement two separate breadth-first searches.
2. Implement a single breadth-first search, but enqueue both head squares at the beginning. When you find the spam, trace it back to which ever head corresponded to that path.
   
   
3. The user should be able to mouse-click on a square to add more spam.
   
   

Extra credit options:

4. The user is able to shift-click on a square to add more blockage.
   
   
5. The user is be able to nudge the DESC in one of the four directions by pressing one of the arrow keys. The nudge is processed before after the current spam finding cycle. If the user is fast enough, he or she should be able to nudge the DESC several times between cycles. (In order to react to keyboard events, have your applet implement interface KeyListener. Consult the java documentation web page.)
   
   
6. The DESC is able to reposition itself so as to find spam in the event that there is no direct path to the spam from either head. (This is a significant complication. Probably the best approach is to use depth-first search with iterative deepening. Ask me for an explanation if you need it.)
   
   
7. Other things: negotiate with me.

Submitting your code

cs60submit *.java . . .