teaching machines

CS1: Lecture 29 – Bundled Data

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

Dear students,

Last time we used arrays as a means to map integers to values. We associated our data with 0, 1, 2, 3, and so on. When we got a new piece of data in, we use its index to reach inside our array directly. Today we shine the spotlight on arrays as a means for making bundles of data. The indices aren’t nearly so important as the ability of the array to collect up our information under one name.

Initializer Lists

In our first examples, we built up the array as we processed the input. Sometimes we know what data should go in the array ahead of time. We could just assign the elements one at a time:

String[] names = new String[7];
names[0] = "Sunday";
names[1] = "Monday";
names[2] = "Tuesday";
names[3] = "Wednesday";
names[4] = "Thursday";
names[5] = "Friday";
names[6] = "Saturday";

But it’s usually preferable to use an initializer list:

String[] names = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

Arrays can often replace decision structures that we write to simply choose between data. For instance, we might write a program that draws stripes across an image. Without arrays, we’d use an if statement to pick our color:

create image
for each row r
  for each column c
    if c % nstripes == 0
      pick first color
    elsif c % nstripes == 1
      pick second color
    elsif c % nstripes == 2
      pick third color
    elsif ...
      ...
    else
      pick last color
    set pixel (c, r) to color

But with arrays, we can do a much simpler lookup into a collection of colors:

colors = [color0, color1, color2, ...]
create image
for each row r
  for each column c
    i = c % number of colors
    set pixel (c, r) to color

Bundling Data

Another really nice thing about arrays is that they all us to pass bundles of data back and forth between methods. 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. The aces are a little tricky to count, so let’s just not count them initially:

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;
}

We clamp the rank at 10, because that’s how much jacks, queens, and kings contribute to the score.

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.

Shell

For our last example, let’s write a poor man’s shell, which is a text-based means of navigating a computer’s file system. It is an alternative to the Finder on macOS and File Explorer on Windows. We want to be able to have interactions like this:

> where
/Users/johnch
> what
a.txt
Documents
dogs_playing_blackjack.png
Music
Videos
> into Music
> where
/Users/johnch/Music
> open moana_ost.mp3
> up
> where
/Users/johnch

Let’s start with a non-functional read-eval-print-loop (REPL):

Scanner in = new Scanner(System.in);

System.out.print("> ");
while (in.hasNext()) {
  String command = in.next();
  if (command.equals("where")) {
  } else if (command.equals("what")) {
  } else if (command.equals("open")) {
  } else if (command.equals("up")) {
  } else if (command.equals("into")) {
  } else {
    System.out.println("Wakarimasen. No comprendo.");
  }

  System.out.print("> ");
}

To get where working, we need to track our current directory. Since this information lives longer than a single iteration of the loop, we declare it outside the loop:

File currentDirectory = new File(System.getProperty("user.home"));
...

while (in.hasNext()) {
  if (command.equals("where")) {
    System.out.println(currentDirectory.getAbsolutePath());
  }

We can implement up and into using this directory:

} else if (command.equals("up")) {
  currentDirectory = currentDirectory.getParentFile();
} else if (command.equals("into")) {
  currentDirectory = new File(currentDirectory, in.next());
}

We can implement open with a little help from the Desktop class:

Desktop desktop = Desktop.getDesktop();
...

while (in.hasNext()) {
  ...
  } else if (command.equals("open")) {
    desktop.open(new File(currentDirectory, in.next()));
  }

And finally, let’s implement what, which is where arrays as a means of bundling data comes in. The File class has a method list that returns an arrays of Strings. When the file is really a directory or folder, then the array contains the names of all the files inside that directory. We can use it like this:

} else if (command.equals("what")) {
  String[] children = currentDirectory.list();
  for (int i = 0; i < children.length; ++i) {
    System.out.println(children[i]);
  }
}

This works, more or less, but there two things we need to address. If a directory contains no children, null is returned. We can’t access null for its length—it is the non-array, not the empty array. Second, the indices don’t really matter to us here. We are only using i as a hook into our array. Java 5 added a simpler loop that abstracts away the indexing when we don’t need it:

} else if (command.equals("what")) {
  String[] children = currentDirectory.list();
  if (children != null) {
    for (String child : children) {
      System.out.println(children[i]);
    }
  }
}

TODO

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

• Keep at homework 4. Run the SpecChecker. Read Piazza posts. Ask questions on Piazza. Commit and push every day. Run the remote SpecChecker with test hw4.

See you next class!

Sincerely,

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

float[] numbers = {0.01, 0.03, 0.008};

These numbers are small
See how I nailed each one down?
Else they’d float array

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

BlackJack.java

package lecture1108.cs145;

public class BlackJack {
  public static final int ACE = 1;
  public static final int JACK = 11;
  public static final int QUEEN = 12;
  public static final int KING = 13;

  public static void main(String[] args) {
    int[] hand = {5, ACE, 10};
    System.out.printf("%d%n", score(hand));
  }

  public static int score(int[] hand) {
    int total = 0;
    int nAces = 0;

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

    if (nAces > 0) {
      int sumWith11 = total + 11 + nAces - 1;
      int sumWithout11 = total + nAces;

//      if (sumWith11 <= 21) {
//        total = sumWith11;
//      } else {
//        total = sumWithout11;
//      }

      total = (sumWith11 <= 21) ? sumWith11 : sumWithout11;
    }

    return total;
  }
}

Shell.java

package lecture1108.cs145;

import java.awt.*;
import java.io.File;
import java.io.IOException;

public class Shell {
  public static void main(String[] args) throws IOException {
  }
}

BlackJack.java

package lecture1108.cs148;

public class BlackJack {
  public static final int ACE = 1;
  public static final int JACK = 11;
  public static final int QUEEN = 12;
  public static final int KING = 13;

  public static void main(String[] args) {
    int[] hand = {JACK, ACE, ACE};
    System.out.printf("%d%n", score(hand));
  }

  public static int score(int[] hand) {
    int someTotal = 0;
    int nAces = 0;
    for (int rank : hand) {
      if (rank == ACE) {
        ++nAces;
      } else {
        someTotal += Math.min(rank, 10);
      }
    }

    if (nAces > 0) {
      int sumWith11 = someTotal + 11 + nAces - 1;
      int sumWithout11 = someTotal + nAces;
      if (sumWith11 <= 21) {
        someTotal = sumWith11;
      } else {
        someTotal = sumWithout11;
      }
    }

    return someTotal;
  }
}

Breakout.java

package lecture1108.cs148;

public class Breakout {
  public static void main(String[] args) {
    int i = 0;

    FOO:
    while (true) {
      System.out.println("while loop going");
      switch (i) {
        case 0:
          break FOO;
      }
    }
  }
}