Assignment 06b

Task

Simulate a meep warren.

Text: 3.1, Java review.
Concepts: encapsulation; interfaces; stacks.

Steps

As a continuation of A06a, you'll reuse some of your classes to build a simulation program. Specifically, you'll need to reuse:

Step 1: Meep

You are going to model some meeps. Meeps are fairly small, brightly-colored, furry creatures that live in holes in the ground. They have round, flat bodies and prefer to sleep stacked up on top of each other in their holes. However, larger meeps never perch upon smaller meeps. When not confined to their burrows, they can breed quickly. In more exotic locales, they can grow rather large and even speak. Some fringe naturalists suggest that they may be descended from flumphs, but this seems unlikely.

For our purposes, all we care about are the meeps' relative sizes. We will also want to be able order meeps from smallest to largest using the Comparable interface.

Therefore, create public class Meep implements Comparable<Meep> with the following details:

public Meep(int size)
All meeps should have a positive size. If the given size is not positive, throw an IllegalArgumentException.
public int getSize()
Return the size of this meep
public String toString()
Returns "M#", where # is the size of that meep. Examples: "M5", "M354", "M8".
public int compareTo(Meep m)
Returns a negative, positive, or zero value if this meep is smaller, larger, or equal (respectively) in size to the given meep m.

You may want to override the equals method too.

Any instance variables you declare should be private. Because your instance variables will be private (encapsulated) and there are no mutator methods, your Meeps will be immutable.

Step 2: MeepBurrow

As mentioned above, meeps live underground. Their burrows always contain 3 vertical shafts. The meeps stack themselves up in decreasing size in the left-most shaft, leaving the other two shafts empty.

When a new meep enters the burrow, it always drops into the center shaft.

5 meeps in a burrow of 3 shafts
A crude depiction of a meep burrow.

The arrival of this new meep causes a flurry of activity among those meeps that are smaller than the newcomer. Researchers believe this behavior is likely due to each meeps' strong desire to be stacked upon larger meeps, but this desire is tempered by the fear of being crushed. Interestingly, once the flurry of movement dies down, all meeps--including the newcomer--are once more stacked in the left-most shaft. This miraculous shuffle happens without any meeps leaving the burrow or getting crushed in the process.

After careful study, naturalists have noted that a meep flurry proceeds as follows:

Meeps have a very keen sense of size and social order and never seem to be at a loss for who stacks upon whom. Therefore, you can assume that the burrow will never contain two meeps of exactly the same size. (However, you can tackle this additional complication for extra credit.)

To simulate all this, create public class MeepBurrow with the following details:

public MeepBurrow()
Constructs an empty burrow with 3 shafts. Uses private PyramidStack<Meep>s to model the shafts.
@Override public String toString()
Returns a 3-line String that shows the current state of the burrow. Shafts should be printed horizontally, listing meeps bottom-to-top, with the left shaft first and the right shaft last. (Basically, rotate the image above clockwise by 90 degrees. See sample output for an example. This will be simple if you just call toString() on each of the PyramidStack shafts.)
public add(Meep newcomer, boolean print)
Drops the given meep into the center shaft of the burrow and then runs through the flurry to get it into the correct location. If the print parameter is false, all of this is done silently with no output. If true, prints details of the simulation, showing the state of the burrow after each meep movement.

Step 4: UsernameA06b

Write a main method that drops 5 or more meeps into a burrow and prints the final state of the burrow. The following is an example you are free to customize:

  public static void main(String[] args) {
    System.out.println("Dropping some meeps into a burrow:");
  
    //randomly order some meeps with none the same size
    Integer[] sizes = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    //convert to list in order to use API's shuffle method
    java.util.List<Integer> meeps = java.util.Arrays.asList(sizes);
    java.util.Collections.shuffle(meeps);
    
    //drop meeps into the burrow
    MeepBurrow hole = new MeepBurrow();
    for (int size : meeps) {
      Meep meep = new Meep(size);
      System.out.println("===ADDING: " + meep + "===");
      hole.add(meep, false);
    }
    
    //show the final burrow state
    System.out.println("FINAL burrow state:\n" + hole);
  }

Note how you can change the argument to the add method from false to true to get a turn-by-turn printing of the simulation.

Sample Output

