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

Programming Pattern: Fence Post Pattern

public class FencePostPattern {
   public static int fencePostProblem(String word) {
      int totCons = 0;
      // loops one beyond lenght of word
      for (int i = 0; i <= word.length(); i++) {
         String letter = word.substring(i, i+1);
         if (!”aeiou”.contains(letter.toLowerCase())) {
             totCons++;
         }
      }
      return totCons;
   }
}

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.

import java.util.Scanner;
public class SentinelLoopPattern {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      System.out.println("\nEnter sequence of nums, quit to see sum.");
      double sum = 0.0;
      /*
       * Sentinel is quit
       * Sum is 0.0 if user does not enter numbers
       */
      System.out.print("Enter value, q to quit: ");
      while (in.hasNextDouble()) {  // enter quit to terminate
         sum += in.nextDouble();
         System.out.print("Enter value, q to quit: ");
      }
      System.out.println("Sum is " + sum);
   }
}

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.

initialize variable(s)
loop begin
   update variable(s)
loop end
variable(s) has accumulated a value

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.

import java.util.Scanner;
public class SumAveragePattern {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      double value;    // will contain each value input by user
      int count = 0;   // initialize the count of user’s numbers to 0
      double sum = 0;  // initialize the sum of user’s numbers to 0
      System.out.println("Enter a double or q to quit: ");
      if (in.hasNextDouble()) {
         while (in.hasNextDouble()) {
            value = in.nextDouble();
            sum = sum + value;  // we could do sum += value;
            count++;
            System.out.println("Enter a double or q to quit: ");
         }
         System.out.println("Sum: " + sum + ", Average: " + (sum / count));
      }
      else {
         System.out.println("No numbers entered");
      }
   }
}

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.

Pseudo Code
largestVal is first value from the user
while there are more values
   inputVal is next value from the user
   if inputVal > largestVal
     largestVal = inputVal

Code
import java.util.Scanner;
public class SumAveragePattern {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      double largest;
      boolean haveFirst = false;
      System.out.println("Enter a double or q to quit: ");
      if (in.hasNextDouble()) {
        while (in.hasNextDouble()) {
          value = in.nextDouble();
          if (!haveFirst) {
            largest = value;
            haveFirst = true;
          } else if (value > largest) {
            largest = value;
          }
          System.out.println("Enter a double or q to quit: ");
        }
        return largest;
      }
      else {
        System.out.println("No numbers entered");
      }
   }
}

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.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class LargestNumInFile {
   public static void main(String[] args) throws FileNotFoundException{
        File inputFile = new File("inputFile.txt"); 
        Scanner in = new Scanner(inputFile);
        double largest = in.nextDouble();
        while (in.hasNextDouble()) {
            double input = in.nextDouble();
             if (input > largest) {
                largest = input;
             }
        }
        System.out.println("Largest value: " + largest);
    }
}

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.

import java.util.Scanner;
public class CountMatchingDigits {
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int counter = 0;
      System.out.print("Enter an long: ");
      long number = in.nextLong();
      System.out.print("Enter a digit to match: ");
      int digitToMatch = in.nextInt();
      long temp = number;
      while (temp > 0) {
         int digit = (int)(temp % 10);
         if (digit == digitToMatch) {
            counter++;
         }
         temp = temp / 10;
      }
      System.out.println(number + " has " + counter + " digits of " + digitToMatch);
   }

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

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.

public class FindPositionOfFirstMatch {
   public static void main(String[] args) {
      String s = "Thissentence hasaspace";
      int firstSpace = -1;
      for (int j = 0; j < s.length(); j++)
         if (s.charAt(j) == ' ') {
            firstSpace = j;
            break;
         }
        
      System.out.println("First space in " + s + " is " + firstSpace);
   }
}

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);
    }
}