Starts and Completions

Programs frequently need to determine the number of tasks associated with an amount of work, given a measure of the amount of work per task. Sometimes the need is for the number of tasks that were started, and sometimes the need is for the number of tasks completed. This chapter considers solutions to these kinds of problems.

Motivation

The terminology used in the name of this pattern comes from baseball/softball, where it is common to track the number of times a pitcher starts a game and the number of times that they complete that same game. However, as a motivating example, it is better to think about running. For example, suppose you are working for a charity that has organized a fund raising event in which donations are tied to the integer number of laps (started or completed, depending on the donor) rather than the number of miles. Each participant has a wrist band that tracks the number of miles they run. Your job is to write a program that calculates the number of laps that a runner has started and completed given the number of miles run (the measure of work) and the number of miles per lap (the amount of work per task).

Thinking About the Problem

The naive approach to finding the number of completions is to use division. For example, if a participant has run 7 miles over a 3 mile track, then they have run \(7 / 3 = 2 \frac{1}{3}\) laps. The obvious shortcoming of this approach is that the result isn’t an integer and donations are promised per “whole” lap.

Fortunately, you know how to solve this problem. In fact, the example itself should bring to mind the notion of doing arithmetic on a circle (or, an oval, in this case) and the use of integer division. It then follows that 0 miles corresponds to 0/3 (i.e. 0) laps, 1 mile corresponds to 1/3 (i.e., 0) laps, 7 miles corresponds to 7/3 (i.e. 2 laps), 9 miles corresponds to 9/3 (i.e., 3) laps, etc.

Given this observation, you might then think that all you need to do to find the number of starts is to add one to the number of completions, and a few tests might convince you that this is, indeed, the case. For example, 7 miles over a 3 mile track corresponds to 7/3 (i.e. 2) completions and 7/3 + 1 (i.e., 3) starts. Unfortunately, this “solution” is only correct for some cases. For example, 9 miles over a 3 mile track corresponds to 3 completions and 3 starts (not 4 starts). In other words, in general, you should only add 1 to the number of completions when the denominator isn’t evenly divisible by the numerator.

The Pattern

The simple part of the pattern involves ideas from Chapter 5 on arithmetic on the circle and can be written as:

    public static int completions(int work, int workPerTask) {
        return work / workPerTask;
    }

where work would correspond to the number of miles run and workPerTask would correspond to the length of the track.

The more complicated part of the pattern, on the other hand, involves an indicator method from Chapter 9, and is given by:

    public static int starts(int work, int workPerTask) {
        return completions(work, workPerTask) 
            + remainderIndicator(work, workPerTask);
    }

where remainderIndicator() is 1 when any “extra” miles have been run and is 0 otherwise. In other words, remainderIndicator() is given by:

    public static int remainderIndicator(int num, int den) {
        if ((num % den) == 0) {
            return 0;
        } else {
            return 1;
        }
    }

Examples

As an example, suppose a very energetic participant in the charity event runs 26 miles (just short of a marathon). Then, that person completed 8 laps (i.e., 26 / 3), but started 9 (since 26 % 3 is non-zero).

As another example, suppose a starting pitcher works for 7 innings in a baseball game (that is 9 innings long). Then, that pitcher did not complete the game (since completions(7, 9) is 0) but did start the game (since completions(7, 9) + remainderIndicator(7, 9) is 1). On the other hand, a starting pitcher that works all 9 innings has 1 (i.e., 9 / 9) completion and 1 start (since 9 % 9 is 0).

Looking Ahead

As mentioned briefly in Chapter 9, you may take advanced courses that consider situations in which it is important to avoid the use of if statements. There are two different ways to accomplish this when solving starts and completions problems.

An Arithmetic Solution

One approach is to use a threshold indicator instead of the indicator method used above. In this context, (miles % length) (the number of “extra” miles run) plays the role of value, and length plays the role of max. What this means is that the indicator is given by:

        indicator = ((miles % length) + length) / (length + 1);

Putting it all together, starts is given by:

        starts = (miles / length)
            + (((miles % length) + length) / (length + 1));

An Alternative Arithmetic Solution

Integer division can be defined in two different ways, an idea that is often discussed in great detail in upper level courses. For now, you can get some understanding of this idea by considering a different way of solving the starts problem.

To begin, ignore situations in which the numerator is 0. Then, considering an example in which the number of miles is between 1 and 6 (inclusive), the complete set of numerators is given by \(\\{\texttt{1}, \texttt{2}, \texttt{3}, \texttt{4}, \texttt{5}, \texttt{6}\\}\). If you simply divide (using integer division) each of these elements by the denominator 3 (i.e., the length of the track in miles), you get the set \(\\{\texttt{0}, \texttt{0}, \texttt{1}, \texttt{1}, \texttt{1}, \texttt{2}\\}\), which is clearly incorrect.

But, maybe the mistake is because you’ve started counting from 1 instead of from 0. So, you start from 0 instead. In this case, the set of numerators is \(\\{\texttt{0}, \texttt{1}, \texttt{2}, \texttt{3}, \texttt{4}, \texttt{5}\\}\). If you now divide (again using integer division) each of these elements by the denominator 3, you get the set \(\\{\texttt{0}, \texttt{0}, \texttt{0}, \texttt{1}, \texttt{1}, \texttt{1}\\}\). Now, each element of the set is only off by 1. So, you only need to add 1 to the result of the integer division to get the correct answer.

In other words, ignoring situations in which miles is 0 you have the following:

        starts = ((miles - 1) / length) + 1;

Now you need to consider whether this solution will work when the numerator is 0, which depends entirely on what -1 / length evaluates to. It turns out that there are two possible answers, depending on how integer division is defined.

In one definition, the result of an integer division is moved towards 0. Using this definition, -1 / length evaluates to 0. This is the way integer division using the / operator works in Java. Using this definition of integer division, the alternative solution does not work when miles is 0 (because the result should be 0 but will be 1).

In the other definition, the result of an integer division is moved towards negative infinity. Using this definition, -1 / length evaluates to -1. This is the way integer division using the Math.floorDiv() method works in Java. Using this definition of integer division, the alternative pattern does work when miles is 0 (because the result should and will be 0). In other words, the following solution:

        starts = Math.floorDiv((miles - 1), length) + 1;

does work.