» CS 1: Lecture 22 – Loops, Part 4

CS 1: Lecture 22 – Loops, Part 4

October 30, 2017 by Chris Johnson. Filed under cs1, cs145, cs148, fall 2017, lectures.

Dear students,

This weekend six computer science majors from the department competed at the 2017 ACM Intercollegiate Programming Contest. We competed at Macalester College in St. Paul. One of our teams solved four problems, which was good enough to place 20th in the entire North Central region, which includes Wisconsin, Minnesota, parts of Canada, the Dakotas, Iowa, and Nebraska.

Also, my kids and I are reading Secret Coders, which is a series of graphic novels about kids using code to fight evil. Last night during our reading, one of the kids’ mothers told her that she didn’t think kids should have to fight evil—that the job should be left to adults. My 9-year-old said, “They’re not kids; they’re coders!” I hope you too feel this superpower that you can use to transcend age, class, whatever situation. I also hope you fight evil.

Today I want to spend a little time answering some of the questions that you’ve asked on your quarter sheets.

First, one of you asked how loops are actually implemented inside the machine. All the instructions of our code will get compiled down to a better of simpler instructions known as machine instructions. These machine instructions can usually be represented with a small and fixed-size set of bits. Each of those instructions can be given an address of where it resides in memory:

0: increment a
1: a = b + 5
2: c = d && e
...

There’s a special piece of memory on the CPU called the program counter, which holds the address of the instruction currently being executed. Normally, the program counter steadily marches up in value in serial execution, processing instruction 0, then 1, then 2, and so on. The looping mechanic is achieved by turning the program counter back to some earlier instruction. Most machine languages support a family of jump instructions for setting the program counter. Let’s see this through the lens of Human Resource Machine.

Conditional statements are achieved with the same mechanic. But instead of jumping back, they jump ahead to the appropriate next instruction. Method calls also involve jumping with the program counter, but there’s a bunch of memory operations that also must occur to support a language’s calling semantics.

Second, many of you asked about when we should use for loops and when we should use while. The book talks of classifying loops as definite (which are coded with for) or indefinite (which are coded with while), which is a problematic dichotomy in my book. Here’s the criteria I follow:

if the iterator needs to live beyond the loop
  choose while
elsif the loop logic can be written compactly
  choose for
else
  choose while

Third, one of you wondered if there’s a way to make two loops execute simultaneously. Yes, there is. We can use something called a thread to add another thread of execution to our programs. Here’s one in Java:

class Countdown extends Thread {
  public void run() {
    for (int i = 10; i >= 0; --i) {
      System.out.println(i);
    }
  }
}

Here we’re making an extension of an existing class named Thread. We redefine its run method to do our custom task, which is just a countdown. To get multiple countdowns running at the same time, we create threads for each and get them started:

Thread a = new Thread();
Thread b = new Thread();
a.start();
b.start();

We won’t go into further details on threads in this class, but they are an essential tool for getting one program to do lots of jobs simultaneously.

Fourth, one of you stated that at one point in your life you had been fascinated by the word abacabadabacaba. You wondered how you might generated this with a loop. It turns out that loops might not be the best choice for this sort of structure. We’re going to repeat ourselves with a different repetition mechanic: recursion.

First, what do you notice about this word? It’s got symmetry: the first half is the same as the right half. It’s also got a structure like a tournament bracket. The d is surrounded by two smaller c brackets to its left and right. The cs are surrounded by two b brackets. The bs are surrounded by two a brackets. Like this:

       d
   c       c
 b   b   b   b
a a a a a a a a

This self-similarity leads to how we might implement this. The topmost level looks this like:

to bracketD
  print bracket with c
  print d
  print bracket with c

The c bracket looks mightily similar:

to bracketC
  print bracket with b
  print c
  print bracket with b

But because each level is a lot like the others, let’s generalize this:

to bracket
  bracket with subroot
  print root
  bracket with subroot

Let’s code this up as a Java method. We’ll send it a list of our roots, from topmost to bottommost. Since getting the subroot’s bracket is a lot like getting the root’s bracket, we actually call ourself in this method. Crazy, huh?

