###### Books / Patterns for Beginning Programmers / Chapter 11

# 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.