Assignment 05b


Simulate a meep warren.

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


As a continuation of A05a, 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 and dangerously. 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: a shallow vestibule on the left, a wide atrium in the center, and a warm deep tablinum on the right. The meeps stack themselves up in decreasing size in the tablinum, leaving the other two shafts empty.

When a new meep enters the burrow, it always drops into the vestibule (left-most shaft).

5 meeps in a burrow of 3 shafts
A crude depiction of a meep burrow.
A new meep has just entered the 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 meep's 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 tablinum (right-most shaft). This miraculous shuffle happens with only one meep moving at a time, without any meeps leaving the burrow, and without any meep getting crushed in the process.

Natural algorithm: 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.)

Tower of Hanoi algorithm: Later scholars have noted that the above algorithm produces the exact same sequence of moves as a traditional Tower of Hanoi algorithm. Specifically, whenever a newcomer arrives, all smaller meeps use a Tower of Hanoi movement to perch on top of the newcomer in the vestibule. Then this entire stack, including the newcomer, uses Tower of Hanoi movement to move back again to the tablinum.

While most meep naturalists believe that the smallest meep in the burrow leads the flurry in some way, as described in the natural algorithm, either algorithm will be valid for this simulation. The Tower of Hanoi approach has the advantage of being more concise and handles meeps of equal size (good for extra credit), but most support in the Discussion and FAQs below is for the natural algorithm.

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

public MeepBurrow()
Constructs an empty burrow with 3 shafts. Uses PyramidStack<Meep>s to model the shafts. (I recommend you put the 3 stacks into a single ArrayList so you can refer to them by index.) All instance variables must be private.
@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. Shafts should be given in vestibule-atrium-tablinum order, and each line should be prefaced with either a V, A, or T label. (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 void add(Meep newcomer, boolean print)
Drops the given meep into the vestibule of the burrow and then runs through the flurry to get it into the correct location. If the print argument 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: UsernameA05b

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);
    //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:
T{M9, M8, M7, M6, M5, M4, M3, M2, M1

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

What to Submit

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

Upload your UsernameA05b.jar to Tamarin.

Remember to follow the course coding standards on all assignments.

Grading [70 points]

5 - Compiles
15 - Meep
Requested constructor, accessor, and toString methods (5; required for more points). Correct compareTo method (10).
50 - MeepBurrow
Requested constructor and toString method (15; 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).
+5 - Equal-sized Meeps
Still works correctly if meeps of the same size are added to the burrow.


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 Tower of Hanoi through trial-and-error.

Tower of Hanoi is a classic recursive problem undertaken at the 211 or 311 level, though there are less-well-known iterative solutions. However, the meeps problem is not exactly the same problem. In Tower 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. You now have the chance to choose between two different algorithms that are known to solve the same problem.

Note that it is 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 "observed" meep movement. So, 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 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(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.

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 Natural 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.

The recursive Tower of Hanoi algorithm will already handle equal-sized meeps.


I don't trust that my PyramidStack is 100% correct. Is there anything I can do to move on to A05b?
You may 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 file in this case, since it would overwrite the working PyramidStack.class file when Tamarin compiles all your submitted .java files.)

This Natural algorithm is still giving me trouble. Can you give me some more help here?
Here is a more specific rewrite of what was given above:
public void add(Meep newcomer, boolean print):
    push newcomer into shaft(0)
    if shaft(2) is empty or if newcomer is smaller than shaft(2)'s top meep:
        move newcomer from shaft(0) to shaft(2)
        //a flurry is required
        //track which shaft (index) tiny meep is in
        tiny = 2  

        //determine which direction tiny meep will move during this flurry
        if shaft(tiny) countBefore newcomer is even:
            move = -1   //left
            move = 1   //right
        while there are still meeps in shaft(0) or shaft(1):
            //run the flurry.  There are 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
                //both shafts have a meep
                move the smaller meep (if <= newcomer) from one to the other shaft

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 natural 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.