Loop Patterns

## Fence Post Error – Off-by-one Error

Suppose you want to build a fence that is 16 yards long, and you want each section of the fence to 4 yards long. How many fence posts do you need? The correct answer is 5; however, many people divide 16 by 4 to say they need 4 posts. You can easily observe the correct answer in the following figure. In a loop, the fence post error is when the loop iterates one extra time or one less time. You will create fence post errors throughout your programming career. Most fence post errors are relatively easy to discover with good test cases. Consider the following `for` loop, which attempts to print four numbers, but prints three.

``````for (int i = 1; i < 4; i++) {
System.out.println(i);
}
``````

You should be careful with loops that process `String`s. The first character of a `String` is at position 0. The length of a `String` is the number of characters in the `String` - for example, `"Gusty"` has a length of 5. The last character in a `String` is a position length-1. Consider the following loop that is counting non-vowels in the `String` word. The loop has a fence post error. On the last iteration of the loop, the variable `i` contains the value 5. This translates to the statement `String letter = word.substring(5,6);` and 6 is beyond the range of characters in `word` – a `String` index out of range exception.

``````int totCons = 0;
for (int i = 0; i <= word.length(); i++) {
String letter = word.substring(i, i+1);
if (!”aeiou”.contains(letter.toLowerCase())) {
totCons++;
}
}
``````

The Fence Post Pattern is repeated as follows.

## Loop Patterns

There are several loop patterns that are used over and over in solving problems. You want to put these patterns in your memory mansion so they can easily be recalled. We return to these patterns in Arrays and ArrayLists. The patterns discussed in this section include the following. The code provided in the patterns solves a specific problem, but you can change the code to work for similar problems. For example, the find position of first match pattern code searches through a `String`. The code can be changed to search throug a an array or `ArrayList`.

1. Sentinel Pattern
2. Accumulator Pattern
3. Compute Sum/Average Pattern
4. Count Matches Pattern
5. Find Largest (or Smallest) Pattern
6. Find Position of First Match Pattern

## Sentinel Pattern

A sentinel loop is one that terminates when the loop encounters a sentinel, which is a preknown entity that tells us to stop. For example, you could iteratively read positive numbers (one at a time) from a user. You would stop reading when the user inputs a negative number. In this case, the negative number is the sentinel, which is guarding the input like a sentinel. The following loop demonstrates the Sentinel Pattern. The loop reads numbers from a user. The sentinel is when the user enters `quit`. Actually, the sentinel is any input that is not a number.

## Accumulator Pattern

The Accumulator Pattern is a pattern for a pattern. The Compute Average, Count Matches, Find Largest, etc. are specific instances of the Accumulator Pattern.
The Accumulator Pattern initializes some data structure prior to a loop and then accumulates data as the loop iterates. This pattern is shown in the following pseudo code.

## Compute Sum/Average Pattern

This section describes the Compute Average Pattern, which is a specific instance of the Accumulator Pattern. An average is the sum of N numbers divided by N. Thus the Compute Average Pattern contains the compute sum pattern. The Compute Average Pattern initializes two variables to 0 prior to the loop.

• `count` counts the numbers entered by the user
• `sum` accumulates the sum of numbers entered by the user

The `while` loop is a sentinel loop that terminates when the user enters `"quit"`. Since the `while` expression is `Scanner hasNextDouble` method, the sentinel loop actually terminates when the user enters something other than a number. On each iteration of the `while` loop, we read a `double` from the user, which is added to `sum`.

## Find Largest (or Smallest) Pattern

This section describes finding the Find Largest Pattern. You can change the comparison from `>` to `<` to find the smallest. When finding the largest, you assume that the first values is the largest. Then you repeately examine other values in a loop, updating the largest whenever a new value is largest than the current largest. The following is pseudo code and the code for finding the largest, which is a specific instance of the accumulator pattern.

This algorithm finds the largest in terms of input from some user (or possibly a file), but the same algorithm applies to arrays and arrayLists, which we study in Arrays and ArrayLists.

## Find Largest Pattern for Numbers in a File

We can connect a Java `Scanner` to an input file, and read numbers from a file to find the largest number. The code for doing this is given by the following.

## Count Matches Pattern

The section describes the Count Matches Pattern, which is a specific example of the Accumulator Pattern. The Count Matches Pattern is demonstrated by counting digits in a `long`. Suppose `long longVar` contains 1001232121. The count of digit 0 is 2, digit 1 is 4, digit 2 is 3, and digit 3 is 1. Section “Numbers - Converting Between Bases” in Numbers as Information contains pseudo code that converts to a particular base. The following code implements the base conversion algorithm where we convert a `long` to decimal, picking out digits to compare.

## Find Position of First Match Pattern

A `String` is a sequence of characters. A `String` can also be a sentence with words. The position of a match in a `String` is the index where the `String` begins. For examples,

• The first `'a'` in `"I am a teacher."` is at position 2.
• The first `"brick"` in `"Lego bricks are not masonry bricks"` is at position 5.

The Find Poistion of First Match Pattern finds the index where the match begins. The example in ths section uses `String`, but this pattern works with any sequential collection such as arrays and `ArrayList`s.

The following example finds the position of a space in a `String`. If the `String` does not contain a space, the position is determined to be -1. You should notice this mimicks the semantics of the `String` method `indexOf`.

## Loops and Simulation

We write a program that simulates throwing darts at a circle in a square. We randomly throw our darts, and assume that all of them hit the square. When we do this, most of the darts land in the circle, but a few land in the corners outside of the circle. The ratio of number of darts in the circle to the total darts thrown is an approximation of the circle’s area / the square’s area, which is pi/4. We can let our circle’s center point be at (0,0), and let the squares coordinates go from -1 to 1. To represent the point where our dart lands, we generate two random numbers x and y, where both are between -1 and 1. If the distance between our random point where the dart lands and the center point (0,0) is less than 1, our dart is in the circle, otherwise it is in the corners outside of the circle. The code for this is given by the following.

``````import java.util.Random;
import java.util.Scanner;
public class Darts {
public static void main(String[] args) {
Random generator = new Random(42);
Scanner in = new Scanner(System.in);
System.out.println("Enter number of dart throws: ");
int dartThrows = in.nextInt();

int insideCircle = 0;
for (int i = 1; i <= dartThrows; i++) {
double x = generator.nextDouble() * 2 - 1;
double y = generator.nextDouble() * 2 - 1;
if (x * x + y * y <= 1) { // unit circle: short-cut exp
insideCircle++;
}
}
double piEstimate = 4.0 * insideCircle / dartThrows;
System.out.println("PI Estimate: " + piEstimate);
}
}
``````
Tags: