Harvey Mudd College
Computer Science 60
Assignment 06

Double-Ended Spam-Cruncher (revised)

Due Dates:

• For all sections Tuesday night. Oct. 29.

This assignment is an application of queues 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-Eater, 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. (Here is where you use a deque.)
  
  
• A DESC always travels by having its cells follow one of its two heads, chosen by the DESC itself.
  
  
• Each square in the grid might or might not contain spam, the favorite food of the DESC.
  
  
• When a DESC moves onto a square containing spam, it crunches the spam, leaving the square containing no more spam. Simultaneously, the DESC grows longer by one cell, so that the head opposite the one doing the crunching effectively stays put.
  
  
• 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 cells can be obstacles when it comes to getting food.

The purpose of this assignment is to program the class DESC and the class Grid, as well as a main program for a DESC, described next.

Requirement for the main program:

The main program reads a grid from the standard input (System.in). The size of the grid (number of rows then columns) is read first, followed by the coordinates of the spam (row then column) until the end of file. If any row or column is out of range, the pair should be simply ignored.

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.
   
   
3. Print out the new coordinates of the head in the direction of motion, one row-column pair per line.

Illustration

Below observe several snapshots of the main program.

1. The first snapshot shows the start, with the DESC represented by o’s in the upper-left and the spam represented by x’s. oo x x x x			2. The DESC turns toward the nearest spam: o x o x x x
3. The DESC crunches the spam: o x o o x x		4. The DESC turns toward the next nearest spam: x o oo x x
5. The DESC crunches the next spam: x oooo x	6. The DESC, having reversed direction, turns toward the next spam: x ooo o x

Sample input and output files will be provided in the directory

 /cs/cs60/a/06/.
 

Submitting your code

You should submit your rex functions in two files: Quantity.java and OpenList.java using

cs60submit DESC.java Grid.java . . .

where . . . represents any other support .java files needed. Do NOT submit .class files or test files.