Assignment 5: Spampede and Fun with Rex
Part 1 Due Wednesday, Oct 4, 5pm
Part 2 Due Sunday, Oct 8, 11:59pm

Suggested Reading for this week: Keller Chapters 2 and 3. You may wish to read over this material to reinforce your grasp of rex concepts.

Please start this assignment early. It's fun and challenging. There are two parts: Part 1 is rex and some of Spampede and Part 2 is finishing up Spampede.

A reminder also that the first exam will be in class on Thursday, October 5.  The exam will cover material up to, and including, the lecture before the exam. You may bring an 8.5 by 11 sheet of paper with writing on both sides (your own writing please). Write down anything on that sheet that you like. The purpose of this sheet is to minimize memorization so that you can concentrate on concepts instead. You will submit the sheet with your exam but will get it back.

To help you have time to study for the exam, we have split this assignment into two parts with two different due dates.  Please note the earlier due date for part 1!

Summary of What's Due When

• All subparts of problem A (rex)
• Basic Spampede from functionality described below under part 1 requirements

• All remaining Spampede functionality

A.    Playing with Rex! [35 points] (All due with Part 1)

In this part of the assignment, you will have a chance to write some fun rex functions.

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.) For more documentation, see the rex reference guides available from the "Reference Guides" link on the course homepage.

Use your favorite editor (emacs, vim, etc.) to create a file called hw5.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 hw5.rex or you can just type rex and once you are there you can include a file by typing *i hw5.rex at the rex prompt.

Important information on testing: For this part of the assignment, your grade will be based both on the correctness of your functions and completeness of your testing.  You should test each function on several inputs, paying special attention to "hard" or "boundary" cases.   It is the diversity of the tests that matters, not the absolute number, so you don't need to go overboard with the number of tests you choose to run for each function.  You should create a text file called hw5tests.txt that shows the results of running your tests in the rex interpreter.  (You can copy from rex and paste into your favorite text editor--let us know if you have problems with this).  Submit both your rex functions (hw5.rex) and your tests (hw5tests.txt) when you submit this assignment.    

In this part of the assignment, you may use any built-in functions which we have seen in class. You may also define your own additional helper functions if you wish. For full credit, try to keep your code simple - all of these functions can be implemented very succinctly.

Your hw5.rex file should contain programs ("functions") for the following:

1. [3 Points] A function called find_index(X, L) which returns the index of the first occurrence of element X in list L. The first item in the list is assumed to have index 0. If X is not an element of L then this function should return a number larger than the index of any element in the list. For example here is some sample input and output:

    rex > find_index(1, [1, 2, 3]); 
    0
   
    rex > find_index(3, [1, 2, 3]);
    2
   
    rex > find_index(42, [1, 2, 3]);
    4
    

   Note that since 4 is not in the list [1, 2, 3], the function returned a number larger than the length of the list, which is 3. My solution printed 4, but any number larger than 3 would be OK in this case.
   
   
2. [3 Points] A function remove(X, L) which constructs a list identical to L except that every occurrence of X in L has been removed. The order of the unremoved elements should not be changed. If X does not occur in L then, naturally, this function simply constructs a list identical to L. For example here is some sample input and output:

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

3. [2 Points] pair(X, L) returns a list of all pairs (a pair is a list with exactly two elements) in which the first element is X and the second element is taken from L. For example here is some sample input and output:

    rex > pair(1, [2, 3, 4]);
    [[1, 2], [1, 3], [1, 4]]
    

4. [3 Points] all_pairs(L1, L2) takes two lists as arguments and returns a list whose elements are all the pairs with the first element from L1 and the second element from L2. For example here is some sample input and output:

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

5. [5 Points] dupereverse(L) takes a list L whose elements could be numbers or lists (the elements of those lists could be numbers and/or lists). This function returns a list which is the reversal of L. If L contains a list, then that list gets recursively reversed. For example here is some sample input and output.

    rex > dupereverse([1, [2, 3], [4, [5, 6, [7, 8], 9] ] ]);
    [[[9, [8, 7], 6, 5], 4], [3, 2], 1]
    

   You may use any built-in rex functions. In particular, the atomic predicate (take a look at how we implemented flatten) will be especially useful here, and you may (or may not) choose to use reverse in your solution.
   
   
