►Commonwealth School CS 3
Introduction to Class-based Program Design
▼Assignments
►Assignment 4: Accumulators
On this page:
Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
8.6
    contents  ← prev  up  next → 

Assignment 4: Accumulators

Goals: Practice designing methods that use accumulators.

You should submit one .java file containing the solution to these problems.

Be sure to properly test your code and write purpose statements for your methods. A lack of tests and documentation will result in a lower grade! Remember that testing requires you to make some examples of data in an examples class.

Read this paragraph. You must do at least three of these problems. They are listed in (what I think is) ascending difficulty; problems 3 onwards are above average difficulty. You will get extra credit for completing problem 4, and even more extra credit for completiting problem 5, as well as further extra credit for completing 2 or more of these problems.

Problem 1

For this problem, you will model an ancestry tree (abbreviated as AT). Every person in your AT should have a name, year of birth, and two ancestors. Due to imperfect genealogy records, some ancestors will be unknown. Unknown ancestors have no information.

  1. Design all of the classes and interfaces necessary to represent this tree.

  2. Create a sufficient number of examples to test on.

  3. Design a method that determines if this AT is well formed. An AT is well formed if everyone is younger than all of their ancestors by at least 10 years. Your method should only visit every node of the tree at most once.

Problem 2

For this problem, you will model a cashier’s job at a movie theater. At this movie theater, every customer only buys one ticket with cash, and tickets only cost five dollars (if only!). All cash is either a five or ten dollar bill. If a customer has a ten dollar bill and change cannot be made, the customer goes to another theater.

Here are classes to represent this data:

// a cash register with a certain # of five and ten dollar bills in it class CashRegister {
int fives;
int tens;
 
CashRegister(int fives, int tens) {
this.fives = fives;
this.tens = tens;
}
}
 
// cash interface ICash {}
 
// a five dollar bill class Five implements ICash {}
 
// a ten dollar bill class Ten implements ICash {}
 
// a list of cash interface ILoCash {}
 
class MtLoCash implements ILoCash {}
 
class ConsLoCash implements ILoCash {
ICash first;
ILoCash rest;
 
ConsLoCash(ICash first, ILoCash rest) {
this.first = first;
this.rest = rest;
}
}

  1. Create a sufficient number of examples to test on.

  2. Design a method in the CashRegistger class with the signature int moneyAtEndOfDay(ILoCash customers) that determines how much money is left in the cash register at the end of the day when all of the given customers have made their transactions (or been turned away if no transaction was possible). The first customer of the day is at the head of the list. Be aware that the cash register may start out with some amount of fives and tens already in it.

    Note: as always, use proper delegation!

Problem 3

For this problem, we will model documents with a nested structure, and a numbered path to each section. Below is an example that was floating around the internet:

In this example, there is no section below "Getting Around In Excel" at the outer-most layer, but this is entirely possible. The section below it at the outer-most layer would have a "2." at the front.

Here is a data definition which allows us to model such a structure (note that it ignores section text, such as this paragraph, and only considers a section header):

// a section in a nested document interface ISection {
}
 
// a section with a header class Section implements ISection {
String title; // the title of the section ISection child; // below and indended to the right ISection below; // below and at the same level of indentation  
Section(String title, ISection child, ISection below) {
this.title = title;
this.child = child;
this.below = below;
}
}
 
// an empty section; used to indicate the end of a document/section class NoSection implements ISection {
}

The numbers at the beginning of the output should not actually appear in the title field of your Sections; only in the string that is generated.

Your task is to add (and test) one method (and any helper methods you may need) to the ISection interface, stringify, which will output a single string that contains not only the title of each section, but each title prepended with the path to it. For example, in the above image, the title "The Ribbons" would be prepended with "1.1.3. " (notice the space).

In the output, each section header should end with a newline, which in Java (much like ISL) is the special string "\n". Empty documents should just output the empty string. You do not have to prepend a line with anything other than the path to it followed by a single space (in other words, you do not have to generate any kind of indentation in your output).

Problem 4

Design a class for a task. A task has an id (an integer) and a (possibly empty) list of prerequisites, represented as the ids of the tasks that need to be completed before that task is.

Design a method on a list of tasks which produces the list of the tasks one can complete from these tasks. You can assume all task ids are unique.

Before beginning to program, sketch the helpers you’ll need to solve this problem, and ask yourself some questions: can task dependencies be cyclic? Are any tasks guaranteed to be completable? Be sure to understand these questions and what they imply for your program, as well as your examples and test cases. Your method should be able to terminate no matter what list it is operating on.

Note that in the problem definition alone a list of tasks can represent two different things: the tasks the method is being called on, and the subset of those tasks that can actually be completed. Keeping track of what list of tasks means what as you complete the problem is essential.

Problem 5

In this problem, you’re going to help two drivers on a RoadTrip. Every road trip has two drivers, driver1 and driver2, as well as directions, which is a list of Direction. A Direction has a description, and a number of miles. For example, if a direction had the description "make a U-turn" and the number of miles was 20, it would mean that in 20 miles, the driver should make a U-turn. Also, for simplicity’s sake, miles will always be measured with whole numbers in this assignment. Drivers will just be represented by their names.

The issue our drivers are facing is that the road trip might be very long, so they want to split up the road trip by changing who is in the driver’s seat every 10 (or 15, or 20, or whatever the given number is) miles. The number of miles is always guaranteed to be positive and a whole number, but those are the only assumptions that can be made about the number. Also, note that driver1 should always be the first driver on the road trip.

Design a method splitUpTrip that transforms a road trip into a list of road trip chunks, based on the given number of miles the drivers want to switch-off. A RoadTripChunk has a driver as well as directions, which is a list of Direction.

For example, imagine that drivers Hazel and Henry are following these directions (with the number of miles given after the direction’s description):

  • Make a left at Alberquerque, 13

  • Make a right at the fork, 2

  • Make a left at the next fork, 3

  • Take the overpass, 45

  • Destination on left, 12

If they wanted to switch who was driving every 15 miles, the split up instructions would look like this, with Hazel as the first driver:

  • Make a left at Alberquerque, 13

  • Make a right at the fork, 2

  • Switch with Henry, 0

Then, with Henry driving:

  • Make a left at the next fork, 3

  • Switch with Hazel, 12

Then, with Hazel driving:

  • Switch with Henry, 15

Then, with Henry driving:

  • Switch with Hazel, 15

Then, with Hazel driving:

  • Take the overpass, 3

  • Destination on left, 12

Note that the drivers have to be informed how long to drive until they need to switch, so those instructions need to become new directions in the list of road trip chunks where appropriate.

Before you begin to program, make sure you understand the entire given example. Work through it on paper until each step of the output is clear. Going through this process by hand will make the logic the code must implement much more explicit. Once you have done this, upload a photo of the paper to Google Classroom. I will not answer questions on this homework unless someone has uploaded a photo, unless the question relates to understanding the problem and being able to work through the example on paper.

Hint: When a direction is too long for the current driver to finish, it effectively becomes two directions: the direction to switch drivers when their driving is up, and the original direction minus the distance already travelled. When writing your methods, think carefully about how these "new" directions play into the recursive structure of your code, and what list of directions you want to recur on.

Hint: you will certainly need to use at least one accumulator parameter in at least one helper method. There are several valid designs for this problem; work through a wish-list process to figure out what helpers you might want.

Hint: If you find yourself needing to reverse the order of lists (not all implementations will), it is best to reverse everything at the end once so you don’t need to keep track of whether or not directions and/or road trip chunks are in order as you go. You might also want to write methods which place items at the end of a list instead.

    contents  ← prev  up  next →