From e3a192fd3a5b535e246deba540164e69cfdfa689 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Thu, 2 Jun 2016 11:43:53 -0700 Subject: [PATCH] Initial boggle code checkin. --- org/guru/boggle/Board.java | 19 ++++ org/guru/boggle/BoardPosition.java | 29 ++++++ org/guru/boggle/Boggle.java | 52 +++++++++++ org/guru/boggle/DictionaryTrie.java | 134 ++++++++++++++++++++++++++++ org/guru/boggle/SimpleBoard.java | 120 +++++++++++++++++++++++++ 5 files changed, 354 insertions(+) create mode 100644 org/guru/boggle/Board.java create mode 100644 org/guru/boggle/BoardPosition.java create mode 100644 org/guru/boggle/Boggle.java create mode 100644 org/guru/boggle/DictionaryTrie.java create mode 100644 org/guru/boggle/SimpleBoard.java diff --git a/org/guru/boggle/Board.java b/org/guru/boggle/Board.java new file mode 100644 index 0000000..f310a5e --- /dev/null +++ b/org/guru/boggle/Board.java @@ -0,0 +1,19 @@ +package org.guru.boggle; + +import java.util.List; + +public interface Board { + void reset(); + + char letterAt(BoardPosition p); + + void markUsed(BoardPosition p); + + void clearUsed(BoardPosition p); + + boolean isUsed(BoardPosition p); + + List adjacentNeighborPositions(BoardPosition p); + + List adjacentUnusedNeighborPosition(BoardPosition p); +} diff --git a/org/guru/boggle/BoardPosition.java b/org/guru/boggle/BoardPosition.java new file mode 100644 index 0000000..5ef96a7 --- /dev/null +++ b/org/guru/boggle/BoardPosition.java @@ -0,0 +1,29 @@ +package org.guru.boggle; + +import com.google.common.base.Objects; + +public class BoardPosition { + private final int x; + private final int y; + + public BoardPosition(int x, int y) { + this.x = x; + this.y = y; + } + + public int x() { + return x; + } + + public int y() { + return y; + } + + @Override + public String toString() { + return Objects.toStringHelper(this) + .add("x", x) + .add("y", y) + .toString(); + } +} \ No newline at end of file diff --git a/org/guru/boggle/Boggle.java b/org/guru/boggle/Boggle.java new file mode 100644 index 0000000..b1dd13c --- /dev/null +++ b/org/guru/boggle/Boggle.java @@ -0,0 +1,52 @@ +package org.guru.boggle; + +import java.io.IOException; +import java.util.Set; + +public class Boggle implements Runnable { + + private final SimpleBoard board; + private final DictionaryTrie dict; + + public Boggle() throws IOException { + this.dict = new DictionaryTrie("/Users/scott/words"); + this.board = new SimpleBoard(); + } + + @Override + public void run() { + if (dict.containsWord("BUDDG")) { + System.out.println("wtf?"); + } + + for (BoardPosition p : board.allPositions()) { + System.out.println("Starting position " + p); + recurse(p, ""); + } + } + + public void recurse(BoardPosition p, String soFar) { + char letter = board.letterAt(p); + board.markUsed(p); + soFar = soFar + letter; + if (dict.containsWord(soFar)) { + System.out.println(soFar); + } + Set possibleSuccessors = dict.possibleSuccessorLetters(soFar); + for (BoardPosition q : board.adjacentUnusedNeighborPosition(p)) { + char potentialSuccessor = board.letterAt(q); + if (possibleSuccessors.contains(potentialSuccessor)) { + recurse(q, soFar); + } + } + board.clearUsed(p); + } + + public static void main(String args[]) { + try { + new Boggle().run(); + } catch (IOException e) { + e.printStackTrace(); + } + } +} diff --git a/org/guru/boggle/DictionaryTrie.java b/org/guru/boggle/DictionaryTrie.java new file mode 100644 index 0000000..421d670 --- /dev/null +++ b/org/guru/boggle/DictionaryTrie.java @@ -0,0 +1,134 @@ +package org.guru.boggle; + +import java.io.BufferedReader; +import java.io.FileReader; +import java.io.IOException; +import java.util.Set; + +import com.google.common.base.Objects; +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Sets; + +public class DictionaryTrie { + + private static class Node { + private boolean wordEndsHere; + private final Node[] children = new Node[26]; + + public Node(boolean wordEndsHere) { + this.wordEndsHere = wordEndsHere; + } + + private int letterToIndex(char letter) { + Preconditions.checkArgument(letter >= 'A' && letter <= 'Z', "Expect uppercase letter"); + return letter - 'A'; + } + + // nullable + public Node childForLetter(char letter) { + return children[letterToIndex(letter)]; + } + + public void addChildAtLetter(Node child, char letter) { + Preconditions.checkState(!hasChildAtLetter(letter), "I already have a child"); + children[letterToIndex(letter)] = child; + } + + public boolean hasChildAtLetter(char letter) { + return children[letterToIndex(letter)] != null; + } + + public Set childrenList() { + Set result = Sets.newHashSetWithExpectedSize(8); + for (int i = 0; i < 26; ++i) { + if (children[i] != null) { + result.add((char) (i + 'A')); + } + } + return result; + } + + public boolean doesWordEndHere() { + return wordEndsHere; + } + + public void markWordEndsHere() { + wordEndsHere = true; + } + + @Override + public String toString() { + return Objects.toStringHelper(this) + .add("wordEndsHere", wordEndsHere) + .add("children", children) + .toString(); + } + } + + private final Node root = new Node(false); + + public DictionaryTrie(String inputFilePath) throws IOException { + FileReader fr = new FileReader(inputFilePath); + BufferedReader br = new BufferedReader(fr); + try { + String line; + while ((line = br.readLine()) != null) { + line = line.toUpperCase(); + Node node = root; + for (int i = 0; i < line.length(); ++i) { + char letter = line.charAt(i); + if (!Character.isUpperCase(letter)) { + break; + } + boolean lastCharacter = (i == line.length() - 1); + if (node.hasChildAtLetter(letter)) { + node = node.childForLetter(letter); + if (lastCharacter) { + node.markWordEndsHere(); + } + } else { + Node child = new Node(lastCharacter); + node.addChildAtLetter(child, letter); + } + } + System.out.printf("Added %s\n", line); + } + } catch (IOException e) { + System.err.println("Error: " + e); + } finally { + br.close(); + fr.close(); + } + } + + // nullable + private Node traverse(String word) { + Node node = root; + for (int i = 0; i < word.length(); ++i) { + char letter = word.charAt(i); + if (!Character.isUpperCase(letter)) { + return null; + } + if (node.hasChildAtLetter(letter)) { + node = node.childForLetter(letter); + } else { + return null; + } + } + return node; + } + + public boolean containsWord(String word) { + Node node = traverse(word); + return node != null && node.doesWordEndHere(); + } + + public Set possibleSuccessorLetters(String prefix) { + Node node = traverse(prefix); + if (node == null) { + return ImmutableSet.of(); + } + return node.childrenList(); + } +} diff --git a/org/guru/boggle/SimpleBoard.java b/org/guru/boggle/SimpleBoard.java new file mode 100644 index 0000000..c291a63 --- /dev/null +++ b/org/guru/boggle/SimpleBoard.java @@ -0,0 +1,120 @@ +package org.guru.boggle; + +import java.util.List; +import java.util.Random; + +import com.google.common.collect.Lists; + +public class SimpleBoard implements Board { + + private static final int DIM = 5; + private final char[][] state = new char[DIM][DIM]; + private final boolean[][] used = new boolean[DIM][DIM]; + private final Random rand = new Random(); + + public SimpleBoard() { + reset(); + dump(); + } + + @Override + public void reset() { + for (int i = 0; i < DIM; ++i) { + for (int j = 0; j < DIM; ++j) { + state[i][j] = randomLetter(); + used[i][j] = false; + } + } + } + + public void dump() { + for (int i = 0; i < DIM; ++i) { + for (int j = 0; j < DIM; ++j) { + System.out.printf("%c ", state[i][j]); + } + System.out.printf("\n"); + } + } + + public List allPositions() { + List result = Lists.newArrayList(); + for (int i = 0; i < DIM; ++i) { + for (int j = 0; j < DIM; ++j) { + result.add(new BoardPosition(i, j)); + } + } + return result; + } + + private char randomLetter() { + return Character.valueOf((char) (rand.nextInt(26) + 65)); + } + + private void checkDimension(int i) { + if (i < 0 || i >= DIM) { + throw new IllegalArgumentException("Bad board dimension: " + i); + } + } + + private void checkOnBoard(BoardPosition p) { + checkDimension(p.x()); + checkDimension(p.y()); + } + + @Override + public char letterAt(BoardPosition p) { + checkOnBoard(p); + return state[p.x()][p.y()]; + } + + @Override + public void markUsed(BoardPosition p) { + checkOnBoard(p); + used[p.x()][p.y()] = true; + } + + @Override + public void clearUsed(BoardPosition p) { + checkOnBoard(p); + used[p.x()][p.y()] = false; + } + + @Override + public boolean isUsed(BoardPosition p) { + checkOnBoard(p); + return used[p.x()][p.y()]; + } + + @Override + public List adjacentNeighborPositions(BoardPosition p) { + List result = Lists.newArrayList(); + int x = p.x(); + int y = p.y(); + for (int i = x - 1; i <= x + 1; ++i) { + for (int j = y - 1; j <= y + 1; ++j) { + if (i == x && y == j) continue; + if (i < 0 || j < 0) continue; + if (i >= DIM || j >= DIM) continue; + result.add(new BoardPosition(i, j)); + } + } + return result; + } + + @Override + public List adjacentUnusedNeighborPosition(BoardPosition p) { + List result = Lists.newArrayList(); + int x = p.x(); + int y = p.y(); + for (int i = x - 1; i <= x + 1; ++i) { + for (int j = y - 1; j <= y + 1; ++j) { + if (i == x && y == j) continue; + if (i < 0 || j < 0) continue; + if (i >= DIM || j >= DIM) continue; + if (used[i][j] == true) continue; + result.add(new BoardPosition(i, j)); + } + } + return result; + } +} -- 2.47.1