teaching machines

CS 245 Lecture 8 – Brute Force and Spellchecking

September 26, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• a little Timer class
• brute force password cracking with recursion
• spellchecking with recursion
• linear search
• binary search

TODO

• Work on homework 1, part 1.

Code

Sketcher.java

package lecture0926;

import java.awt.BorderLayout;
import javax.swing.JFrame;

public class Sketcher {
  public static void main(String[] args) {
    JFrame frame = new JFrame("Sketcher");
    
    frame.add(new SketcherWidget(), BorderLayout.CENTER);
    
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(1200, 700);
    frame.setVisible(true);
  }
}

SketcherWidget.java

package lecture0926;

import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JPanel;

public class SketcherWidget extends JPanel {
  @Override
  public void paintComponent(Graphics g) {
    drawCircles(g, 500);
  }

  private void drawCircles(Graphics g,
                           int radius) {

    // Base case.
    if (radius <= 0) {
      // Nothing to do here. Get rid of this branch.
    }

    // General case.
    else {
      // draw one circle
      g.setColor(Color.RED);
      g.fillOval(0, 0, radius, radius);
      g.setColor(Color.WHITE);
      g.fillOval(0, 0, radius - 5, radius - 5);

      // draw the rest
      drawCircles(g, radius - 10);
    }
  }
}

PoorMansTimer.java

package lecture0926;

import java.util.Scanner;

public class PoorMansTimer {
  private long startTime;
  private long endTime;
  
  public void start() {
    startTime = System.currentTimeMillis();
  }
  
  public void stop() {
    endTime = System.currentTimeMillis();
  }
  
  public double getElapsedSeconds() {
    return (endTime - startTime) / 1000.0;
  }
  
  public static void main(String[] args) {
    PoorMansTimer timer = new PoorMansTimer();
    timer.start();
    Scanner in = new Scanner(System.in);
    in.nextLine();
    timer.stop();
    System.out.println(timer.getElapsedSeconds());
  }
}

BruteForcer.java

package lecture0926;

public class BruteForcer {
  private static final String SECRET = "zzzzzz";
  
  public static void main(String[] args) {
    PoorMansTimer timer = new PoorMansTimer();
    timer.start();
    brutify("", 6);
    timer.stop();
    System.out.println(timer.getElapsedSeconds());
  }

  public static void brutify(String soFar,
                             int targetLength) {

    // Base case.
    if (targetLength == 0) {
//      System.out.println(soFar);
      if (SECRET.equals(soFar)) {
        System.out.println("Cracked!");
      }
    }

    // General case.
    else {
      // I have a partially generated password in soFar.
      // I would like to tack on all possible next letters.
      for (char letter = 'a'; letter <= 'z'; ++letter) {
        brutify(soFar + letter, targetLength - 1);
      }
    }
  }
}

Spellchecker.java

package lecture0926;

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

public class Spellchecker {
  private ArrayList<String> words;

  public Spellchecker() {
    words = new ArrayList<String>();

    try {
      Scanner in = new Scanner(new File("/usr/share/dict/words"));
      while (in.hasNextLine()) {
        String word = in.nextLine();
        words.add(word);
      }
    } catch (FileNotFoundException e) {
    }
  }
  
  public boolean isLegitimate(String wordInQuestion) {
    return indexOf(wordInQuestion) != -1;
  }
  
  private int indexOf(String wordInQuestion) {
    for (int i = 0; i < words.size(); ++i) {
      if (words.get(i).equals(wordInQuestion)) {
        return i;
      }
    }
    
    return -1;
  }
  
  private int smarterIndexOf(String wordInQuestion, int lo, int hi) {
    
    int middle = (lo + hi) / 2;
    int order = wordInQuestion.compareTo(words.get(middle));
    
    if (order == 0) {
      return middle;
    } else if (order < 0) {
    }
    
  }
  
  public static void main(String[] args) {
    Spellchecker checker = new Spellchecker();
    System.out.println(checker.isLegitimate("foobag"));
  }
}

Haiku