teaching machines

CS 145 Lecture 30 – ArrayList

November 18, 2016 by Chris Johnson. Filed under
Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383

Deprecated: Creation of dynamic property WP_Term::$cat_ID is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 378

Deprecated: Creation of dynamic property WP_Term::$category_count is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 379

Deprecated: Creation of dynamic property WP_Term::$category_description is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 380

Deprecated: Creation of dynamic property WP_Term::$cat_name is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 381

Deprecated: Creation of dynamic property WP_Term::$category_nicename is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 382

Deprecated: Creation of dynamic property WP_Term::$category_parent is deprecated in /var/www/twodee/blog/wp-includes/category.php on line 383
cs145, fall 2016, lectures.

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. Just like you wrap around a pair of shoes.

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
• playing the card game War
• 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?

We’ll solve the last 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 to for gambling.

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

• Midterm 2 happens on Monday (November 21). Topics we’ve covered since the last exam include the various classes of operators that deal with booleans, conditional statements, loops, and arrays. The exam is structured much like the last—with some multiple choice and fill in the blanks followed by a few exercises where you must write code.
• The amnesty period opens Saturday, November 19, and closes Sunday, November 27. During this time you can resubmit missed homework assignments (only homeworks are eligible, no labs). I will regrade a homework submission under the following conditions:
  • For each homework you want regraded, you correctly complete one of the tasks below.
  • You fix your homework submission, commit, and push to Bitbucket.
  • You email me one message per regrade request with the following: the number of the homework you have resubmitted, your code and a screenshot that shows that you completed the task.
  Here are the tasks you may choose from:
  • Complete Problem 1 – Multiples of 3 and 5 on Project Euler.
  • Complete Problem 8 – Largest product in a series on Project Euler.
  • Create a holiday ornament (for a holiday of your choosing) in Madeup.
  • Get three stars on every level of generations 0 through 4 of Trux Falsy.

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

I wanted three kids
She two, so just to be safe…
We bought a schoolbus

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

Suffixer.java

package lecture1118;

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

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

Cards.java

package lecture1118;

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

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

// deck1.remove(51);
// deck1.remove(38);
// deck1.remove(25);
// deck1.remove(12);

    shuffle(deck1);

    ArrayList<String> deck2 = getDeck();
    shuffle(deck2);

// System.out.println(deck);

    int i = 0;
    while (deck1.size() > 0 && deck2.size() > 0) {
      System.out.printf("%d vs %d%n", deck1.size(), deck2.size());
      playRound(deck1, deck2);
      ++i;
      if (i > 100) {
        i = 0;
        shuffle(deck1);
        shuffle(deck2);
      }
    }
  }

  private static void playRound(ArrayList<String> deck1, ArrayList<String> deck2) {
    String card1 = deck1.remove(0);
    String card2 = deck2.remove(0);
    if (getWorth(card1) > getWorth(card2)) {
      deck1.add(card1);
      deck1.add(card2);
    } else if (getWorth(card1) < getWorth(card2)) {
      deck2.add(card1);
      deck2.add(card2);
    } else {
      deck1.add(card1);
      deck2.add(card2);
//      ArrayList<String> pile = new ArrayList<String>();
//      pile.add(card1);
//      pile.add(card2);
//
//      while (deck1.size() > 0 && deck2.size() > 0 && getWorth(card1) == getWorth(card2)) {
//        card1 = deck1.remove(0);
//        card2 = deck2.remove(0);
//        pile.add(card1);
//        pile.add(card2);
//      }
//
//      if (deck1.size() == 0 && deck2.size() == 0) {
//        System.out.println("Tie!");
//      } else if (deck1.size() == 0) {
//        System.out.println("Player two wins!");
//      } else if (deck2.size() == 0) {
//        System.out.println("Player one wins!");
//      } else if (getWorth(card1) > getWorth(card2)) {
//        for (String card : pile) {
//          deck1.add(card);
//        }
//      } else if (getWorth(card1) < getWorth(card2)) {
//        for (String card : pile) {
//          deck2.add(card);
//        }
//      }
    }
  }

  private static void shuffle(ArrayList<String> deck) {
    Random generator = new Random();
    for (int i = deck.size() - 1; i > 0; --i) {
      int j = generator.nextInt(i + 1);
      String tmp = deck.get(i);
      deck.set(i, deck.get(j));
      deck.set(j, tmp);
    }
  }

  private static int getWorth(String cardLabel) {
    if (cardLabel.startsWith("A")) {
      return 1;
    } else if (cardLabel.startsWith("J")) {
      return 11;
    } else if (cardLabel.startsWith("Q")) {
      return 12;
    } else if (cardLabel.startsWith("K")) {
      return 13;
    } else {
      return Integer.parseInt(cardLabel.substring(0, cardLabel.length() - 1));
    }
  }

  private 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<>();

    for (String suit : suits) {
      for (String rank : ranks) {
        deck.add(rank + suit);
      }
    }

    return deck;
  }
}

