» CS 1: Lecture 26 – Array Patterns

CS 1: Lecture 26 – Array Patterns

November 8, 2017 by Chris Johnson. Filed under cs1, cs145, cs148, fall 2017, lectures.

Dear students,

After you solve a few array problems, you start to see some regular patterns emerging in your algorithms. Today, we break down a few of those patterns. The payoff of cataloging these is that the next time we encounter an array problem, we can apply the general structure and save our labor and thinking for the parts that are different.

We’ll start with the map pattern, which involves transforming one array into another. We might turn an array of strings into an array of their lengths, an array of miles into an array of kilometers, an array of strings into their lowercase equivalents, and so on. The map pattern looks like this:

make destination array that's the same size as source
for each item i in source
  destination[i] = transform source[i]

First we’ll convert an array of names into at an array of initials. Next we’ll distill an array of Stringy race results into an array of runner’s ages.

After that, we’ll visit the optimize pattern. Optimization algorithms find the maximum, the minimum, the shortest, the longest, the nearest, or some other extreme value within a data set.

initiaze soFar to first item
for each remaining item
  if item is better than soFar
    soFar = item

We’ll look a few examples of optimizing: we’ll find the oldest runner in the race. Then we’ll find the youngest.

We then turn to the linear search, in which we scan an array for a particular item and report its location. We might use this in a list of runners in a race, sorted by finish time. We search for a name and use its location to determine that runner’s place. The linear search pattern looks like this:

for each element
  if this element is the one we want
    return its index

Here’s your TODO list to complete before we meet again:

Homework 5 is posted. It is due before before November 22. You will need to Team / Pull… from template to get the SpecChecker. Want to avoid stress? Do the first five methods today. They are short. Do one of the remaining methods each day for the next week. Ask questions early.
The 10th annual Chippewa Valley Code Camp takes places this Saturday from 7:45 to 5 PM at CVTC—which is just up the hill. Attend, learn some stuff from industry speakers, and receive extra credit participation points by writing up a quarter sheet response to up to 2 of the talks. If you plan to attend, you need to RSVP as soon as possible.

See you next class!

Sincerely,

P.S. It’s time for a haiku!

How to find the cloves
For each spice, read its label
It is the last one

P.P.S. Here’s the code we wrote together in class…

Music.java

package lecture1108;

import java.awt.Desktop;
import java.io.File;
import java.io.IOException;

import hw5.speccheck.Duration;
import hw5.speccheck.Letter;
import hw5.speccheck.Note;
import hw5.speccheck.WavIO;

public class Music {
  public static void main(String[] args) throws IOException {
    // C C G G A A G
    
    Note[] twinkle = {
      new Note(Letter.C, 4, Duration.QUARTER),
      new Note(Letter.C, 4, Duration.QUARTER),
      new Note(Letter.G, 4, Duration.QUARTER),
      new Note(Letter.G, 4, Duration.QUARTER),
      new Note(Letter.A, 4, Duration.QUARTER),
      new Note(Letter.A, 4, Duration.QUARTER),
      new Note(Letter.G, 4, Duration.HALF),
    };
    
    Note a4 = new Note(Letter.A, 4, Duration.QUARTER);
    Note[] a4song = {a4, a4, a4, a4, a4};
    
    Note[] scale = new Note[40];
    for (int i = 0; i < scale.length; ++i) {
      scale[i] = new Note(a4.getHalfstepID() + i, Duration.EIGHTH);
    }
    
    String path = "/Users/johnch/Desktop/song.wav";
    WavIO.write(twinkle, 100, path);
    Desktop desktop = Desktop.getDesktop();
    desktop.open(new File(path));
  }
}

Initials.java

package lecture1108;

import java.util.Arrays;

import javax.xml.stream.events.Namespace;

public class Initials {
  public static void main(String[] args) {
    String[] names = {
      "Jill Mancurse",
      "John Smith",
      "Honest Abe",
      "Kim Jong",
      "Masahiro Sakurai",
      "Chancellor Jim",
    };
    
    String[] initials = initialize(names);
    
    System.out.println(initials);
    System.out.println(Arrays.toString(initials));
  }
  
  private static String[] initialize(String[] names) {
    String[] initials = new String[names.length];
    for (int i = 0; i < names.length; ++i) {
      char first = names[i].charAt(0);
      char last = names[i].charAt(names[i].indexOf(' ') + 1);
      initials[i] = "" + first + last;
    }
    return initials;
  }
}

Carson10.java

package lecture1108;

import java.util.Arrays;
import java.util.Scanner;

