Harvey Mudd College
Computer Science 42

Fall Semester, 2012
Assignment 6: Double-Ended Spam Cruncher Puzzle

Due Date: Wed. night. Nov. 7 (allowing you two weeks; please start early, because this is non-trivial)

Working in pairs is possible on this assignment, and is highly recommended. Do not work in groups larger than two. Each partner is expected to contribute 50% of the effort.

Partnering Protocol: If you agree to collaborate with a partner, let me know. Otherwise your name will be published on a list of people without partners. If you want to work alone, let me know that as well.

Requirement: Implement a Java application demonstrating the Double-Ended Spam Cruncher (DESC) behavior on a variety of grid samples that will be provided, selected from a menu. The DESC could model an AI player in certain types of games.

Objective: The objective is to implement and use some data structures, such as Queue and Deque, and to implement breadth-first search. The objective does not include creating the ultimate high-scoring puzzle solver. Rather you should aim for a clean general solution, but not expect it to be optimal.

An annotated partial screen shot of one version of the application is given below. The objective of the DESC is to “crunch” as much spam as possible, in the fewest number of moves possible, while staying in its two-dimensional environment. In addition, there is a penalty for spam left uncrunched. These items are combined in a Score, the point values of which are:

• 20 for each crunched spam,
• -10 for each leftover spam, and
• -2 for each step taken.

The DESC is shown below with its two red heads and a body of magenta circles. The spam is shown as green rounded rectangles.

When spam on a cell is “crunched” by either head, the DESC’s body lengthens by one cell. In the picture above, the DESC has already crunched 36 spam. Thus it has extended its original size of only two cells (both heads) to 38 cells total. The crunch effect is to be achieved as follows: If the DESC can move its head onto a spam cell, then the head takes the place of that cell and a body cell is added where the head formerly was.

There are some constraints that must be obeyed:

• The blue squares are walls through which the DESC cannot pass.
• The DESC always starts as just a head and tail on the leftmost two squares in the top row. Those squares are considered sacred, and no spam or wall can be placed on them.
• The DESC can only move in one of four directions (N, S, E, W).
• The DESC must remain connected at all times. Connections are NSEW, not diagonal.
• The DESC must stay totally within the given grid.
• The DESC cannot pass through or over its own body.
• The body must always follow one of the two heads.
• Only heads, not body cells, can “crunch”. (The DESC is not a constrictor.)
• The display should not flicker.
• The score must be display on the screen.
• The DESC must eventually stop, at which time Done is displayed before the score, as shown below:

A menu lists the available samples. A second menu chooses the delay between steps of the DESC. The DESC begins moving as soon as an example is chosen, and the delay can be set at any time, without restarting the current example.

The square size we are using is 15x15 pixels, The grids wil be limited to 40x40 cells.

Resources:

Zipped code for a starter kit may be found at:

http://www.cs.hmc.edu/courses/2012/fall/cs42/descStarterKit.zip

This code can be run on the command line using ‘ant run’. In the starter code, a detached head moves around randomly on the grid. If it happens to hit spam, it crunches it. It does not go through walls. This code was developed using Netbeans and the class DESCframe contains layout information that NetBeans understands, but other IDEs might not.

Hints and Suggestions

· Please use the “boilerplate” code provided for graphics buffering, so that your application does not flicker.

• Start by just getting the detached head to do a breadth-first search for spam. Then proceed with other aspects, such as constructing and controlling the body of the DESC.
  
  
• A Deque is the recommended structure for the DESC.
  
  
• Keep track of the cells covered as (row, column) pairs.
  
  
• Treat one head as dominant for controlling motion at any one time, but enable switching between the two heads easily.
  
  
• There are many possible heuristics, but please do not ITR because of spending too much time on this assignment. A few of many things that could be tried are:
  
  
• For searching in a dense region, some kind of raster scan by the DESC might be more cost-effective.
  
  
• When out of obvious possibilities, “regroup” by having the DESC “coil up” in an unoccupied region.
  
  
• Search along the body of the DESC to find a cell from which spam can be “seen”, then try to back up the head to that cell.

Submit your code as a zipped source directory.

Other versions (as web applets, but applets are not required in this assignment):

· A version by Aaron Bernard

· A very fancy version by Jeremy Lennert