 Graphic by Keith Ohlfs |
|
|
Graphic by Keith Ohlfs |
|
The purpose of this problem set is to give you experience with conditionals, instance variables, and object diagrams.
There are 3 pieces to this problem set: the prelaboratory assignment, the laboratory assignment and the homework assignment. You are required to do all three parts. We recommend that you do the prelaboratory problem before your lab section, the laboratory problem during your lab section and the homework problems after completing the prelab and lab assignments.
Prelab Problem: Turn in your final object diagram with the rest of your hardcopy submission. There is no softcopy submission for this part.
Laboratory Problem: Save the modified HurdleWorld.java file in the ps6_Buggles folder. When you have completed the entire problem set, upload the ps6_Buggles folder to your ps6 drop folder. Turn in a hardcopy of the HurdleWorld.java file.
Homework Problem 1: Save the modified FollowWorld.java file in the ps6_Buggles folder. Upload the entire folder to your ps6 drop folder. Turn in a hardcopy of the FollowWorld.java file.
Homework Problem 2: Save the modified FindWorld.java file in the ps6_Buggles folder. Upload the entire folder to your ps6 drop folder. Turn in a hardcopy of the FindWorld.java file.
Turn in only one package of hardcopy materials. Staple your files together with the cover page, and submit your hardcopy package by placing it in the box outside of Stanzi's office (E106, directly across from E101).
Reminders
The purpose of this prelab is to give you some practice drawing object diagrams. Recall that an object diagram shows a collection of interconnected class instances. Each instance is drawn as a large box that is labelled by the class name and contains the labelled instances variables of the class. Each variable is a small box that contains either a primitive data type (e.g., int, double, boolean, char) or a pointer to another object. Because object diagrams are drawn with boxes and pointers, they are sometimes called box-and-pointer diagrams.
Consider the following Java class declaration:
class Node { public int value; public Node left; public Node right; public Node (int v, Node l, Node r) { this.value = v; this.left = l; this.right = r; } }
The Node class specifies that instances of the node class have three instance variables: a value variable that holds an integer, and variables left and right that hold pointers to other Node instances. The Node constructor takes an integer and two Node instances and intializes the instance variables with these values.
Here is a sequence of statements that creates and manipulates Node instances:
Node a = new Node(1, new Node(2, null, null), new Node(3, new Node(4, null, null), null)); a.left.right = a.right.left; a.left.left = a; Node b = a.left; b.left.value = a.left.value + b.right.value;
Recall that null denotes the null pointer, a special value that can fill any variable of object type in place of a pointer to an object of that type.
In this problem, you are to draw a single object diagram that depicts the variables and objects created by executing the above five statements. Your diagram should include the local variables a and b as well as all of the Node instances that are created. It should show the state of all variables and objects at the end of the execution of the five statements.
Follow these conventions:
This fall, buggles are putting on their sneakers in preparation for one of their favorite activities: hurdle jumping! In this activity, a number of hurdles (walls one grid cell high) are placed at the base of a BuggleWorld grid. A buggle starting at position (1,1) must run across the base of the grid jumping all of the hurdles in its path until it reaches the opposite wall. The buggle does not know the placement of the hurdles in advance and so must detect them when it encounters them. For example, here is a sample hurdle configuration
and here is the result of a buggle jumping all of the hurdles
To begin this problem, download the ps6_programs folder from the CS111 download folder. This folder contains a ps6_Buggles folder that you will use both for this laboratory assignment and for Homework Problem 1. In the Test subfolder of the ps6_Buggles folder is an applet HurdleWorld.java that you should run with the Applet Viewer. This applet shows the correct behavior of a hurdling buggle. The applet begins with a random number and placement of hurdles.Pressing Run sets the hurdler in motion. Each time Reset is pressed, a new configuration of grid cells and hurdles is generated.
Your goal in this problem is to implement two kinds of hurdling buggles:
The File HurdleWorld.java contains three classes, two of which are shown below:
public class HurdleWorld extends BuggleWorld { Randomizer rand = new Randomizer(5); // Lots of code you can ignore omitted here. public void run () { Hurdler happy = new Hurdler(); happy.tick16(); } } class Hurdler extends TickBuggle { public void tick() { } public boolean atFinishLine() { // Return true if buggle is facing wall (as opposed to hurdle) and false otherwise. // Should leave buggle in same position and heading as when it starts. // Should not leave any marks behind. } public void jumpHurdle() { // Cause the buggle to jump the hurdle it is facing. } }
The HurdleWorld class is responsible for changing the size of the grid and populating it with a random number of hurdles. You do not have to understand the code that performs these actions. All that you have to understand about HurdleWorld is that it has a run() method that makes a Hurdler instance named happy and tells this buggle to move for 16 clock ticks. The Hurdler class is a subclass of the TickBuggle class discussed in lecture. Hurdler has a tick() method that specifies what it does on each clock tick. This method overrides the default tick() message supplied by the TickBuggle superclass.
You should flesh out the tick() method so that it implements the following behavior:
As is often the case, the specification of the tick() method can be simplified with some auxiliary methods. You should define these methods as part of your solution:
After a long day of hurdling, buggles are often too tired to jump all of the hurdles in a configuration. The TiredHurdler class describes buggles who will jump no more than a specified number of hurdles. The constructor method for TiredHurdler takes an integer that is the maximum number of hurdles the buggle will jump. For instance, new TiredHurdler(3) creates a buggle that will jump no more than three hurdles. If it encounters a fourth hurdle, it will stop moving.
Here is the skeleton for a TiredHurdler class that you can find in HurdleWorld.java:
class TiredHurdler extends Hurdler { private int hurdlesLeft; public TiredHurdler(int hurdlesLeft) { this.hurdlesLeft = hurdlesLeft; } public void tick() { } }
The class has an integer instance variable hurdlesLeft that keeps track of how many more hurdles the buggle is willing to jump. The constructor method for TiredHurdler initialize this instance variable to the number supplied when the instance is constructed. When a TiredHurdler runs the course, it should decrement this instance variable every time it jumps a hurdle and refuse to jump a hurdle when this instance variable contains 0.
Use the following version of run() to test your TiredHurdler:
public void run () { Hurdler happy = new Hurdler(); happy.tick16(); TiredHurdler harried = new TiredHurdler(3); harried.setColor(Color.green); harried.tick16(); }
This causes TiredHurdler harried to follow Hurdler happy part of the way through a course.
For your hardcopy submission, turn in the final version of HurdleWorld.java after you have finished implementing both the Hurdle and TiredHurdle classes. Your softcopy submission should be the final version of the ps6_Buggles folder after you have also completed Homework Problem 2.
In the FollowWorld problem, a buggle named Folla at coordinate (1,1) has before her a tantalizing trail of bagels. The exact length and shape and length of the trail is not specified. However, it is known that (1) the bagel trail has at least one bagel; (2) it starts at coordinate (1,1); and (3) it forms a continuous line that may bend in many different directions but may never branch out. For example, here is a sample bagel trail:
Your goal is to program members of the Follower class (such as Folla) to follow the trail of bagels. At every position, a Follower should eat (i.e., pick up) the bagel at that position, and then move in the direction of the next bagel. This process should continue until there are no more bagels. A Follower should also leave behind a colored mark in every grid cell that formerly contained a bagel so that the original path of the bagels is clear from the marks. For example, here is the state of the world after Folla has eaten all the bagels in the above picture:
To begin this problem, use the AppletViewer to run FollowWorld.html in the Test subfolder of the ps6_Buggles folder. When you start this applet, you should see the bagel trail shown in the first picture above. Every time you click on the Reset button, a new bagel trail will be randomly generated. When you click on "Run", a buggle follows the trail of Bagels, picking them up as it goes. Your goal is to develop a buggle that will correctly follow all such trails as in the Test example. You will use Reset and Run to test your program on a variety of trails.
Open the project file ps6_Buggles.proj. This contains many files, but the only one you need to look at is FollowWorld.java. This file contains two classes, as shown below:
public class FollowWorld extends BagelTrailWorld {
public void run () {
Follower folla = new Follower();
folla.tick64(); // Would be nicer to stop when find last bagel,
// but assume a predetermined number of steps for now.
}
}
class Follower extends TickBuggle{
public void tick () {
// Override default tick method of TickBuggle class.
// Follow the trail of bagels until they have all be picked up.
}
}The FollowWorld class is a subclass of the BagelTrailWorld class, whose responsibility is to draw bagel trails subject to the constraints mentioned above. The run() method of the FollowWorld class creates Folla and tells her to execute her tick() method 64 times. (We use a predetermined number of steps, but it would be much more elegant to have Folla move until she has eaten all the bagels in the trail. We will show how to accomplish this via recursion in lecture.) You do not need to modify the FollowWorld class in this problem.
In this problem, you should develop a bagel-following strategy for the Follower class and implement it in terms of the tick() method in that class. You should first develop a set of motion rules in the same style as those discussed for the Snaker class in lecture. Then you should implement your rules in the tick() method of the Follower class. (Note: you can download the code for Snaker.java from the lec12_programs folder inside the CS111 download directory.) Remember that the tick() method will be sent to Folla exactly 64 times for every bagel trail, regardless of its length and shape. So tick() must appropriately "do nothing" after all the bagels have been consumed.
Some notes/hints/suggestions:
public boolean isBagelInFront () {
boolean result;
if (isFacingWall()) {
result = false;
} else {
forward();
result = isOverBagel();
brushUp();
backward();
brushDown();
}
return result;
}
You might also want methods that check for a bagel to the left or right of a buggle.
public void setup() {
setDimensions(columns,rows);
}
To submit this problem, save the modified FollowWorld.java file in the ps6_Buggles folder and upload it (with the modified files from the lab and homework problem 2) into your ps6 drop folder. Turn in a hardcopy of FollowWorld.java
In the FindWorld problem, a hungry buggle named Fiona starting at coordinates (1,1) is attempting to find a single bagel hidden in an connected acyclic maze. An connected acyclic maze is a maze in which there is a unique non-backtracking path from any point in the maze to any other. This means that it is always possible for Fiona to find her bagel! Here is an example of a connected acyclic maze:
It is possible to visit all the cells of an connected acyclic maze by using the "right-hand-on-the-wall" strategy. That is, if you always keep your right hand on a wall as you walk through such a maze, you will eventually visit all the cells. Along the way, you will visit some cells more than once (i.e., backtrack), but that's OK.
Your goal is to program members of the Finder class (such as Fiona) to find the bagel in the maze by using the "right-hand-on-the-wall" strategy to visit cells in the maze until the bagel is found. Upon finding the bagel, the buggle should not eat it. but just sit on top of it. The buggle should leave a mark behind in every visited cell except for the cell containing the bagel. Here is a snapshot of the above grid when Fiona finds the bagel:
To begin this problem, use the Applet Viewer to run the FindWorld.html applet within Test subfolder of the ps6_Buggles folder that you downloaded for the laboratory assignment. This applet contains a working solution of the maze-navigating buggle. When you start this applet, you should see the maze and bagel shown in the first picture above. Every time you click on the Reset button, a new maze and bagel will be randomly generated. When you click Run, the buggle uses the buggle uses the right-hand-on-the-wall strategy to find the bagel.
Your goal is to develop a program that instructs the buggle to correctly find the bagel in any such maze. You will use Reset and Run to test your program on a variety of trails.
You will implement yout code in the file FindWorld.java. This file contains two classes, as shown below:
public class FindWorld extends MazeWorld { public void run () { Finder fiona = new Finder(); fiona.tick256(); // Would be nicer to stop when find bagel, // but assume a predetermined number of steps for now. } } class Finder extends TickBuggle { public void tick() { // Override the default tick method of the TickBuggle class. // Keep "right finger" of buggle on right wall until find bagel. } // Put auxiliary methods here }
The FindWorld class is a subclass of the MazeWorld class, whose responsibility is to draw a connected acyclic maze with a bagel in it. The run() method of the FindWorld class creates Fiona and tells her to execute her tick() method 256 times. (As usual, a predetermined number of steps is icky; we will see how to get rid of this ickiness later in the course via recursion and iteration) You do not need to modify the FindWorld class in this problem.
In this problem, you should "teach" members of the Finder class how to follow the "right-hand-on-the-wall" strategy by filling in the details of the tick() method skeleton in that class. Before writing any code, you should think carefully about the kinds of "before and after" rules your buggle should be following. That is, describe the buggle motion in terms of rules like "if the buggle is in configuration A before its move, it should be in configuration B after its move." For example, what should the buggle do when there is a wall to its right? when there is not a wall to its right? when there is a wall in front of it? when there is not a wall in front of it? These conditions are not orthogonal; e.g., the buggle may have a wall both in front of it and to its right.
Try to narrow the number of rules into the smallest number that implement a correct strategy. We strongly encourage you to work with your classmates on this part of the problem.
Once you have figured out a strategy, you should encode that strategy in Java code in the body of the tick() method within FindWorld.java. As always, you should feel free to define any auxiliary methods that you find helpful. In this problem, it is particularly helpful to define the following auxiliary method:
public boolean isWallToRight()
Returns true if there is a wall directly to the right of this buggle, and false otherwise.When this method returns, this buggle should have exactly the same position and heading as it did before the method was called.
It is possible to write a clear and correct solution to this problem in remarkably few lines of code. If you find yourself lost in a rats nest of conditionals, you are probably on the wrong track.
For your hardcopy submission, turn in the final version of FindWorld.java. Your softcopy submission should be the final version of the ps6_Buggles folder after you have also completed the Laboratory Problem.