public class Carson10 {
  public static void main(String[] args) {
    String[] results = {
      "Brent Kann,31,56:31.4",
      "Brent Wathke,34,1:01:47.4",
      "Ken Ellingsen,21,1:02:48.3",
      "Elise Sigg,27,1:02:56.3",
      "Matt Carter,46,1:03:09.4",
      "Andrew Komp,40,1:03:10.9",
      "Jason Beckerman,45,1:04:39.0",
      "Stephanie Cloutier,26,1:04:57.3",
      "Cole Cloutier,26,1:04:57.8",
      "Josh Webb,41,1:06:03.3",
      "Cody Buckli,24,1:06:42.6",
      "Jamie Riley,30,1:07:00.2",
      "Garrett Hrubesch,27,1:08:43.4",
      "Allan Stierer,61,1:10:25.4",
      "Jennifer Reeves,32,1:10:45.6",
      "Chris Huse,56,1:11:17.9",
      "Anne Schreiber,20,1:12:46.9",
      "Dayeton Tolle,20,1:13:39.6",
      "Noah Harmuth,20,1:15:00.9",
      "Tim Case,37,1:15:11.7",
      "Theresa Monpas,29,1:15:37.0",
      "melissa zajec,41,1:16:15.0",
      "Jeremy Reeves,28,1:16:22.1",
      "Chris Vetter,44,1:16:44.6",
      "Rachel Drescher,39,1:16:50.4",
      "Jamie McGuire,32,1:17:07.8",
      "Mandy Schoelzel,39,1:17:10.0",
      "Molly Barnes,44,1:19:05.3",
      "Alec Augustyn,16,1:20:18.5",
      "Carli Palmer,40,1:20:25.5",
      "melanie reed,40,1:21:43.5",
      "Camarie Slagle,19,1:21:46.0",
      "Gina Young,39,1:22:26.1",
      "Sarah Wergeland,38,1:22:31.6",
      "Vicky Ebensperger,48,1:24:25.2",
      "Grace Hogan,36,1:24:34.5",
      "nicole Brandner,37,1:25:29.8",
      "Unknown Partic. 324,,1:26:14.0",
      "Traci Messner,54,1:26:36.8",
      "Unknown Partic. 323,,1:28:49.4",
      "Abby Hanlon,31,1:29:01.7",
      "Elizabeth Krieg,33,1:29:39.0",
      "Karley Bahr,25,1:29:45.8",
      "Tom Glenetzke,53,1:29:45.8",
      "Vince Friedel,19,1:30:11.0",
      "Unknown Partic. 215,,1:30:24.8",
      "Alyssa Larsen,40,1:30:43.0",
      "Bruce Buchholz,52,1:30:53.8",
      "Unknown Partic. 158,,1:31:10.6",
      "Unknown Partic. 161,,1:31:11.1",
      "Christopher Martinson,23,1:31:50.4",
      "Michelle Lange,62,1:32:53.8",
      "Christy Larson,46,1:33:09.9",
      "Rich Chryst,60,1:33:17.6",
      "Kelly Bresina,29,1:33:21.0",
      "Katie Ives,30,1:33:22.9",
      "Michelle Gibson,28,1:33:23.4",
      "Jerry Wink,42,1:33:34.0",
      "Reid Ferguson,54,1:34:00.7",
      "Christopher Moberg,49,1:34:02.2",
      "Brianna Hestekin,33,1:34:39.7",
      "Jim Janezic,58,1:35:06.1",
      "Jodi Stevens,37,1:35:16.8",
      "Shauna Walther,36,1:35:20.8",
      "Jennifer Wiltgen,39,1:35:21.8",
      "Unknown Partic. 187,,1:35:21.8",
      "Jamie Krause,38,1:35:25.1",
      "Ann Phillips,51,1:36:48.4",
      "Patrick Batz,47,1:37:39.7",
      "Todd Kuennen,45,1:37:39.8",
      "Aaron Walczak,43,1:37:40.0",
      "Shirley Cervantes,56,1:37:51.3",
      "John Hogan,66,1:39:41.0",
      "Dick Lange,63,1:40:53.7",
      "Mary Bodoh-Stone,58,1:41:46.9",
      "Tasha Alexander,37,1:42:10.2",
      "Gary Frueh,58,1:42:29.8",
      "Renee Jablonske,30,1:42:53.4",
      "Scott Honadel,48,1:43:13.7",
      "Jennifer Frueh,45,1:43:27.8",
      "Faith Higdon,41,1:44:12.6",
      "Wendy Schmidley,46,1:46:51.3",
      "Kristy Martin,43,1:46:51.5",
      "Kayleigh Steinmetz,30,1:47:17.2",
      "Mindy Mahr,39,1:47:17.2",
      "Pam Ogden,60,1:47:36.1",
      "Unknown Partic. 191,,1:49:05.5",
      "Patricia Schneider,40,1:49:31.3",
      "Jeffrey Wilson,56,1:49:51.4",
      "Chuck White,42,1:50:00.1",
      "John bachman,65,1:50:25.0",
      "Heather Felty,45,1:59:42.9",
      "Alayne Vetter,29,2:04:25.2",
      "Tadd Faith,44,2:14:25.5",
      "Unknown Partic. 389,,2:16:07.1",
      "Desiree Flanders,36,2:39:22.8",
      "Elise Sitzman,31,2:39:43.0"
    };

    int[] ages = new int[results.length];
    for (int i = 0; i < results.length; ++i) {
      Scanner in = new Scanner(results[i]);
      in.useDelimiter(",");
      in.next();
      if (in.hasNextInt()) {
        int age = in.nextInt();
        ages[i] = age;
      } else {
        ages[i] = -1;
      }
    }

    System.out.println(Arrays.toString(ages));
    
    int oldestSoFar = ages[0];
    for (int i = 1; i < ages.length; ++i) {
      if (ages[i] < oldestSoFar && ages[i] >= 0) {
        oldestSoFar = ages[i];
      }
    }
    
    System.out.println(oldestSoFar);
    
    int iPerson = find(results);
    System.out.println(iPerson + 1);
  }
  
  private static int find(String[] results) {
    for (int i = 0; i < results.length; ++i) {
      if (results[i].contains("PERSON WE'RE LOOKING FOR")) {
        return i;
      }
    }
    return -1;
  }
}

Music.java

package lecture1108;

import java.awt.Desktop;
import java.io.File;
import java.io.IOException;

import hw5.speccheck.Duration;
import hw5.speccheck.Letter;
import hw5.speccheck.Note;
import hw5.speccheck.WavIO;

public class Music {
  public static void main(String[] args) throws IOException {
    Note a4 = new Note(Letter.A, 4, Duration.QUARTER);
    
//    Note[] a4song = {a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4, a4};
    
    
    Note[] scale = new Note[72];
    Note root = new Note(Letter.D, 2, Duration.QUARTER);
    for (int i = 0; i < scale.length; ++i) {
      scale[i] = new Note(root.getHalfstepID() + i, Duration.EIGHTH);
    }
    
    String path = "/Users/johnch/Desktop/song.wav";
    WavIO.write(scale, 200, path);
    
    Desktop desktop = Desktop.getDesktop();
    desktop.open(new File(path));
  }
}

Initialer.java

package lecture1108;

import java.util.Arrays;

public class Initialer {
  public static void main(String[] args) {
    String[] names = {
      "Bill Ding",
      "Paula Ticks",
      "Craig Slist",
      "Brian Storm",
      "Ellie Quint",
      "Why Not"
    };
    
    String[] initials = initialize(names);
    System.out.println(Arrays.toString(initials));
  }
  
  private static String[] initialize(String[] fulls) {
    String[] initials = new String[fulls.length];
    for (int i = 0; i < fulls.length; ++i) {
      char first = fulls[i].charAt(0);
      char last = fulls[i].charAt(fulls[i].indexOf(' ') + 1);
      initials[i] = "" + first + last;
    }
    return initials;
  }
}

Carson10.java

package lecture1108;

import java.util.Arrays;
import java.util.Scanner;