Dropping some meeps into a burrow:
===ADDING: M8===
===ADDING: M2===
===ADDING: M1===
===ADDING: M6===
===ADDING: M7===
===ADDING: M9===
===ADDING: M4===
===ADDING: M3===
===ADDING: M5===
FINAL burrow state:
{M9, M8, M7, M6, M5, M4, M3, M2, M1
{
{

If I change the add argument to true, I get something like this: fullMeepSim.txt

What to Submit

Create a .jar file named UsernameA06b.jar. This should include:

Upload your UsernameA06b.jar to Tamarin.

Remember to follow the course coding standards on all assignments.

Grading [65 points]

5 - Compiles
15 - Meep
Requested constructor, accessor, and toString methods (5; required for more points). Correct compareTo method (10).
45 - MeepBurrow
Requested constructor and toString method (10; required for more points). Uses PyramidStacks to model burrows (5). Correct add method behavior according to rules of the simulation (25). Can run add silently (with false argument) or else prints each meep movement (with true argument) (5).
+20 - Equal-sized Meeps
Still works correctly if meeps are the same size are added to the burrow.

Discussion

This assignment involves the following concepts.

Algorithm and Simulation
I have a vague memory of playing an educational computer game very much like this when I was in elementary school in the 1980s. The goal was to sort small colored furry creatures living in vertical holes without crushing the smaller ones under larger ones. Little did I know that I was basically solving Towers of Hanoi through trial-and-error.

Towers of Hanoi is a classic recursive problem undertaken at the 211 or 311 level. However, the meeps problem is not exactly the same problem. In Towers of Hanoi, all the disks start in the correct order. With meeps, we're introducing an extra meep that is out of the normal order at the start of the movement. Also, with meeps, I wanted to find an algorithm that produces a motion that could be explained in terms of the meeps themselves. For example, in the process described above, the Tiny Meep leads the flurry based on size information that would be readily apparent to that meep. In the recursive solution, why would one stack of meeps choose to recursively move to a different burrow?

I discovered the less-common iterative solution to Towers of Hanoi and took that as the starting point. However, it took me 4 rewrites of this assignment to find a simple enough version of the problem. In the original version:

Note that it's important to maintain the rules of the simulated world here. If our goal was just to sort some meeps, we could throw them in an array and call java.util.Arrays.sort. Instead, we want to simulate the "natural" meep movement. Also, every meep in the burrow should be in one shaft or another at all times, without magically slipping past one another to a spot further down in a stack.

Immutability
Immutability is an important design tool when writing robust programs. Consider what would happen if a meep had a setSize() method:
Meep one = new Meep(1);
Meep two = new Meep(2);
Meep three = new Meep(3);
PyramidStack<Meep> stack = new PyramidStack<Meep>();
stack.push(three);
stack.push(two);
stack.push(one);  //stack is: M3 M2 M1
two.setSize(5);   //now stack is: M3 M5 M1

We just violated the supposed invariant of a PyramidStack because we were able to modify an element after it was placed in the stack. The simple mistake of modifying a meep that is actually still in a stack somewhere can thus produce some pretty terrible bugs in nontrivial code.

To avoid this possibility, we can make meeps immutable ("unchangeable") by not writing a mutator method. If you want to change a meep's size, make a new meep instead:

two = new Meep(5);

This effectively changes the value of the Meep in two, but that Meep object is no longer the one in the Stack.

Not every class can or should be designed to be immutable, but, when possible, it can be a good design choice.

Advice
These are some of the things you should probably consider as you implement different parts of this assignment.
Equal-sized meeps
Trying to handle meeps of the same size in the burrow while following the algorithm given above is very tricky. You would need to consider some of the following:

If you do want to attempt this, I strongly urge you to complete the normal version above, save a copy of your code, and only then consider how this might be done. (You may modify the algorithm to use a recursive Towers of Hanoi algorithm provided the flurry still ends up back in the left-most stack.)

FAQs

My PyramidStack is incomplete or buggy. Is there anything I can do to move on to A06b?
You my use my compiled version if you want: PyramidStack.class.

You will still need the Node and Stack .java files and to compile them. When you submit to Tamarin, you must include PyramidStack.class in your jar file. (Do not include any incomplete PyramidStack.java file in this case, since it would overwrite the working PyramidStack.class file when Tamarin compiles all your submitted .java files.)

This algorithm is still giving me trouble. Can you give me some more help here?
While it is possible to implement this differently (such as with a recursive form of the Towers of Hanoi algorithm), it can become very tricky if you start tinkering around. I strongly recommend you implement the algorithm as described. Here's a more specific rewrite of what was given above:
public void add(Meep newcomer, ...):
    push newcomer into shaft(1)
    if shaft(0) is empty or if newcomer is smaller than shaft(0)'s top meep:
        move newcomer from shaft(1) to shaft(0)
        //done
    else:
        //a flurry is required
        //track which shaft (index) tiny meep is in
        tiny = 0  

        //determine which direction tiny meep will move during this flurry
        if shaft(tiny) countLessThan newcomer is even:
            move = -1   //left
        else:
            move = 1   //right
        
        while there are still meeps in shaft(1) or shaft(2):
            //run the flurry.  Two steps every turn:
            
            //step 1
            move tiny meep to next shaft  //use tiny and move variables to do this
                                          //remember to update tiny variable to new loc
            
            //step 2: move one other meep (maybe) between other two non-tiny shafts
            determine indexes of other two shafts that don't contain tiny
            if both of other shafts are empty:
                //do nothing
            else if one of the shafts is empty and other shaft's meep is <= newcomer:
                move other meep into the empty shaft
            else:
                //both shafts have a meep
                move the smaller meep (if <= newcomer) from one to the other shaft
        
        //done

Note that this does not include any of the required printing details. Also, not every if given here will necessarily map to an if in your code. For example, "else if one of the shafts is empty" might become:

  else if shaft(other1) is empty...  
      ...
  else if shaft(other2) is empty...
Also, you can break this method into pieces. For example, as mentioned above, it would be a good idea to move the last part above into an moveOtherMeeps(int tiny, Meep newcomer) method that computes the indices of the other two non-tiny stacks, determines whether the move (of a Meep smaller than newcomer) is required, and if so, executes the move.
Wait, so I only determine the Tiny Meep's direction once per flurry?
Yes, that's right. Determine the tiny meep's direction before you start the flurry. The tiny meep then keeps moving in that direction for the entire flurry.