teaching machines

CS 1: Lecture 29 – Growable Arrays

Dear students,

Arrays make the modern world happen. The computer itself can be viewed as one big array, lining up all our data, music, photos, and movies on disks and in RAM. However, arrays have their limits. In particular, arrays are fixed in size. We need to know their size when we create them. Sometimes the size is not information we have. Adding something to an array is not possible. It’s also awkward to remove something from an array. We might null or zero out an element, but its shadow is still there. The length property will report the same number throughout the array’s lifetime.

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:

operation array ArrayList
create type[] id = new type[#]; ArrayList<Type> id = new ArrayList<Type>();
get count id.length id.size()
read item id[i] id.get(i)
write item id[i] = expr; id.set(i, expr)
append item not supported id.add(item)
remove item not supported id.remove(item) or id.remove(index)

Let’s see ArrayLists in action through the following exercises:

  • loading up a word list from a file
  • A well-dressed man approaches you with two decks of cards in hand. He says, “Let us play a game. Here’s your deck. Here is mine. We turn over our cards one at a time. If any match, I win and you give me $5. If none match, you win and I give you $5.” Should you play this game?
  • playing the card game War

We’ll solve the second of these through a Monte Carlo simulation. Such a simulation can be summarized as follows: simulate a phenomenon n times and compute your expected value of some measure of interest as the average across all runs. Here’s an interesting historical note about the first formal description of the Monte Carlo simulation from physicist Stanislaw Ulam:

The first thoughts and attempts I made to practice [the Monte Carlo Method] were suggested by a question which occurred to me in 1946 as I was convalescing from an illness and playing solitaires. The question was what are the chances that a Canfield solitaire laid out with 52 cards will come out successfully? After spending a lot of time trying to estimate them by pure combinatorial calculations, I wondered whether a more practical method than “abstract thinking” might not be to lay it out say one hundred times and simply observe and count the number of successful plays. This was already possible to envisage with the beginning of the new era of fast computers, and I immediately thought of problems of neutron diffusion and other questions of mathematical physics, and more generally how to change processes described by certain differential equations into an equivalent form interpretable as a succession of random operations. Later [in 1946], I described the idea to John von Neumann, and we began to plan actual calculations.

Ulam and von Neumann used the ENIAC, one of the first programmable computers, to simulate various physical phenomena for the Manhattan Project and the hydrogen bomb. We’ll just use it for gambling.

We’re going to write a few helper methods to support this:

  • A method to generate a deck. We can create an array of suits and an array of ranks, like these:
    String[] suits = {"\u2665", "\u2666", "\u2660", "\u2663"};
    String[] ranks = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
    
    We can visit all possible pairs and add each to an ArrayList.
  • A method to shuffle a deck. We’ll apply the Fisher-Yates algorithm for this:
    for each index i in reverse
      j = random number in [0, i]
      swap items i and j
  • A method for simulating one session of the game. We’ll have to go through both decks, comparing the cards that we turn over:
    for each pair of cards
      if they're the same
        the man wins
    we win
    Let’s have the method return the amount of money gained or lost.
  • A main method that plays the game many times to see what sort of gain or loss we can expect to see.

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

  • Midterm 2 happens on Monday.

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

After a big meal
I move to a new body
People think it’s growth

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

Table.java

package lecture1115;

import java.util.Arrays;

public class Table {
  public static void main(String[] args) {
//    System.out.println(Arrays.deepToString(timesTable(5, 4)));
    int[][] table = timesTable(5, 4);
    
    System.out.print("   ");
    for (int c = 0; c < table[0].length; ++c) {
      System.out.printf("%3d", c);
    }
    System.out.println();
    
    for (int r = 0; r < table.length; ++r) {
      System.out.printf("%3d", r);
      for (int c = 0; c < table[r].length; ++c) {
        System.out.printf("%3d", table[r][c]);
      }
      System.out.println();
    }
  }
  
  private static int[][] timesTable(int w, int h) {
    int[][] table = new int[h][w];
    
    for (int r = 0; r < table.length; ++r) {
      for (int c = 0; c < table[r].length; ++c) {
        table[r][c] = c * r;
      }
    }
    
    return table;
  }
}

Suffix.java

package lecture1115;

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

public class Suffix {
  public static void main(String[] args) throws FileNotFoundException {
    ArrayList<String> words = new ArrayList<>();
    Scanner dictionary = new Scanner(new File("/usr/share/dict/words"));
    while (dictionary.hasNextLine()) {
      words.add(dictionary.nextLine());
    }
    dictionary.close();
    
    String suffix = "phobia";
    for (int i = 0; i < words.size(); ++i) {
      if (words.get(i).endsWith(suffix)) {
        System.out.println(words.get(i));
      }
    }
  }
}

MonteCarlo.java

package lecture1115;

import java.util.ArrayList;
import java.util.Random;

public class MonteCarlo {
  public static void main(String[] args) {
    ArrayList<String> deck1 = getDeck();
    ArrayList<String> deck2 = getDeck();
    shuffle(deck1);
    System.out.println(deck1);
  }
  
  public static void shuffle(ArrayList<String> deck) {
    Random g = new Random();
    for (int i = deck.size() - 1; i >= 0; --i) {
      int j = g.nextInt(i + 1);
      String tmp = deck.get(i);
      deck.set(i, deck.get(j));
      deck.set(j, tmp);
    }
  }
  
  public static ArrayList<String> getDeck() {
    String[] suits = {"\u2665", "\u2666", "\u2660", "\u2663"};
    String[] ranks = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
    
    ArrayList<String> deck = new ArrayList<String>();
    
    for (String suit : suits) {
      for (String rank : ranks) {
        deck.add(rank + suit);
      }
    }
    
    return deck;
  }
}

Comments

Leave a Reply

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