Reading for this assignment:
- Notes on programming style. You should follow these guidelines for this problem set and all your future programming assignments.
- Notes on pre-conditions, post-conditions, and invariants.
- Notes on conditionals and indenting code.
About this Problem Set
The purpose of this problem set is to give you experience with conditionals and boolean expressions in the context of two BuggleWorld programs and an application.In your coding, you should follow the style guidelines outlined in the reading as well as demonstrate that you understand the principle of when/how to use invariants.
On this assignment, getting the buggles to behave correctly is not enough to receive a perfect score. You must also write your programs so that they are beautiful. Good programming style produces programs that are easy for others to read and understand.
For this problem set, notes, hints, and suggestions are given (on a separate page) for the first two tasks. We want you to have freedom to think about the problem in your own way. Reading the hints page is not required. Its main purpose is to help you think about the problem if you don't know how to get started. We included some notes on what we think are good ways of going about programming. It is not required that you follow those guidelines exactly. However, your programming style should result in a program that is at least as easy to read and understand as the program would be if you followed our suggestions.
The code is available in the ps04_programs folder in the
cs111 download directory on the cs server.
This assignment is more challenging than the previous assignments. Based on student time estimates from previous semesters, most of you will need between 6 and 10 hours to complete this assignment. Please start early and plan your time accordingly.
How to turn in this Problem Set
You are required to turn in both a hardcopy and a softcopy. For general guidelines on problem set submission, including how to submit a softcopy and how to check if your softcopy submission was successful, click here. Please make sure to keep a copy of your work, either on your own computer or external storage device, or in your private directory (or, to play it safe, both).Hardcopy Submission
Your hardcopy packet should consist of:- The cover page;
- Your new
Follower.javafile from Task 1; - Your modified
DeadEndWorld.javafile from Task 2. - Your new
RPS.javafile from Task 3.
Softcopy Submission
Save the final
Follower.java, DeadEndWorld.java
and RPS.java files
in the ps04_programs folder. Submit the entire
ps04_programs folder to your drop folder on the cs111
server.
Task 1: FollowWorld
| A buggle named Folla at square (1, 1) has before her a tantalizing trail of bagels. The exact length and shape of the trail is not specified. However, it is known that (1) the bagel trail has at least one bagel; (2) it starts at square (1, 1); and (3) it forms a continuous line that may bend in many different directions but may never branch out. Here is a sample bagel trail: | Define a Follower class (for Folla to be
an instance of) 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 leaves behind a colored mark in every grid cell
that formerly contained a bagel, except for the cell of the very last
bagel. The Follower should stop and rest in that final cell.
For example, here is the state of the world after Folla has eaten all
the bagels in the previous picture: |
 |
 |
To begin this problem, run the sample solution applet
FollowWorldSoln.html.
When you start the FollowWorldSoln program, you should see a
bagel trail. Every time you click on the Reset button, a new
bagel trail will be randomly generated. When you click on the
Run button, a buggle follows the trail of Bagels, picking them
up as it goes.
We recommended that you slow down the pace of the buggle so that you can see what actions it takes at every step. You can do this by pressing the Step button many times, or by using the setDelay button to have the buggle wait a certain amount of time between every pair of steps. (Experiment to find a nonzero time that works best for you.)
Your goal is to develop a buggle that will correctly
follow all such trails as in the test example.
We have supplied you with the following FollowWorld class
in the file FollowWorld.java:
public class FollowWorld extends BagelTrailWorld
{
public void setup()
{
setDimensions(15, 15);
}
public void run ()
{
Follower folla = new Follower();
folla.tick128(); // Would be nicer to stop when find last bagel.
// assume predetermined number of steps for now.
}
public static void main (String[] args)
{
runAsApplication(new FollowWorld(), "FollowWorld");
}
} The run() method of the FollowWorld
class creates a Follower (a special kind of buggle) named
folla and tells her to execute her tick()
method 128 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 later see how to
accomplish this.) You do not need to modify the
FollowWorld class in this problem.
Your task is to create a Follower class from scratch
in a new file named Follower.java. Your
Follower class should be a subclass of TickBuggle
and it should define a tick() method and any helper methods used
by your tick() method.
(Because Follower is a subclass of TickBuggle,
Follower buggles already understand messages
like tick2(), tick4(), tick8(),
and so on, so you do not need to define these.)
Your tick() method should implement your
bagel-following strategy. Remember that the tick()
method will be sent to folla exactly 128 times for every
bagel trail, regardless of its length and shape. So
tick() must appropriately do nothing after all the bagels
have been consumed. In particular, once the buggle has determined
that there are no more bagels, it should not repeatedly
“dance” or “wiggle” in its final position.
Your Follower buggle should behave exactly like the
one we have given you in the test folder. Use
Reset and Run/Step to test your program on a
variety of trails.
In addition to creating your new Follower class in
Dr. Java, you will also need to open and compile the
FollowWorld class from
FollowWorld.java. The FollowWorld
class will not compile until you have defined your new
Follower class, of course. To test your program, run the
FollowWorld class using java FollowWorld
in the Interaction Pane.
Task 2: DeadEndWorld
An eccentric buggle named Deanna loves to wander around in mazes finding all the dead ends — i.e., cells surrounded on three sides by a wall. She loves it so much that she tries to get all her friends to find the dead ends in mazes, too. She does this by carrying around a bag of bagels as she explores mazes. Every time she finds a dead end, she leaves a bagel there so that her friends can be rewarded when they find the dead end.Deanna explores only connected acyclic mazes. A connected acyclic maze is a maze in which there is a unique path from any point in the maze to any other. This means that it is always possible for Deanna to find all the dead ends in a particular maze. Here is an example of a connected acyclic maze:
It is possible to visit all the cells of a 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 and end up where you started. Along the way, you will visit some cells more than once (i.e., backtrack), but that's OK.
Define a DeadEndBuggle class (of which Deanna will be
an instance) to drop bagels in all the dead ends of a particular maze
by using the right-hand-on-the-wall strategy to visit cells in the
maze until the buggle has explored the entire maze.
The buggle should color every visited cell with its color and
leave a bagel in every dead end of the maze. Here is a snapshot of
the above maze after Deanna is done exploring it:
To begin this problem, run the sample solution applet
DeadEndWorldSoln.html.
The DeadEndWorldSoln program is a working
solution of the maze-navigating, bagel-dropping buggle. When you
start this program, you should see a maze like the one shown in the
first picture above. Every time you click on the Reset
button, a new maze will be randomly generated. When you click Run,
the buggle uses the right-hand-on-the-wall strategy to explore the maze
and uses conditionals to figure out where to drop bagels.
As in Task 1, you are encouraged to use Step or setDelay
to slow down the pace of the buggle to study its behavior.
Complete the definition of the DeadEndBuggle class so
that instances of this class behave like the test buggle. That is, an
instance of DeadEndBuggle should explore every cell of a
connected acyclic maze and drop a bagel in every dead end. We have
provide you with the following skeleton of the
DeadEndBuggle class in the file
DeadEndBuggle.java:
public class DeadEndBuggle extends TickBuggle
{
// This location is helpful for stopping the buggle
// when it returns to its starting position.
Location start = new Location(1, 1);
// Override the default tick() method of the TickBuggle class.
// Keep "right finger" of buggle on right wall to explore maze.
// Drop bagels in dead ends.
public void tick()
{
//your definition here
}
// Add your auxiliary methods below:
}
You will need to teach members of the DeadEndBuggle
class how to follow the right-hand-on-the-wall strategy by filling in
the details of the tick() method skeleton in that class.
You should also define any auxiliary methods you find helpful.
We have also provided you with the following working definition
of the DeadEndWorld class in the file
DeadEndWorld.java:
public class DeadEndWorld extends MazeWorld
{
public void setup()
{
setDimensions(15, 15);
}
public void run ()
{
DeadEndBuggle deanna = new DeadEndBuggle();
deanna.tick1024();
}
public static void main (String[] args)
{
runAsApplication(new DeadEndWorld(), "DeadEndWorld");
}
}The DeadEndWorld class is a subclass of the
MazeWorld class, whose responsibility is to draw a
connected acyclic maze. The run() method of the
DeadEndWorld class creates a DeadEndBuggle
named deanna and tells her to execute
her tick() method 1024 times. (A predetermined
number of steps is inelegant. We will see how to get rid of this inelegance
later in the course via recursion and iteration.) You do not
need to modify the DeadEndWorld class in this problem.
As always, add helper methods to simplify or improve the readability
of your code. Depending on how you structure your solution, you might
want to code one or more of the following methods:
isWallToRight()
isWallToLeft()
isInDeadEnd()
isPathToRight()
isPathInFront()
isPathToLeft()
You can test your solution by compiling the
DeadEndWorld class and running the
DeadEndWorld program. You should make sure that your solution
works properly on at least the first 3
mazes generated by Reset. These first three mazes
include all the possible starting configurations that your buggle
needs to handle. Your solution should behave exactly like the
solution provided except that your buggle
may continue to move after returning to the starting position. In
fact, your buggle will likely start traversing the maze again.
However, your program must not crash and produce any
Unhandled exception messages. For example, you must
never drop a bagel onto another bagel, which crashes BuggleWorld.
If you want an extra challenge, you can try to figure out how to get the buggle to stop in the initial square without continuing to move. But don't try this until after you have done everything else in the assignment!
Task 3: Rock, Paper, Scissors
Write an application from scratch that plays the children's rock, paper, scissors game. Specifically, write a class calledRPS whose main() method
invokes a method for determining the winner of a game. The method to
determine the winner should take two arguments. The first argument is
a string representing the choice of the first player, and the second
argument is a string representing the choice of the second player.
Each player chooses one of "rock", "paper",
or "scissors". If one or both players choose something
else, your program should print out an error message and not determine
a winner.
Given two valid inputs, the method that determins the winner should print out one of the following 3 lines, as appropriate:
Unless there is a tie, your program should also print a reason for the victory, which is one of the following 3 rules (the first choice beats the second choice):Player 1 wins Player 2 wins It's a tie
The output may appear in either order (winner then reason or reason then winner). Neither a winner nor a reason should appear if the input is invalid, however.Rock dulls scissors. Paper wraps rock. Scissors cuts paper.
Your main() method should test your code on various
combinations of inputs. There nine possible pairs of valid inputs,
but you should also test your code on invalid inputs.
Your solution will be graded on correctness, but also on the basis of its modularity and clarity of style. Judicious use of methods will improve your program's modularity and readability, and thus its score.