War.java

package lecture1118;

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

public class War {
  public static void main(String[] args) {
    ArrayList<String> deck1 = getDeck();
    ArrayList<String> deck2 = getDeck();
    
    deck1.remove(51);
    deck1.remove(38);
    deck1.remove(25);
    deck1.remove(12);

    shuffle(deck1);
    shuffle(deck2);

    int i = 0;
    while (!deck1.isEmpty() && !deck2.isEmpty()) {
      System.out.println(deck1.size() + " vs. " + deck2.size());
      playOneRound(deck1, deck2);
      ++i;
      if (i > 100) {
        shuffle(deck1);
        shuffle(deck2);
        i = 0;
      }
    }
  }
  
  private static void playOneRound(ArrayList<String> deck1,
                                   ArrayList<String> deck2) {
    String card1 = deck1.remove(0);
    String card2 = deck2.remove(0);

    if (getWorth(card1) > getWorth(card2)) {
      deck1.add(card1);
      deck1.add(card2);
    } else if (getWorth(card1) < getWorth(card2)) {
      deck2.add(card1);
      deck2.add(card2);
    } else {
      deck1.add(card1);
      deck2.add(card2);
    }
  }
  
  private static int getWorth(String card) {
    if (card.startsWith("A")) {
      return 1;
    } else if (card.startsWith("J")) {
      return 11;
    } else if (card.startsWith("Q")) {
      return 12;
    } else if (card.startsWith("K")) {
      return 13;
    } else {
      return Integer.parseInt(card.substring(0, card.length() - 1));
    }
  }
  
  private static void shuffle(ArrayList<String> deck) {
    // for i from n−1 downto 1 do
    //   j ← random integer such that 0 ≤ j ≤ i
    //   exchange a[j] and a[i]
    
    Random generator = new Random();
    for (int i = deck.size() - 1; i >= 1; --i) {
      int j = generator.nextInt(i + 1);
      
      // tmp = a
      // a = b
      // b = tmp
      
      String tmp = deck.get(i);
      deck.set(i, deck.get(j));
      deck.set(j, tmp);
    }
  }

  private 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 (int si = 0; si < suits.length; ++si) {
      for (int ri = 0; ri < ranks.length; ++ri) {
        String card = ranks[ri] + suits[si];
        deck.add(card);
      }
    }
    
    return deck;
  }
}

Bet.java

package lecture1118;

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

public class Bet {
  public static void main(String[] args) {

    int earnings = 0;
    final int N = 10000000; 
    for (int i = 0; i < N; ++i) {
      ArrayList<String> deck1 = getDeck();
      ArrayList<String> deck2 = getDeck();
      shuffle(deck1);
      shuffle(deck2);
      int payoff = play(deck1, deck2);
      earnings += payoff;
    }
    
    System.out.println(earnings);
    System.out.println(earnings / (double) N);
  }
  
  private static int play(ArrayList<String> deck1,
                          ArrayList<String> deck2) {
    for (int i = 0; i < deck1.size(); ++i) {
      if (deck1.get(i).equals(deck2.get(i))) {
        return -5;
      }
    }
    return 5;
  }

  private static void shuffle(ArrayList<String> deck) {
    Random generator = new Random();
    for (int i = deck.size() - 1; i > 0; --i) {
      int j = generator.nextInt(i + 1);
      String tmp = deck.get(i);
      deck.set(i, deck.get(j));
      deck.set(j, tmp);
    }
  }

  private 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<>();

    for (String suit : suits) {
      for (String rank : ranks) {
        deck.add(rank + suit);
      }
    }

    return deck;
  }
}