6. [3 Points] uniquify(L) returns a list identical to L except that only the first occurence of each item of the list is saved. That is, all duplicates of an item are removed except for the first occurence. For example here is some sample input and output:

    rex > uniquify([1, 2, 1, 3, 2, 4, 2]);
    [1, 2, 3, 4]
    

7. [3 Points] height(T) takes a list representing a tree as input (remember from lecture that a tree is just cleverly represented as a list!) and returns the height of the tree. The height of the empty tree is defined to be 0. The height of a tree with just one node is 1. The height of a tree, in general, is the maximum number of nodes among all paths from the root of the tree to a leaf of the tree. For example here is some sample input and output:

    rex > mytree = [5, [3, [], []], []];
    1
   
    rex > height(mytree);
    2
    

8. [3 Points] Create a function called minimum(T) which takes a list representing a binary search tree as input and returns the smallest element in that tree. For example, here is some sample input and output:

    rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ]];
    1
   
    rex> minimum(mytree);
    3
    

9. [10 Points] Write a function delete(X, T) which takes a value X and a list T representing a binary search tree and returns a binary search tree with all of the elements of T except with X removed. You can assume that X is definitely in the tree T. You should use the algorithm described in class for removing an item from a binary search tree. You'll need to use the minimum function that you wrote in the previous problem to do this. Remember that to delete an element from a binary tree is not difficult if the element has 0 or 1 children. If the element (call it X) to be deleted has 2 children, we find the next larger element in the tree (call it Y) (the minimum element in the right subtree), remove Y, and place Y where X used to be. Now, we must do this using recursion! (Take a look at the insert function that we wrote in class. The recursion in delete will use similar ideas!) For example here is some input and output:

    rex > mytree = [10, [3, [], []], [42, [20, [], []], [60, [], []] ] ];
    1
   
    rex > delete(10, mytree);
    [20, [3, [], []], [42, [], [60, [], []]]

B. Spampede! [65 points total: 20 in part 1, 45 in part 2]

The Spampede game takes advantage of the double-ended Queue (Deque) class you wrote in Assignment 4 in order to implement a centipede in search of spam within a simple Maze-like world.

Example Applet

You can run an example Spampede applet at www.cs.hmc.edu/~alvarado/applets/Spampede.html.

You can also run the "starter" Spampede applet which we saw in class by clicking here. We have provided the code for this starter applet and you will be modifying it until you have the working game!

Files and Classes

You will need to write the Spampede.java file that contains your Spampede class extending Applet. The "starter" applet Spampede.java and its html file Spampede.html are provided for you in /cs/cs60/assignments/assignment5/Spampede/.

In addition, you will need to use the following classes. These files are also provided:

• a Boardcell class (a default class modified from HW4 is provided)
• a Deque class (such as the one you wrote last week -- there will be a fully functional one placed in the directory on Wednesday, in case you'd prefer not to use your own.)
• a DNode class (provided in Deque.java)
• a DequeADT interface (provided in DequeADT.java)
• a Queue class (provided in Queue.java, used for the Deque)
• a Node class (provided in Queue.java)

Finally, we have also provided the following files which you may wish to use (totally optional):

• Spam.au, an audio file
• spam.gif, an image of a can of Spam
• copyFiles, a script that copies everything to your public_html directory

Getting the applet running

Make sure that you can run the provided "starter" applet from an Applet Launcher or from your webpage. If you're using your webpage, here are things to remember:

1. Make sure you have the Java Console open for your browser for debugging.
2. Compile everything with javac *.java .
3. Copy everything to your web directory with ./copyFiles. (If you are copying the files manually, please make sure not to copy the .java files.)
4. Now your Spampede applet (in it's current state) should appear from any web browser at the address

    http://www.cs.hmc.edu/~<your turing login name>/Spampede.html
    

Writing the applet

• create, in init, a 2d array of Boardcells. The reference to this 2d array is called grid and is already defined. Be sure you don't have a 2d array of nulls!


• initialize the contents of each of these Boardcells. This is similar to adding mines in Spamsweeper, except that you should be sure that the edges of your grid are all designated as walls. This will prevent many out-of-bounds errors! (Internal walls are OK, but not required.) The Boardcell.java file has setContents and getContents members. By default, it uses chars to represent its contents. Also, each Boardcell should hold its coordinates (while not strictly necessary, this is often helpful).


• draw the 2d array of Boardcells with the off-screen Graphics object named g. This should happen every time cycle gets called, and perhaps more often, e.g., when a key is pressed, as well. You should draw the 2d array of Boardcells as a 2d array of colored rectangles, with different colors of your choice representing walls, empty space, the head of the centipede and the body of the centipede. You will want to use the fillRect command to accomplish this.


• keep track of a Deque of spam. You can add (and/or remove) spam by calling a method from cycle every so often (probably not every time). You can also add spam as needed (e.g., when one is eaten). But, you should have spam on the board at all times!


• keep track of the centipede (i.e., the "spampede") with a Deque. Your centipede will be a Deque of Boardcells, where the head of the centipede is at the front (not surprisingly), and the body of the centipede, which should be a different color, is the remainder of the Deque. The centipede should advance one square each time the cycle method is called. Keep in mind that no Boardcells are moving! Rather, it's the Deque that's wending its way through the 2d array of Boardcells.

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

What does the code have to do?

Part 1 requirements:

• Drawing the grid and the centipede within it. Each Boardcell should be 10 pixels by 10 pixels. The default environment should be a simple room 30 Boardcells (in the y direction) by 50 Boardcells (in the x direction), the outer boundary of which consists of walls. Additional obstacles/walls are totally optional.


• Populate the board with spam (the spam can be static for Part 1)

Part 2 requirements:

• Every so often, the centipede's position should be updated within the maze. That is, the centipede's head advances one Boardcell in whatever direction it is facing, and the centipede's tail retracts by one Boardcell. (You need not stick to any particular speed, but remember that the graders will be using your applet -- try to keep them happy!) This is done in the cycle method, which is called every so often independent of the other things going on in the applet.
  
• If the centipede's head moves to a Boardcell that contains a wall or another part of the centipede, the centipede dies, and the game can either stop with an approprite message or it may start again. Note: it's tempting to try to call init, but applets should not do this. Rather, you might write another method, perhaps called reset, that resets the game's conditions. This reset method could be called from init, as well as in the case that the centipede dies.

• If the centipede's head occupies a Boardcell that contains a morsel of spam, the centipede grows by one Boardcell. That is, when the centipede next moves, its head advances one square, but its tail does not retract.


• When the user presses the following keys, the centipede should change direction as indicated:
  • r : reverse, switching its head's position to its tail
  • i : turn north
  • j : turn west
  • l : turn east
  • k : turn south
  If the centipede is already heading in the direction that the user chooses, nothing changes. If the user changes the centipede's direction so that it is moving back on itself (from South to North, say, or West to East), you may reverse direction, ignore the command, or "terminate" the centipede.


• Note on "reverse" The reverse key (r) does not necessarily send the centipede in the compass direction opposite to which it was just heading. Instead, it switches the current tail to become the head and the current head to become the tail. It then should determine which direction the centipede's head segment and second segment are heading and set the current heading appropriately. (It's a good thing you wrote reverse, peekFront, and peek2Front methods in your Deque class!


• Maintain Start and Pause buttons. Working versions are provided in Babypede.java -- you will not have to change them, though you may "upgrade" them if you wish.

I want more!

If you haven't had enough of the Spampede.java file at the end of this assignment, there are a couple of specific items and an open-ended invitation to improve on the applet for optional bonus credit. (Up to 3 points for each additional feature for up to 9 bonus points in total.) However, please do the rex part of this assignment first. (The rex part is important and will help you prepare for the exam.)

If you add optional features, please document them in ALL UPPERCASE in a comment at the top of your Spampede.java file so that the grutors will see this.

• Speed up: You might want to have the rate at which the centipede is moving to increase as the game progresses.


• Scoring: You might want to have a system of scoring with a running total displayed as a label or text field or simply drawn to the applet panel.


• Lives: Rather than resetting or stopping the game after a single Spampede crash, keep a text field (or label) with the number of lives remaining and decrement it after each crash. When there are no lives left, stop the game (though you might want to consider a "reset" button.)
  


• Levels: Rather than maintaining a single, static maze, you may want to have the centipede advance to different mazes after consuming enough spam.
  


• Wrapping: Allow the centipede to wrap around the game board -- either in an unlimited fashion or through small "tunnels" in the walls. Or you might consider a "hyperspace" square, that sends cells to another spot on the board.


• General improvements: Feel free to add additional features you think would enhance the Spampede applet: different kinds of spam, sounds, images, other graphical widgets like pull-down menus or text boxes, etc.
  

Submission and Testing

There are a lot of files that make up this assignment, so the easiest thing to do is to run

 > cs60submitall