teaching machines

CS 1: Lecture 25 – Arrays as Bundles

November 6, 2017 by . Filed under cs1, cs145, cs148, fall 2017, 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.

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

We’ll write this, and maybe animate it to shift across time.

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.

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
> ls
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("ls")) {
  } 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 ls, 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("ls")) {
  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("ls")) {
  String[] children = currentDirectory.list();
  if (children != null) {
    for (String child : children) {
      System.out.println(children[i]);
    }
  }
}

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

See you next class!

Sincerely,

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

Arrays ruined me
I go a little crazy
When someone writes “1st”

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

Stripes.java

package lecture1106;

import java.awt.Color;
import java.awt.Desktop;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.net.URI;

public class Stripes {
  public static void main(String[] args) throws IOException {
    BufferedImage image = new BufferedImage(400, 200, BufferedImage.TYPE_INT_RGB);
    
//    Color[] colors = new Color[5];
//    colors[0] = Color.ORANGE;
//    colors[1] = new Color(255, 0, 200);
//    colors[2] = Color.BLUE;
//    colors[3] = Color.GREEN;
//    colors[4] = Color.GREEN;
    
    String path = "/Users/johnch/Desktop/foo.gif";
    GifSequenceWriter out = new GifSequenceWriter(new File(path), 16, true);
    Color[] colors = {Color.ORANGE, new Color(255, 0, 200), Color.BLUE, Color.GREEN, Color.GREEN};

    for (int t = 0; t < colors.length; ++t) {
      for (int r = 0; r < image.getHeight(); ++r) {
        for (int c = 0; c < image.getWidth(); ++c) {
          int i = (r + t) % colors.length;
          image.setRGB(c, r, colors[i].getRGB());
        }
      }
      
      out.appendFrame(image);
    }
    
    out.close();
    
    Desktop desktop = Desktop.getDesktop();
    desktop.browse(URI.create("file://" + path));
  }
}

PoShell.java

package lecture1106;

import java.awt.Desktop;
import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public class PoShell {
  public static void main(String[] args) throws IOException {
    
    Scanner in = new Scanner(System.in);
    File currentDirectory = new File(System.getProperty("user.home"));
    Desktop desktop = Desktop.getDesktop();
    
    System.out.print("> ");
    while (in.hasNext()) {
      String command = in.next();
      if (command.equals("where")) {
        System.out.println(currentDirectory.getAbsolutePath());
      } else if (command.equals("up")) {
        currentDirectory = currentDirectory.getParentFile();
      } else if (command.equals("into")) {
        currentDirectory = new File(currentDirectory, in.next());
      } else if (command.equals("open")) {
        File child = new File(currentDirectory, in.next());
        desktop.open(child);
      } else if (command.equals("ls")) {
        String[] children = currentDirectory.list();
//        for (int i = 0; i < children.length; ++i) {
//          System.out.println(children[i]);
//        }
        
        for (String child : children) {
          System.out.println(child);
        }
      } else {
        System.out.println("Wakarimasen. No comprendo.");
      }
      
      System.out.print("> ");
    }
  }
}

Rainbow.java

package lecture1106;

import java.awt.Color;
import java.awt.Desktop;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.net.URI;

public class Rainbow {
  public static void main(String[] args) throws IOException {
    BufferedImage image = new BufferedImage(600, 300, BufferedImage.TYPE_INT_RGB);

//    Color[] colors = new Color[3];
//    colors[0] = Color.RED;
//    colors[1] = Color.ORANGE;
//    colors[2] = Color.YELLOW;
    
    String path = "/Users/johnch/Desktop/rainbow.gif";
    GifSequenceWriter out = new GifSequenceWriter(new File(path), 1000, true);
    
    Color[] colors = {Color.RED, Color.ORANGE, Color.YELLOW, Color.GREEN, new Color(127, 255, 0), new Color(128, 0, 128)};

    for (int t = 0; t < colors.length; ++t) {
      for (int r = 0; r < image.getHeight(); ++r) {
        for (int c = 0; c < image.getWidth(); ++c) {
          image.setRGB(c, r, colors[((r / 24) + t) % colors.length].getRGB());
        }
      }
      out.appendFrame(image);
    }
    
    out.close();
    
    Desktop desktop = Desktop.getDesktop();
    desktop.browse(URI.create("file://" + path));
  }
}