public static String abacaba(String symbols) {
  String s = "";

  s += abacaba(symbols.substring(1));
  s += symbols.charAt(0);
  s += abacaba(symbols.substring(1));

  return s;
}

public static void main(String[] args) {
  System.out.println(abacaba("dcba"));
}

If we run this, we encounter a StringIndexOutOfBoundsException. Where does this happen? On the a sub-brackets. We end up calling abacaba(""), and this call fails. We must guard against this. When we reach the bottom, let’s not try to recurse further:

public static String abacaba(String symbols) {
  String s = "";

  if (!symbols.isEmpty()) {
    s += abacaba(symbols.substring(1));
    s += symbols.charAt(0);
    s += abacaba(symbols.substring(1));
  }

  return s;
}

This works nicely, and we even substitute other root symbols into it.

Fifth, let’s use loops to get some real work done. Let’s make an animated GIF of a bouncing ball.

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

I updated the homework 4 SpecChecker on Sunday. Run Team / Pull… from template today to bring the update into your repository.
CS 145, lab 7 is posted. Feel free to start early—but do not bring work you started on as individual into a group during lab. Either finish early as an individual or work collaboratively from the beginning.

See you next class!

Sincerely,

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

wowzwowuwowzwow
bobebobabobebob
lolzlol4lolzlol

This was generated with this code:

System.out.println(abacaba("uzow"));
System.out.println(abacaba("aeob"));
System.out.println(abacaba("4zol"));

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

Counting.java

package lecture1030;

public class Counting {
  public static void main(String[] args) {
    Counter a = new Counter();
    Counter b = new Counter();
    a.start();
    b.start();
  }
}

class Counter extends Thread {
  public void run() {
    for (int i = 100; i >= 0; --i) {
      System.out.println(i);
    }
  }
}

Abacaba.java

package lecture1030;

public class Abacaba {
  public static void main(String[] args) {
    
    System.out.println(abacaba("jihgfedcba"));
  }
  
  public static String abacaba(String symbols) {
    String s = "";
    
    if (!symbols.isEmpty()) {
      s += abacaba(symbols.substring(1));
      s += symbols.charAt(0);
      s += abacaba(symbols.substring(1));
    }
  
    return s;
  }
}

GifSequenceWriter.java

package lecture1030;
//  GifSequenceWriter.java

//  
//  Created by Elliot Kroo on 2009-04-25.
//
// This work is licensed under the Creative Commons Attribution 3.0 Unported
// License. To view a copy of this license, visit
// http://creativecommons.org/licenses/by/3.0/ or send a letter to Creative
// Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.

import javax.imageio.*;
import javax.imageio.metadata.*;
import javax.imageio.stream.*;
import java.awt.image.*;
import java.io.*;
import java.util.Iterator;

public class GifSequenceWriter {
  protected ImageWriter gifWriter;
  protected ImageWriteParam imageWriteParam;
  protected IIOMetadata imageMetaData;
  protected ImageOutputStream outputStream;

