teaching machines

CS1: Lecture 30 – 2D Arrays and ArrayList

November 11, 2019 by Chris Johnson. Filed under cs1, fall 2019, lectures.

Dear students,

Today we will complete a whirlwind tour through a couple of concepts that really deserve a couple of conversations each. These concepts are two-dimensional arrays and ArrayList.

Two-dimensional Arrays

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:

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

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 an array 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]);
    }
  }
}

Growable Arrays

Enter ArrayList. It wraps around an array in Java and makes it feel resizable. Internally, it keeps an array of some fixed size. When it fills up, it creates a new array that’s bigger, copies over the data, and ditches the old array.

For the most part, we can treat arrays and ArrayLists the same. Their interface is slightly different. The following table contrasts their operations:

We’ll explore the use of ArrayList in the context of simulating the card game War.

TODO

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

• CS 145, your lab is posted.
• There’s no lecture on Wednesday or Friday of this week, and no CS 148 lab on Thursday.
• Read chapter 7, from section 7.3 to the end, and chapter 10 through section 10.1. You may also want to consult YouTube for more examples of 2D arrays and ArrayLists.
• After you finish homework 4, start homework 5, which will be due December 1. I’ve placed this due date after Thanksgiving break for those that want the extra time, but I encourage you to finish before break. I will not be checking Piazza or email during break, so plan accordingly. Make use of the extra time you have this week to get a good start.

See you next class!

Sincerely,

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

2D is tiny
3D’s thicker, but 4D?
We’ll run out of space

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

Birthdays.java

package lecture1111.cs145;

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.csv"));

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

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

      tallies[month - 1][day - 1]++;
    }

    for (int m = 0; m < tallies.length; ++m) {
      // I have a month row in hand with tallies[m]
      for (int d = 0; d < tallies[m].length; ++d) {
//        System.out.printf("%3d", tallies[m][d]);
        if (tallies[m][d] > 1) {
          System.out.printf("%d %d -> %d%n", m + 1, d + 1, tallies[m][d]);
        }
      }
      System.out.println();
    }

    in.close();
  }
}

War.java

package lecture1111.cs145;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class War {
  public static void main(String[] args) {
    ArrayList<Integer> deck1 = getDeck();
    ArrayList<Integer> deck2 = getDeck();

    Collections.shuffle(deck1);
    Collections.shuffle(deck2);

    while (!deck1.isEmpty() && !deck2.isEmpty()) {
      int card1 = deck1.remove(0);
      int card2 = deck2.remove(0);

      if (card1 > card2) {
        deck1.add(card1);
        deck1.add(card2);
      } else if (card2 > card1) {
        deck2.add(card1);
        deck2.add(card2);
      } else {
        deck1.add(card1);
        deck2.add(card2);
      }

      System.out.printf("%d vs. %d%n", deck1.size(), deck2.size());
    }
  }

  public static ArrayList<Integer> getDeck() {
    ArrayList<Integer> deck = new ArrayList<Integer>();

    for (int i = 2; i <= 14; i++) {
      deck.add(i);
      deck.add(i);
      deck.add(i);
      deck.add(i);
    }

    return deck;
  }
}

Birthdays.java

package lecture1111.cs148;

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

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

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

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

    for (int m = 0; m < tallies.length; m++) {
      // tallies[m] is a month's array
      for (int d = 0; d < tallies[m].length; d++) {
        if (tallies[m][d] > 1) {
          System.out.printf("%d %d -> %2d%n", m + 1, d + 1, tallies[m][d]);
        }
      }
    }

    in.close();
  }
}

War.java

package lecture1111.cs148;

import java.util.ArrayList;
import java.util.Collections;

public class War {
  public static void main(String[] args) {
    ArrayList<Integer> deck = getDeck();
    Collections.shuffle(deck);
    System.out.println(deck);
  }

  public static ArrayList<Integer> getDeck() {
    ArrayList<Integer> deck = new ArrayList<Integer>();

    for (int i = 1; i <= 13; i++) {
      deck.add(i);
      deck.add(i);
      deck.add(i);
      deck.add(i);
    }

    return deck;
  }
}