public class Carson10 {
  public static void main(String[] args) {
    String[] results = {
      "Brent Kann,31,56:31.4",
      "Brent Wathke,34,1:01:47.4",
      "Ken Ellingsen,21,1:02:48.3",
      "Elise Sigg,27,1:02:56.3",
      "Matt Carter,46,1:03:09.4",
      "Andrew Komp,40,1:03:10.9",
      "Jason Beckerman,45,1:04:39.0",
      "Stephanie Cloutier,26,1:04:57.3",
      "Cole Cloutier,26,1:04:57.8",
      "Josh Webb,41,1:06:03.3",
      "Cody Buckli,24,1:06:42.6",
      "Jamie Riley,30,1:07:00.2",
      "Garrett Hrubesch,27,1:08:43.4",
      "Allan Stierer,61,1:10:25.4",
      "Jennifer Reeves,32,1:10:45.6",
      "Chris Huse,56,1:11:17.9",
      "Anne Schreiber,20,1:12:46.9",
      "Dayeton Tolle,20,1:13:39.6",
      "Noah Harmuth,20,1:15:00.9",
      "Tim Case,37,1:15:11.7",
      "Theresa Monpas,29,1:15:37.0",
      "melissa zajec,41,1:16:15.0",
      "Jeremy Reeves,28,1:16:22.1",
      "Chris Vetter,44,1:16:44.6",
      "Rachel Drescher,39,1:16:50.4",
      "Jamie McGuire,32,1:17:07.8",
      "Mandy Schoelzel,39,1:17:10.0",
      "Molly Barnes,44,1:19:05.3",
      "Alec Augustyn,16,1:20:18.5",
      "Carli Palmer,40,1:20:25.5",
      "melanie reed,40,1:21:43.5",
      "Camarie Slagle,19,1:21:46.0",
      "Gina Young,39,1:22:26.1",
      "Sarah Wergeland,38,1:22:31.6",
      "Vicky Ebensperger,48,1:24:25.2",
      "Grace Hogan,36,1:24:34.5",
      "nicole Brandner,37,1:25:29.8",
      "Unknown Partic. 324,,1:26:14.0",
      "Traci Messner,54,1:26:36.8",
      "Unknown Partic. 323,,1:28:49.4",
      "Abby Hanlon,31,1:29:01.7",
      "Elizabeth Krieg,33,1:29:39.0",
      "Karley Bahr,25,1:29:45.8",
      "Tom Glenetzke,53,1:29:45.8",
      "Vince Friedel,19,1:30:11.0",
      "Unknown Partic. 215,,1:30:24.8",
      "Alyssa Larsen,40,1:30:43.0",
      "Bruce Buchholz,52,1:30:53.8",
      "Unknown Partic. 158,,1:31:10.6",
      "Unknown Partic. 161,,1:31:11.1",
      "Christopher Martinson,23,1:31:50.4",
      "Michelle Lange,62,1:32:53.8",
      "Christy Larson,46,1:33:09.9",
      "Rich Chryst,60,1:33:17.6",
      "Kelly Bresina,29,1:33:21.0",
      "Katie Ives,30,1:33:22.9",
      "Michelle Gibson,28,1:33:23.4",
      "Jerry Wink,42,1:33:34.0",
      "Reid Ferguson,54,1:34:00.7",
      "Christopher Moberg,49,1:34:02.2",
      "Brianna Hestekin,33,1:34:39.7",
      "Jim Janezic,58,1:35:06.1",
      "Jodi Stevens,37,1:35:16.8",
      "Shauna Walther,36,1:35:20.8",
      "Jennifer Wiltgen,39,1:35:21.8",
      "Unknown Partic. 187,,1:35:21.8",
      "Jamie Krause,38,1:35:25.1",
      "Ann Phillips,51,1:36:48.4",
      "Patrick Batz,47,1:37:39.7",
      "Todd Kuennen,45,1:37:39.8",
      "Aaron Walczak,43,1:37:40.0",
      "Shirley Cervantes,56,1:37:51.3",
      "John Hogan,66,1:39:41.0",
      "Dick Lange,63,1:40:53.7",
      "Mary Bodoh-Stone,58,1:41:46.9",
      "Tasha Alexander,37,1:42:10.2",
      "Gary Frueh,58,1:42:29.8",
      "Renee Jablonske,30,1:42:53.4",
      "Scott Honadel,48,1:43:13.7",
      "Jennifer Frueh,45,1:43:27.8",
      "Faith Higdon,41,1:44:12.6",
      "Wendy Schmidley,46,1:46:51.3",
      "Kristy Martin,43,1:46:51.5",
      "Kayleigh Steinmetz,30,1:47:17.2",
      "Mindy Mahr,39,1:47:17.2",
      "Pam Ogden,60,1:47:36.1",
      "Unknown Partic. 191,,1:49:05.5",
      "Patricia Schneider,40,1:49:31.3",
      "Jeffrey Wilson,56,1:49:51.4",
      "Chuck White,42,1:50:00.1",
      "John bachman,65,1:50:25.0",
      "Heather Felty,45,1:59:42.9",
      "Alayne Vetter,29,2:04:25.2",
      "Tadd Faith,44,2:14:25.5",
      "Unknown Partic. 389,,2:16:07.1",
      "Desiree Flanders,36,2:39:22.8",
      "Elise Sitzman,31,2:39:43.0"
    };
    
    int[] ages = new int[results.length];
    for (int i = 0; i < ages.length; ++i) {
      String[] fields = results[i].split(",");
//      System.out.println(Arrays.toString(fields));
      if (fields[1].isEmpty()) {
        ages[i] = -1;
      } else {
        ages[i] = Integer.parseInt(fields[1]);
      }
    }
    
    int oldestSoFar = ages[0];
    for (int i = 1; i < ages.length; ++i) {
      if (ages[i] > oldestSoFar) {
        oldestSoFar = ages[i];
      }
    }
    System.out.println(oldestSoFar);
    
    int iPerson = find(results);
    System.out.println(results[iPerson]);
    
//    System.out.println(Arrays.toString(ages));
  }
  
  private static int find(String[] results) {
    for (int i = 0; i < results.length; ++i) {
      if (results[i].contains("PERSON WE'RE LOOKING FOR")) {
        return i;
      }
    }
    return -1;
  }
}