» CS 1: Lecture 27 – Array Patterns, Part 2

CS 1: Lecture 27 – Array Patterns, Part 2

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

Dear students,

Last time we started looking at a few array patterns: map, linear search, and optimize. Today we visit the last of these: the accumulate pattern. Accumulation algorithms collect all the data up into one big value. Finding the sum, mean, and product of a bunch of numbers fits this description. So does joining a bunch of strings, counting occurrences, checking if all items meet some criteria, and checking if any items meet some criteria. The accumulate pattern looks like this:

initialize runningValue
for each item
  accumulate item into runningValue

One of you asked how we could turn an array into a String without the square brackets that Arrays.toString inserts. We could write our own version:

public static String join(int[] numbers) {
  String series = "";

  for (int i = 0; i < numbers.length; ++i) {
    series += numbers[i];
  }

  return series;
}

But for {1, 2, 30}, this generates "1230". It’s hard to separate the numbers. Let’s change our loop to insert a comma:

for (int i = 0; i < numbers.length; ++i) {
  series += numbers[i];
}

But this generates "1,2,30,". That trailing comma probably shouldn’t be there. Let’s solve this with a loop-and-half:

series += numbers[0];
for (int i = 0; i < numbers.length; ++i) {
  series += "," + numbers[i];
}

But what if the array is empty? Let’s guard against that possibility:

if (numbers.length > 0) {
  series += numbers[0];
  for (int i = 0; i < numbers.length; ++i) {
    series += "," + numbers[i];
  }
}

As a second example of accumulate, let’s write a score21 method that computes a Blackjack score for a hand of cards given as an array of ints. Aces will be sent along as 1s, jacks as 11s, queens as 12s, and kings as 13—because, as we all know, kings are unlucky. Initially, let’s just count them all up without any regard for the rules:

public static int score21(int[] hand) {
  int sum = 0; 

  for (int i = 0; i < hand.length; ++i) {
    sum += hand[i];
  }

  return sum;
}

Now let’s consider that jacks, queens, and kings only contribute 10. We could write an if statement, or to avoid another level of indentation, we can use Math.min:

sum += Math.min(hand[i], 10);

The aces are a little tricky to count, so let’s actually not count them:

public static int score21(int[] hand) {
  int sumWithoutAces = 0; 

  for (int i = 0; i < hand.length; ++i) {
    if (hand[i] != 1) {
      sumWithoutAces += Math.min(hand[i], 10);
    }
  }

  return sumWithoutAces;
}

If this much works, then and only then should we move on to the harder part. Aces are tricky because they either count as 1 or 11. To write the code, it helps to realize that at most one ace can count as 11. Anything else shoots us past 21, which is affectionately called going bust. If we go bust, we lose. So, let’s just try counting the aces both ways. We’ll go with the score that gets us higher without going over 21:

public static int score21(int[] hand) {
  int sumWithoutAces = 0; 
  int nAces = 0;

  for (int i = 0; i < hand.length; ++i) {
    if (hand[i] != 1) {
      sumWithoutAces += Math.min(hand[i], 10);
    } else {
      ++nAces;
    }
  }

  if (nAces == 0) {
    return sumWithoutAces;
  } else if (sumWithoutAces + 11 + nAces - 1 <= 21) { // count one at 11, the rest at 1
    return sumWithoutAces + 11 + nAces - 1;
  } else { // count all at 1
    return sumWithoutAces + nAces;
  }
}

The first and third cases can be consolidated, but we’ll keep them explicitly separate for clarity. Humans matter as much as the machine.

Now that’s we discussed all four patterns, let’s do some blackboxes!

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

Read chapter 7 through section 7.2 in your book. Solve two problems from Array-1 and two problems from Array-2 on Coding Bat. On a quarter sheet, write down the names of the problems you solved and at least one of the solutions.
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!

“Gotta catch ’em all”
Put them in one Poké ball
That’s me in eighth grade

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

Concatenate.java

package lecture1110;

public class Concatenate {
  public static void main(String[] args) {
    int[] numbers = {13, 5, 42, 73, 21};
    String series = join(numbers);
    System.out.println(series);
  }

  private static String join(int[] numbers) {
    String s = "";

    if (numbers.length > 0) {
      s += numbers[0];
      for (int i = 1; i < numbers.length; ++i) {
        s += ", " + numbers[i];
      }
    }

    return s;
  }
}

Blackjack.java

package lecture1110;

public class Blackjack {
  public static void main(String[] args) {
    int[] hand = {};
    System.out.println(score21(hand));
  }
  
  private static int score21(int[] hand) {
    
    int sumWithoutAces = 0;
    int nAces = 0;
    for (int rank : hand) {
      if (rank != 1) {
        sumWithoutAces += Math.min(rank, 10);
      } else {
        ++nAces;
      }
    }
    
    if (nAces == 0) {
      return sumWithoutAces;
    } else if (sumWithoutAces + 11 + (nAces - 1) <= 21) {
      return sumWithoutAces + 11 + (nAces - 1);
    } else {
      return sumWithoutAces + nAces;
    }
  }
}

Chords.java

package lecture1110;

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

public class Chords {
  public static void main(String[] args) {
    Note c4 = new Note(Letter.C, 4, Duration.WHOLE);
    Note e4 = new Note(Letter.E, 4, Duration.WHOLE);
    Note b5 = new Note(Letter.B, 5, Duration.WHOLE);
    
    short[] cSamples = c4.getSamples(10);
    short[] eSamples = e4.getSamples(10);
    
    short[] samples = new short[cSamples.length];
    for (int i = 0; i < cSamples.length; ++i) {
      samples[i] = (short) (0.5 * cSamples[i] + 0.5 * eSamples[i]);
    } 

    WavIO.write(samples, "/Users/johnch/Desktop/song.wav");
  }
}

Joiner.java

package lecture1110;

public class Joiner {
  public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 255};
    //    join(new int[]{1, 2, 3, 4});
    System.out.println(join(nums));
  }

  private static String join(int[] numbers) {
    String s = "";
    if (numbers.length > 0) {
      s += numbers[0];
      for (int i = 1; i < numbers.length; ++i) {
        s = s + "," + numbers[i];
      }
    }
    return s;
  }
}

Blackjack.java

package lecture1110;

public class Blackjack {
  public static void main(String[] args) {
    int[] hand = {
      13,
      1,
      1
    };
    System.out.println(score21(hand));
  }

  private static int score21(int[] hand) {
    int sumWithoutAces = 0;
    int nAces = 0;
    
    for (int i = 0; i < hand.length; ++i) {
      if (hand[i] > 10) {
        sumWithoutAces += 10;
      } else if (hand[i] == 1) {
        ++nAces;
      } else {
        sumWithoutAces += hand[i];
      }
    }
    
    if (nAces == 0) {
      return sumWithoutAces;
    } else if (sumWithoutAces + 11 + nAces - 1 <= 21) {
      return sumWithoutAces + 11 + nAces - 1;
    } else {
      return sumWithoutAces + nAces;
    }
  }
}