teaching machines

CS 1: Lecture 28 – Arrays in 2D

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

Dear students,

Let’s start today off with some blackboxes. As we solve these, consider which of the four patterns our algorithm fits.

• Blackbox #1
• Blackbox #2
• Blackbox #3
• Blackbox #4
• Blackbox #5

Now let’s consider a famous statistical problem. Suppose birthdays are uniformly distributed across the calendar year. What’s the probability that we in this room all have different birthdays? High or low? How many people need to be in a room before we’re more likely to see at least one repeated birthday? The answer’s 22 and some change. We won’t do the statistics, but let’s do see if our class upholds the statistical prediction.

I have this file of our birthdays:

6 6
7 11
5 9
6 2
2 25
6 18
10 23
6 25
5 14
2 7
5 9
2 24
8 18
4 30
7 28
6 18
7 27
4 21
11 17
8 16
11 28
4 6
8 5
6 1
3 14
7 7
2 21
12 28
10 10
11 2
12 15
11 21
1 28
8 27
9 5
2 10
1 6
8 28
2 25
8 1
2 11
1 30
2 16
4 17
3 22
6 15
6 21
6 12
10 10
4 10
7 25
7 7
7 15
8 4
8 13
12 13
1 23
4 12
3 26
11 20
4 12
6 16
4 15
2 24
6 10
6 29
3 30
7 20
11 6
7 19
2 15
1 15
11 29
10 7
11 26
6 1
7 3
2 13
8 12
12 30
3 31
8 23
11 16
4 11
8 11
5 28
7 28
7 9
2 26
4 11
6 2
8 23
8 16
10 3
3 6
2 27
1 27
3 9
10 7
5 19
7 2
6 6
4 27
7 3
8 25
4 23
3 7
10 8
6 12

Let’s look for repeats. We start with a loop that just reads the input:

Scanner in = new Scanner(new File("birthdays.csv"));

while (in.hasNextInt()) {
  int month = in.nextInt();
  int day = in.nextInt();
}

in.close();

How can figure out if any of these birthdays has been seen before? Let’s keep counters. Everytime we see a birthday, we’ll increment that day’s counter. If any days have 2 or more birthdays, we have a repeat. Here we go:

int[] counts = new int[366];

Great. Maybe. To index into that thing, we will need to turn each day into an index in [0, 365]. This is not impossible, but I think it’s too much work. Remember that pattern we saw for making an array:

