A crude depiction of a meep burrow.
A new meep has just entered the burrow.
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:
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)
public int getSize()
public String toString()
public int compareTo(Meep m)
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.
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).
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()
@Override public String toString()
public void add(Meep newcomer, boolean print)
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.
UsernameA05bWrite 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.
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:
V{
A{
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
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.
This assignment involves the following concepts.
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.
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.
new ArrayList<PyramidStack<Meep>>(); and add three new PyramidStack<Meep> objects to it. You now have 3 stacks at shafts.get(0), shafts.get(1), and shafts.get(2) (or whatever you choose to name your variable: shafts, holes, stacks, burrows, etc.)
shafts.get(2).peek(). But we're going to be moving the tiny meep around. So use a variable (such as tiny) that starts as 2. Now, at any time, shafts.get(tiny).peek() will give you the tiny meep. If the meep goes right, tiny would change from 2 to 0. If it goes left, tiny would change from 2 to 1. (Of course, you also have to pop() the meep from its old stack and push it into the new stack whenever you change its index.)
tiny = (tiny + move + 3) % 3;The +3 is necessary to avoid negative results while still getting the "wrap around" behavior. Trace through this to see how it works. For example, if the meep is in the left-most shaft (tiny == 0) moving left (move == -1), this will give the new burrow location: tiny == (0 + -1 + 3) % 3 == 2.
other1 and other2), you may have to move a meep from one shaft to the other. Consider:
shafts.get(0).push(newcomer);), you'll need to check if you can move it from there directly to the right-most shaft and so avoid the flurry. You can do that if the right-most shaft is empty. If it's not empty, then it's safe to peek at it to see the size of the meep there. Shortcut logic operators help a lot here:
if (this.shafts.get(2).size() == 0 ||
this.shafts.get(2).peek().compareTo(newcomer) > 0) {
//move meep from left to right-most shaft
}
moveMeep(int from, int to) method that takes the indices of the stacks to move a meep from and to. Or you might want something like a moveOtherMeeps(int tiny, Meep newcomer) 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.
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.
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.)
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)
//done
else:
//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
else:
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
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.