Simulate a meep warren.
Text: 3.1, Java review.
Concepts: encapsulation; interfaces; stacks.
As a continuation of A06a, 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. 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. 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.
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()
@Override public String toString()
public 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.
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.
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
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.
This assignment involves the following concepts.
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.
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(0).peek()
. But we're going to be moving the tiny meep around. So use a variable (such as tiny
) that starts as 0. Now, at any time, shafts.get(tiny).peek()
will give you the tiny meep. If the meep goes right, tiny
would change from 0 to 1. If it goes left, tiny
would change from 0 to 2. (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 burrow (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(1).push(newcomer);
), you'll need to check if you can move it from there directly to the left-most shaft and so avoid the flurry. You can do that if the left-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(0).size() == 0 || this.shafts.get(0).peek().compareTo(newcomer) > 0) { //move meep from center to left-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. (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.)
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, ...): 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.