Problem Set 7

About this Problem Set

The purpose of this problem set is to give you more experience with recursion and writing recursive methods that return values.

• In Task 1, you will write from scratch a Java application that uses recursion to carry out a simple numerical computation.
• In Task 2, you will use recursion in PictureWorld.
• In Task 3, you will use recursion in BuggleWorld to implement the elaborate buggle bagel-harvesting ritual.

The starter code for Tasks 2 and 3 is available in the ps07_programs directory in the cs111 download directory on the CS server.

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 you softcopy submission was successful, click here. Please make sure to keep a copy of your work, either on your own computer or in your private directory (or, to play it safe, both).

Hardcopy Submission of Problems

Your hardcopy packet for the problems should consist of:

1. The cover page;
2. Your Exponentiation.java file from Task 1;
3. Your modified ColorTree.java file from Task 2;
4. Your modified HarvestWorld.java file from Task 3;

Staple these together, and submit them at the start of class on the due date.

Softcopy Submission of Problems

Save your new Exponentiation.java file and the modified ColorTree.java and HarvestWorld.java files in the ps07_programs folder. Submit the entire ps07_programs folder to your drop folder on the cs111 server.

---

Task 1: A Recursive Application

Write an application that takes two numbers, a base and an exponent, and outputs the exponentiation of the two numbers, i.e., the base raised to the exponent power. For instance, if your application is given the base 3 and the exponent 7 then your application should output the number 2187 since 3⁷ = 2187.

You should start by creating an Exponentiation class in a file named Exponentiation.java. Your Exponentiation class should have two class (i.e., static) methods:

• A recursive method that takes two integer parameters, corresponding to a base and an exponent, and returns an integer that is the value of raising the base to the exponent power. You method may assume that the exponent is an integer greater than or equal to zero.
• A main() method with the following formal parameter: String[] args. The main() method should carry out the following steps:
  • Convert two command line arguments into integers, the first of which corresponds to a base and the second of which corresponds to an exponent.
  • Invoke the recursive method that calculates the exponentiation of the base and exponent.
  • Output (via System.out.println()) the integer returned by the recursive method invocation.

The figure below illustrates the execution of a working Exponentiation application using the "Interactions" tab at the bottom of the Dr. Java window.

---

Task 2: ColorTree [15 points]

In this problem you will explore recursion in PictureWorld. In the ps07_programs folder, you will find a file ColorTree.java (in the ColorTree folder), which you are to edit. Specifically, within ColorTree.java you must define a method:

public Picture makeColorTree(Color c1, Color c2, Color c3, int levels);

Your goal is to define this method, using recursion, to create the patterns shown below. In the file, there is one primitive defined for you, a picture of a one-branched tree, as illustrated below:

Color trees built from the one-brached tree are shown below:

When the level is 0 (zero), the picture should be empty. Note that in the file ColorTree.java, the method invocations to create these color trees have already been included for you. All you need to do is define the method makeColorTree() such that it generates the pictures above. You may use methods from the PictureWorld contract. You do not need to define any other auxiliary methods in your solution, though you are free to do so.

Task 3: Harvest World

Note: Please read this entire problem carefully. Simply generating the correct final pattern is not enough to get full credit. Each specified method must behave as described below. Programming to a specification is an important part of software engineering.