type[] name = new type[#];

It turns out that type can itself be an array type—meaning that we can have an array where each element is itself an array. In other words, we can have arrays of arrays. The declaration for such an array looks like this:

int[][] counts = new int[12][31];

This means we’ll have 12 elements in the outer array, and each of those elements will be an array of 31 elements. We can reach into our array with two indices:

counts[0][0] = 17;   // 17 people born on January 1
counts[11][30] = 3;  // 3 people born on December 31

Watch the order of your indices. The outer array spans the months 0 through 11. The inner arrays span the days 0 through 30 within a month. Not every month has 31 days, but there’s no harm in asking for a few more ints that we’ll never use. We can integrate our array into our loop like so:

Scanner in = new Scanner(new File("birthdays.csv"));

int[][] counts = new int[12][31];
while (in.hasNextInt()) {
  int month = in.nextInt();
  int day = in.nextInt();
  ++counts[month - 1][day - 1];
}

in.close();

Okay, we’ve got our tallies. Are there repeats? We’ll have to walk back through the array of arrays to look for them. We could hardcode 12 as the upperbound of our outer index, but it’s safer to ask the array itself how many months there are:

for (int iMonth = 0; iMonth < counts.length; ++iMonth) {
  // counts[iMonth] is the tallies for this month
}

Within this loop, we can visit all of the days. Once again, we ask the array how many days it has in order to get our upper bound:

for (int iMonth = 0; iMonth < counts.length; ++iMonth) {
  for (int iDay = 0; iDay < counts[iMonth].length; ++iDay) {
    // counts[iMonth][iDay] is the tally
  }
}

And finally, we ask which days have more than one person. Let’s also spell out the months by indexing into a helper array:

String[] monthNames = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
for (int iMonth = 0; iMonth < counts.length; ++iMonth) {
  for (int iDay = 0; iDay < counts[iMonth].length; ++iDay) {
    if (counts[iMonth][iDay] > 1) {
      System.out.printf("%s %d saw %d births.%n", monthNames[iMonth], iDay + 1, counts[iMonth][iDay]);
    }
  }
}

If we have time, we’ll generate a bingo table, complete with free space and no repeats. We probably won’t have time.

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

• Our second midterm is Monday, November 20. It will cover logic, conditionals, loops, and arrays. You may bring a single sheet of notes—front and back and is fine. So that I can grade and you can catch up on homework, we will not have lab on Tuesday nor lecture on Wednesday.
• Read the rest of chapter 7, starting at section 7.3. The Reference Semantics section explains some of the differences that we see between primitives and objects/arrays. On a quarter sheet, write method timesTable that accepts two ints named w and h. It returns a 2D int array with h elements in the outer array and w elements in each inner array and filled such that element [r][c] is c * r. For example, timesTable(5, 4) yields the following 2D array:

  	0	1	2	3	4
  0	0	0	0	0	0
  1	0	1	2	3	4
  2	0	2	4	6	8
  3	0	3	6	9	12

See you next class!

Sincerely,

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

Santa keeps no list
for each lat, for each lon, boom!
It’s a checktable

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

Bert.java

package lecture1113;

import java.util.Arrays;

public class Bert {
  public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int[] numsCopy = nums;
    
//    int[] numsCopy = Arrays.copyOf(nums, nums.length * 2);
    
    nums[0] = 1003;
    
    System.out.println(Arrays.toString(nums));
    System.out.println(Arrays.toString(numsCopy));

  }
}

Blackboxes.java

package lecture1113;

import java.util.Arrays;

public class Blackboxes {
  public static void main(String[] args) {
    System.out.println(Arrays.toString(plus1(new int[] {
      1,
      2,
      8,
      6,
      7,
      37,
      25
    })));
    System.out.println(countPositives(new int[] {
      -4,
      -2,
      -100,
      1,
      0
    }));
    System.out.println(longest(new String[] {"a", "bb", "c"}));
  }
  
  private static String longest(String[] ss) {
    String longestSoFar = ss[0];
    for (int i = 1; i < ss.length; ++i) {
      if (ss[i].length() >= longestSoFar.length()) {
        longestSoFar = ss[i];
      }
    }
    
    return longestSoFar;
  }

  private static int countPositives(int[] src) {
    int nPositives = 0;
    for (int i = 0; i < src.length; ++i) {
      if (src[i] > 0) {
        ++nPositives;
      }
    }
    return nPositives;
  }

  private static int[] plus1(int[] src) {
    int[] dst = new int[src.length];
    for (int i = 0; i < src.length; ++i) {
      dst[i] = src[i] + 1;
    }
    return dst;
  }
}

Birthdays.java

package lecture1113;

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

public class Birthdays {
  public static void main(String[] args) throws FileNotFoundException {
    Scanner in = new Scanner(new File("/Users/johnch/Desktop/birthdays.txt"));

//    int[] counts = new int[366];
    int[][] counts = new int[12][31];

    while (in.hasNextInt()) {
      int month = in.nextInt();
      int day = in.nextInt();
      counts[month - 1][day - 1]++;
    }

    String[] monthNames = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
    for (int iMonth = 0; iMonth < counts.length; ++iMonth) {
      for (int iDay = 0; iDay < counts[iMonth].length; ++iDay) {
        if (counts[iMonth][iDay] > 1) {
          System.out.printf("%s %d saw %d births%n", monthNames[iMonth], iDay + 1, counts[iMonth][iDay]);
        }
      }
    }

    in.close();
  }
}