teaching machines

CS 145 Lecture 22 – Loop-and-a-half

Agenda

  • what ?s
  • what does this do?
  • looping patterns:
    • loop and a half
    • accumulation
    • selection

TODO

  • Let’s not have lab tomorrow. This was anticipated! Quiz 4 is and has been scheduled for next week.
  • For Wednesday, complete some loop questions on CodingBat, sections String-2 or String-3, or Practice-It!, section BJP3 Chapter 5.

Note

Loops add a motor to our code. They definitely open up the possibilities of what we can do in our programs, but things can also get out of hand very easily. Our best bet is to write and read many loops. Let’s read some in another installment of What Does This Do?! I’ll reveal the following code snippets one at a time. Read and absorb them for at least 30 seconds before saying what you think the code is doing.

  1. public static String ?(String raw) {
      String cooked = "";
      for (int i = 0; i < raw.length(); ++i) {
        if (Character.isLetterOrDigit(raw.charAt(i))) {
          cooked += raw.charAt(i);
        } else {
          cooked += "_";
        }
      }
      return cooked;
    }

  2. public static ? ?(int a, int b) {
      int foo = 0;
      for (int i = 0; i < b; ++i) {
        foo += a;
      }
      return foo;
    }

  3. public static ? ?(int n) {
      Random g = new Random();
      while (true) {
        int a = g.nextInt(n);
        int b = g.nextInt(n);
        int c = g.nextInt(n);
        if (a != b && a != c && b != c) {
          return a + " " + b + " " + c;
        }
      }
      return null;
    }

  4. public static void ?() {
      for (int r = 1; r <= 5; ++r) {
        for (int c = r; c >= 0; --c) {
          System.out.print(c);
        }
        System.out.println();
      }
    }

We almost never write code from scratch. Even if we don’t call any helper methods, we still see similar patterns over and over again in our algorithms. Let’s example a few patterns through some examples.

We start with the loop and a half. This pattern emerges when we want to execute some portion of our repeated step more than another portion. We’ll look at an example of signing off a love note with “xoxoxoxoxox”, expressing lineage sentences like “A begat B begat C”, and generating a spherical triangle in Madeup. There’s not necessarily a clean way to solve this problem. We could condition that some portion of our code on the iteration count:

for i through bound
  do everytime stuff
  if i < bound (or perhaps i > 0)
    do inbetween stuff
  do everytime stuff
end

Or we could break out the portion before or after the loop:

do half step on item 0
for i in 1 .. bound
  do full step
end

for i in 0 to bound
  do full step
end
do half step on last item

Next we observe the accumulation pattern, where a loop iterates through a collection and accumulates values in some variable of larger scope. We’ll look at some examples of normalizing an image and calculating a linear approximation of a dataset.

Code

LoveLetter.java

package lecture1026;

public class LoveLetter {
  // xoxoxoxox
  public static void main(String[] args) {
    System.out.println(getLoveOX(3));
  }
  
  public static String getLoveOX(int n) {
    String oxen = "x";
    for (int i = 0; i < n; ++i) {
      oxen += "ox";
    }
    return oxen;
  }
}

Lineage.java

package lecture1026;

import java.util.Scanner;

public class Lineage {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    // Gerald, Esmerelda, Cornelius, Gladys, Margaret, Bartholomew
    // Gerald begat Esmerelda begat Cornelius begat ...
    System.out.print("Enter name list: ");
    in.useDelimiter("(, |\r?\n)");
    
    String lineage = "";
    while (in.hasNext()) {
      String name = in.next();
      System.out.println(name);
      if (lineage.isEmpty()) {
        lineage += name;
      } else {
        lineage += " begat " + name;
      }
    }
    
    System.out.println(lineage);
  }
}

Haiku

Five floors to Light House
Leap three steps, three, three, then two
My loop and two-thirds

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *