CS 245 Lecture 8 – Brute Force and Spellchecking
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
on writing recursively
An untethered rope.
Climb and it holds. Uncooked food.
Eat and it delights.
An untethered rope.
Climb and it holds. Uncooked food.
Eat and it delights.