  /**
   * Creates a new GifSequenceWriter
   * 
   * @param outputStream
   *          the ImageOutputStream to be written to
   * @param imageType
   *          one of the imageTypes specified in BufferedImage
   * @param timeBetweenFramesMS
   *          the time between frames in miliseconds
   * @param loopContinuously
   *          wether the gif should loop repeatedly
   * @throws IIOException
   *           if no gif ImageWriters are found
   *
   * @author Elliot Kroo (elliot[at]kroo[dot]net)
   */
  public GifSequenceWriter(File outFile,
                           int timeBetweenFramesMS,
                           boolean loopContinuously) {
    try {
      // my method to create a writer
      gifWriter = getWriter();
      imageWriteParam = gifWriter.getDefaultWriteParam();
      ImageTypeSpecifier imageTypeSpecifier = ImageTypeSpecifier.createFromBufferedImageType(BufferedImage.TYPE_INT_RGB);

      imageMetaData = gifWriter.getDefaultImageMetadata(imageTypeSpecifier, imageWriteParam);

      String metaFormatName = imageMetaData.getNativeMetadataFormatName();

      IIOMetadataNode root = (IIOMetadataNode) imageMetaData.getAsTree(metaFormatName);

      IIOMetadataNode graphicsControlExtensionNode = getNode(root, "GraphicControlExtension");

      graphicsControlExtensionNode.setAttribute("disposalMethod", "none");
      graphicsControlExtensionNode.setAttribute("userInputFlag", "FALSE");
      graphicsControlExtensionNode.setAttribute("transparentColorFlag", "FALSE");
      graphicsControlExtensionNode.setAttribute("delayTime", Integer.toString(timeBetweenFramesMS / 10));
      graphicsControlExtensionNode.setAttribute("transparentColorIndex", "0");

      IIOMetadataNode commentsNode = getNode(root, "CommentExtensions");
      commentsNode.setAttribute("CommentExtension", "Created by MAH");

      IIOMetadataNode appEntensionsNode = getNode(root, "ApplicationExtensions");

      IIOMetadataNode child = new IIOMetadataNode("ApplicationExtension");

      child.setAttribute("applicationID", "NETSCAPE");
      child.setAttribute("authenticationCode", "2.0");

      int loop = loopContinuously ? 0 : 1;

      child.setUserObject(new byte[] { 0x1, (byte) (loop & 0xFF), (byte) ((loop >> 8) & 0xFF)
      });
      appEntensionsNode.appendChild(child);

      imageMetaData.setFromTree(metaFormatName, root);

      outputStream = new FileImageOutputStream(outFile);
      gifWriter.setOutput(outputStream);
      gifWriter.prepareWriteSequence(null);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  public void appendFrame(BufferedImage img) {
    try {
      gifWriter.writeToSequence(new IIOImage(img, null, imageMetaData), imageWriteParam);
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  /**
   * Close this GifSequenceWriter object. This does not close the underlying
   * stream, just finishes off the GIF.
   */
  public void close() {
    try {
      gifWriter.endWriteSequence();
      outputStream.close();
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  /**
   * Returns the first available GIF ImageWriter using
   * ImageIO.getImageWritersBySuffix("gif").
   * 
   * @return a GIF ImageWriter object
   * @throws IIOException
   *           if no GIF image writers are returned
   */
  private static ImageWriter getWriter() throws IIOException {
    try {
      Iterator<ImageWriter> iter = ImageIO.getImageWritersBySuffix("gif");
      if (!iter.hasNext()) {
        throw new IIOException("No GIF Image Writers Exist");
      } else {
        return iter.next();
      }
    } catch (IOException e) {
      throw new RuntimeException(e);
    }
  }

  /**
   * Returns an existing child node, or creates and returns a new child node (if
   * the requested node does not exist).
   * 
   * @param rootNode
   *          the <tt>IIOMetadataNode</tt> to search for the child node.
   * @param nodeName
   *          the name of the child node.
   * 
   * @return the child node, if found or a new node created with the given name.
   */
  private static IIOMetadataNode getNode(IIOMetadataNode rootNode,
                                         String nodeName) {
    int nNodes = rootNode.getLength();
    for (int i = 0; i < nNodes; i++) {
      if (rootNode.item(i).getNodeName().compareToIgnoreCase(nodeName) == 0) {
        return ((IIOMetadataNode) rootNode.item(i));
      }
    }
    IIOMetadataNode node = new IIOMetadataNode(nodeName);
    rootNode.appendChild(node);
    return node;
  }
}

Static.java

package lecture1030;

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;
import java.util.Random;

public class Static {
  public static void main(String[] args) throws IOException {
    GifSequenceWriter out = new GifSequenceWriter(new File("/Users/johnch/Desktop/foo.gif"), 20, true);

    BufferedImage image = new BufferedImage(512, 400, BufferedImage.TYPE_INT_RGB);

    Random g = new Random();

    for (int i = 0; i < 100; ++i) {
      for (int r = 0; r < image.getHeight(); ++r) {
        for (int c = 0; c < image.getWidth(); ++c) {
          image.setRGB(c, r, new Color(g.nextInt(256), g.nextInt(256), g.nextInt(256)).getRGB());
        }
      }

      out.appendFrame(image);
    }
    
    out.close();
    Desktop desktop = Desktop.getDesktop();
    desktop.browse(URI.create("file:///Users/johnch/Desktop/foo.gif"));
  }
}