Bagels in BuggleWorld grow in fields (you knew that, didn't you?). Twice a year the Harvester buggles go out and harvest bagels so that buggles in BuggleWorld will have bagels to eat and play with throughout the year. Bagels are the most important commodity in BuggleWorld. Therefore, their harvesting procedure is quite complex and elaborate. It is described below:

Each Harvester is assigned a field of bagels to harvest. The buggle does not know the width or height of the bagel field. The buggle starts in the bottom left corner of the field and harvests bagels one row at a time (a row is a vertical column on the BuggleWorld grid). It doesn't matter if the buggle chooses to harvest the closest row first and work down to the end of the field or to walk to the end of the field and harvest rows on the way back to the beginning. Note that there are no bagels planted in the bottom horizontal row of the field: That is the path that buggles walk on to get from row to row.

Each row is harvested according to the following procedure:

The buggle harvests the bagels in the row by picking them up and counting them. It doesn't matter if the buggle picks up bagels on the way to the end of the row or picks them up coming back from the end.

The buggle stacks the bagels in a row near the path (starting from the second cell up) so that they will be able to dry (dried bagels are the best and keep fresh all year long).

The rest of the field needs to be covered with tarp (black) which preserves the field from bad weather during the non-growing season. The tarp is at the far end of the row (i.e. at the top of the BuggleWorld grid). The buggle needs to go to the end of the row and pull the tarp up to the point where the bagels are stacked. The buggle should count the number of empty spaces left in each row (spaces covered by the tarp).

While the Harvester buggles do all the work, their supervisors want to be able to quickly look at the field and see how it did. It's a bit difficult to see the entire field, so the Harvester buggle must mark each row indicating whether or not the row did well. Bad rows (fewer bagels than blank spaces) are marked red and will get more fertilizer and attention in the next growing season. Good rows (more bagels than blank spaces) are marked green. Fair rows (same number of bagels as blank spaces) are left uncolored. Each row is also tagged with the number of empty spaces (i.e. spaces covered with black tarp). See the pictures below for clarification.

Finally, the Harvester buggle must count the number of bagels harvested in the field and report that to her supervisor.

The following two pictures show the state of a field before and after the buggle has harvested it.

Your task is to write the Harvester class, which will contain the methods that allow the Harvester buggle to do its job. You are free to write any auxiliary methods needed. At a minimum, you must define the following methods for the Harvester class. The complete specification for each method is given below. Each method must satisfy the specification given.

In addition to their individual specifications, all the methods described below must also meet the following invariant:

The buggle's state (position, heading, color, and brush state) will not be changed by execution of the method. Assumes the buggle's brush is initially up.

public int harvestField()
This method assumes that the buggle is starting in the lower left corner of a field facing EAST. When this method is invoked, the buggle will harvest the field of bagels to its front and left (up to the walls in front of and to the left of the buggle) and return the number of bagels harvested in this field.

public int harvestRow()
When this method is invoked, the buggle will harvest the row of bagels to its left (i.e. the vertical column above the buggle). The number of bagels harvested in this row is returned. This method should be invoked when the buggle is facing EAST and in the bottom row (the clear path) of the field. Harvesting a row involves the following steps:

• Pick up and count all the bagels in the row
• Put the bagels out to dry in a row starting from the bottom but not including the very bottom row
• Pulling the tarp over the rest of each row by walking to the end of the row and coloring the row black until you've reached the bagels
• Marking the row as fair (no color), good (green), or bad (red) by coloring the first (bottom) square of each row. A row produced a good harvest if there are more bagels than blank spots. A row produced a bad harvest if there are fewer bagels than blank spots.
• Marking the row by dropping the number of blank spots in the bottom square.

public int harvestBagels()
When this method is invoked, the buggle will pick up all the bagels between it and the wall and return the number of bagels picked up. This method should be invoked when the buggle is facing NORTH and in the bottom row (the clear path) of the field.

public void stackBagels(int numberBagels)
When this method is invoked, the buggle will create a stack of the specified number of bagels in front of itself. This method assumes that there will always be at least enough space in front of the buggle for the bagel stack. This method should be invoked when the buggle is facing NORTH and in the bottom row (the clear path) of the field.

public int pullTarp()
When this method is invoked, the buggle should draw a black line from the wall in front of the buggle to the current cell in front of the buggle (i.e. do not color the cell the buggle is on when the method is invoked). This method returns the number of cells colored. This method should be invoked when the buggle is facing NORTH and at the end of its bagel stack (i.e. right where the tarp should start).

public void markRow(int numberBagels, int numberSpaces)
This method paints the current cell green if numberBagels is greater than numberSpaces. The current cell is painted red if numberBagels is less than numberSpaces. The current cell is not painted if the numberBagels is equal to numberSpaces. The buggle also marks the cell with the numberSpaces (using dropInt()).

Notes:

Use setCellColor() to color cells:

public void setCellColor (Color c)
Paints the cell under this buggle with the color c

Use dropInt() to drop an integer into a particular cell:

public int dropInt (int n)
Drops the integer n into the cell of this buggle and returns the integer dropped.

To experiment with a working version of a solution to this problem, run the applet HarvestWorld in a web browser. (Note: a "HarvestWorld" parameters window will appear at the top of your screen, but if you don't see it, it may be located behind your web browser window, so you should move your web browser window.) Every time you run the program, the number of bagels reported by the Harvester buggle (and returned by the harvestField() method) should appear in the cyan colored box within the parameter frame window.