summaryrefslogtreecommitdiffstats
path: root/Algorithms
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms')
-rw-r--r--Algorithms/Part-II/4-Boggle/BoggleGame.java10
-rw-r--r--Algorithms/Part-II/4-Boggle/BoggleHybridTST.java177
-rw-r--r--Algorithms/Part-II/4-Boggle/BoggleSolver.java142
-rw-r--r--Algorithms/Part-II/4-Boggle/BoggleSolverDicho.java305
-rw-r--r--Algorithms/Part-II/4-Boggle/Makefile28
-rw-r--r--Algorithms/Part-II/4-Boggle/outbin0 -> 663 bytes
-rw-r--r--Algorithms/Part-II/4-Boggle/refbin0 -> 663 bytes
7 files changed, 638 insertions, 24 deletions
diff --git a/Algorithms/Part-II/4-Boggle/BoggleGame.java b/Algorithms/Part-II/4-Boggle/BoggleGame.java
index 71d5477..5306774 100644
--- a/Algorithms/Part-II/4-Boggle/BoggleGame.java
+++ b/Algorithms/Part-II/4-Boggle/BoggleGame.java
@@ -383,31 +383,31 @@ public class BoggleGame extends JFrame {
);
// all words in shakespeare
- In in1 = new In(new File("dictionary-shakespeare.txt"));
+ In in1 = new In(new File("./data/dictionary-shakespeare.txt"));
shakespeareDictionary = new SET<String>();
for (String s : in1.readAllStrings())
shakespeareDictionary.add(s);
// all words in shakespeare
- In in2 = new In(new File("dictionary-nursery.txt"));
+ In in2 = new In(new File("./data/dictionary-nursery.txt"));
nurseryDictionary = new SET<String>();
for (String s : in2.readAllStrings())
nurseryDictionary.add(s);
// about 20K common words
- In in3 = new In(new File("dictionary-common.txt"));
+ In in3 = new In(new File("./data/dictionary-common.txt"));
commonDictionary = new SET<String>();
for (String s : in3.readAllStrings())
commonDictionary.add(s);
// all words in Algorithms 4/e
- In in4 = new In(new File("dictionary-algs4.txt"));
+ In in4 = new In(new File("./data/dictionary-algs4.txt"));
algs4Dictionary = new SET<String>();
for (String s : in4.readAllStrings())
algs4Dictionary.add(s);
// dictionary
- In in = new In(new File("dictionary-yawl.txt"));
+ In in = new In(new File("./data/dictionary-yawl.txt"));
String[] dictionary = in.readAllStrings();
// create the Boggle solver with the given dictionary
diff --git a/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java b/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java
new file mode 100644
index 0000000..ee442bb
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/BoggleHybridTST.java
@@ -0,0 +1,177 @@
+
+public class BoggleHybridTST
+{
+ private static final int R = 26;
+ private static final int OFFSET = 'A';
+
+ private static Node emptyNode = null;
+
+ private Node[] roots = new Node[R * R];
+
+ public class Node
+ {
+ private boolean isWord;
+ private char c;
+ private Node left, mid, right;
+
+ public boolean isWord() { return isWord; }
+ public String toString() { return "'"+c+"' "+isWord; }
+ }
+
+ public Node emptyNode() {
+ if (emptyNode == null) {
+ emptyNode = new Node();
+ }
+ return emptyNode;
+ }
+
+ public void put(String word)
+ {
+ int l = word.length();
+ if (l < 3) return;
+ int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
+ roots[idx] = put(roots[idx], word, 2);
+ }
+
+ private Node put(Node n, String word, int d)
+ {
+ char c = word.charAt(d);
+
+ Node x = n;
+ if (n == null) {
+ x = new Node();
+ x.c = c;
+ }
+
+ char ref = x.c;
+ if (c < ref) {
+ x.left = put(x.left, word, d);
+ } else if (c == ref) {
+ if (word.length() == (d + 1)) {
+ x.isWord = true;
+ } else {
+ x.mid = put(x.mid, word, (d + 1));
+ }
+ } else {
+ x.right = put(x.right, word, d);
+ }
+
+ return x;
+ }
+
+ public boolean contains(String word)
+ {
+ return (get(word) != null);
+ }
+
+ private Node get(String word)
+ {
+ if (word.length() < 3) return null;
+ int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
+ return get(roots[idx], word, 2);
+ }
+
+ private Node get(Node n, String word, int d)
+ {
+ if (n == null) return null;
+
+ char c = word.charAt(d);
+ char ref = n.c;
+
+ if (c < ref) {
+ return get(n.left, word, d);
+ } else if (c == ref) {
+ if (word.length() == (d + 1)) {
+ if (n.isWord) return n;
+ else return null;
+ }
+ return get(n.mid, word, (d + 1));
+ } else {
+ return get(n.right, word, d);
+ }
+ }
+
+ private Node get(Node n, char c)
+ {
+ if (n == null) return null;
+
+ char ref = n.c;
+
+ if (c < ref) {
+ return get(n.left, c);
+ } else if (c == ref) {
+ return n;
+ } else {
+ return get(n.right, c);
+ }
+ }
+
+ public Node filter(char c, Node n, StringBuilder s, int l)
+ {
+ if (n == null) return null;
+
+ if (l > 2) {
+ return get(n.mid, c);
+ } else if (l == 2) {
+ int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
+ Node root = roots[idx];
+ if (root == null) return null;
+ return get(root, c);
+ } else {
+ return n;
+ }
+ }
+
+ public Node filter(char c, Node n, String s, int l)
+ {
+ if (n == null) return null;
+
+ if (l > 2) {
+ return get(n.mid, c);
+ } else if (l == 2) {
+ int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
+ Node root = roots[idx];
+ if (root == null) return null;
+ return get(root, c);
+ } else {
+ return n;
+ }
+ }
+
+ public static void check(BoggleHybridTST tst, String word, boolean expected)
+ {
+ String status = "ok";
+ if (tst.contains(word) != expected)
+ status = "ERROR";
+ System.out.println("check "+word+" : "+status);
+ }
+
+ // test client
+ public static void main(String[] args)
+ {
+
+ BoggleHybridTST tst = new BoggleHybridTST();
+
+ In in = new In(args[0]);
+ String[] dictionary = in.readAllStrings();
+
+ for (String word : dictionary)
+ tst.put(word);
+
+ check(tst, "ABC", true);
+ check(tst, "BITE", false);
+ check(tst, "BITEX", false);
+ String word = "QUESTIONACCIA";
+ check(tst, word, true);
+
+ word += "X";
+ StringBuilder s = new StringBuilder();
+ Node n = tst.emptyNode();
+ for (int i = 0; i < word.length(); i++) {
+ char c = word.charAt(i);
+ n = tst.filter(c, n, s, i);
+ s.append(c);
+ System.out.println(s+" "+n);
+ }
+ }
+}
diff --git a/Algorithms/Part-II/4-Boggle/BoggleSolver.java b/Algorithms/Part-II/4-Boggle/BoggleSolver.java
index 49633cd..6b7ad07 100644
--- a/Algorithms/Part-II/4-Boggle/BoggleSolver.java
+++ b/Algorithms/Part-II/4-Boggle/BoggleSolver.java
@@ -1,37 +1,153 @@
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+import java.util.Set;
+import java.util.HashSet;
+
public class BoggleSolver
{
+ private int cols, rows;
+ private BoggleHybridTST dict;
+ private BoggleBoard board;
+ private boolean[] visited;
+ private Set<String> result;
+
// assume each word in the dictionary contains only [A-Z]
public BoggleSolver(String[] dictionary)
{
+ dict = new BoggleHybridTST();
+ for (String word : dictionary)
+ dict.put(word);
}
// Returns the set of all valid words in the given Boggle board
- public Iterable<String> getAllValidWords(BoggleBoard board)
+ public Iterable<String> getAllValidWords(BoggleBoard b)
{
- return null;
+ this.board = b;
+ this.cols = board.cols();
+ this.rows = board.rows();
+ this.result = new HashSet<String>();
+
+ for (int r = 0; r < this.rows; r++) {
+ for (int c = 0; c < this.cols; c++) {
+ this.visited = new boolean[this.rows * this.cols];
+ explore(r, c, dict.emptyNode(), new StringBuilder(), 0);
+ }
+ }
+
+ return result;
+ }
+
+ //
+ private void explore(int r, int c, BoggleHybridTST.Node parent,
+ StringBuilder s, int l)
+ {
+ if ((r < 0) || (r >= rows) || (c < 0) || (c >= cols)) return;
+
+ int visitedIdx = (r * this.cols) + c;
+ if (visited[visitedIdx]) return;
+
+ boolean isQu = false;
+ char ch = board.getLetter(r, c);
+
+ BoggleHybridTST.Node next = dict.filter(ch, parent, s, l);
+ if (next == null) return;
+ l += 1;
+ s.append(ch);
+ if (ch == 'Q') {
+ next = dict.filter('U', next, s, l);
+ if (next == null) {
+ s.setLength(l - 1);
+ return;
+ }
+ isQu = true;
+ l += 1;
+ s.append('U');
+ }
+
+ if (next.isWord()) result.add(s.toString());
+
+ visited[visitedIdx] = true;
+
+ explore((r - 1), (c - 1), next, s, l);
+ explore((r - 1), c, next, s, l);
+ explore((r - 1), (c + 1), next, s, l);
+ explore(r, (c - 1), next, s, l);
+ explore(r, (c + 1), next, s, l);
+ explore((r + 1), (c - 1), next, s, l);
+ explore((r + 1), c, next, s, l);
+ explore((r + 1), (c + 1), next, s, l);
+
+ visited[visitedIdx] = false;
+ if (isQu) s.setLength(l - 2);
+ else s.setLength(l - 1);
}
// Returns the score if it is in the dictionary, zero otherwise.
// assume the word contains only [A-Z]
public int scoreOf(String word)
{
- return -1;
+ if (!dict.contains(word)) return 0;
+
+ int l = word.length();
+ if (l < 3) {
+ return 0;
+ } else if (l < 5) {
+ return 1;
+ } else if (l < 6) {
+ return 2;
+ } else if (l < 7) {
+ return 3;
+ } else if (l < 8) {
+ return 5;
+ } else {
+ return 11;
+ }
}
public static void main(String[] args)
{
- In in = new In(args[0]);
- String[] dictionary = in.readAllStrings();
- BoggleSolver solver = new BoggleSolver(dictionary);
- BoggleBoard board = new BoggleBoard(args[1]);
- int score = 0;
- for (String word : solver.getAllValidWords(board))
- {
- StdOut.println(word);
- score += solver.scoreOf(word);
+ if (args[0].equals("timing")) {
+ In in = new In("./data/dictionary-yawl.txt");
+ String[] dictionary = in.readAllStrings();
+
+ Stopwatch w = new Stopwatch();
+ BoggleSolver solver = new BoggleSolver(dictionary);
+ double dt = +w.elapsedTime();
+ System.out.println("construction : "+dt);
+
+ String s = "board-pneumonoultramicroscopicsilicovolcanoconiosis.txt";
+ BoggleBoard []boards = new BoggleBoard[5];
+ boards[0] = new BoggleBoard("./data/board-points4527.txt");
+ boards[1] = new BoggleBoard("./data/board-points13464.txt");
+ boards[2] = new BoggleBoard("./data/board-points4410.txt");
+ boards[3] = new BoggleBoard("./data/board-points1250.txt");
+ boards[4] = new BoggleBoard("./data/board-points1500.txt");
+ // boards[1] = new BoggleBoard("./data/board-rotavator.txt");
+ // boards[2] = new BoggleBoard("./data/board-16q.txt");
+ // boards[4] = new BoggleBoard("./data/" + s);
+
+
+ for (int t = 0; t < 5; t++) {
+ w = new Stopwatch();
+ for (int i = 0; i < 3000; i++) {
+ solver.getAllValidWords(boards[i % 5]);
+ }
+ dt = +w.elapsedTime();
+ System.out.println("search time : "+dt);
+ }
+ } else {
+ In in = new In(args[0]);
+ String[] dictionary = in.readAllStrings();
+ BoggleSolver solver = new BoggleSolver(dictionary);
+ BoggleBoard board = new BoggleBoard(args[1]);
+ int score = 0;
+ for (String word : solver.getAllValidWords(board))
+ {
+ StdOut.println(word);
+ score += solver.scoreOf(word);
+ }
+ StdOut.println("Score = " + score);
+ StdOut.println("Score = " + solver.scoreOf("REQUEST"));
}
- StdOut.println("Score = " + score);
}
}
diff --git a/Algorithms/Part-II/4-Boggle/BoggleSolverDicho.java b/Algorithms/Part-II/4-Boggle/BoggleSolverDicho.java
new file mode 100644
index 0000000..23a645a
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/BoggleSolverDicho.java
@@ -0,0 +1,305 @@
+/* vim: set expandtab tabstop=4 shiftwidth=4 : */
+
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Arrays;
+
+public class BoggleSolverDicho
+{
+
+ private class BoggleDictState
+ {
+ private String s;
+ private int idx, from, to;
+ private boolean isWord;
+
+ public BoggleDictState(int from, int to)
+ {
+ this.s = "";
+ this.idx = -1;
+ this.from = from;
+ this.to = to;
+ this.isWord = false;
+ }
+
+ public BoggleDictState(String s, int idx, int from, int to,
+ boolean isWord)
+ {
+ this.s = s;
+ this.idx = idx;
+ this.from = from;
+ this.to = to;
+ this.isWord = isWord;
+ }
+
+ public String s() { return s; }
+ public int idx() { return idx; }
+ public int from() { return from; }
+ public int to() { return to; }
+ public boolean isWord() { return isWord; }
+ public int n() { return (to - from + 1); }
+
+ public String toString(String[] words)
+ {
+ String ret = s + "(" + idx + ") " + isWord + " "
+ + " [" + from + ";" + to + "](" + n()+") ";
+
+ if (from > 0) ret += words[from - 1];
+ ret += " ["+words[from]+"..."+words[to]+"] ";
+ if (to < (words.length - 1)) ret += words[to + 1];
+
+ return ret;
+ }
+ }
+
+ private class BoggleDict
+ {
+ private String[] words;
+
+ public BoggleDict(String[] words)
+ {
+ this.words = Arrays.copyOf(words, words.length);
+ }
+
+ public int size()
+ {
+ return words.length;
+ }
+
+ public boolean exists(String word) {
+ if (word.isEmpty()) return false;
+
+ BoggleDictState st = new BoggleDictState(0, (size() - 1));
+ for (int i = 0; i < word.length(); i++) {
+ st = filter(word.charAt(i), st);
+ if (st == null) return false;
+ }
+
+ return st.isWord();
+ }
+
+ private BoggleDictState filter(char c, BoggleDictState st)
+ {
+ int idx = st.idx() + 1;
+ int from = st.from();
+ int to = st.to();
+ int n = st.n();
+
+ if (words[from].length() <= idx) {
+ if (n == 1) return null;
+ from++;
+ }
+
+ boolean fromOk = (words[from].charAt(idx) == c);
+ boolean toOk = (words[to].charAt(idx) == c);
+
+ if (!fromOk && (n == 1)) return null;
+
+ // if (n < 200) {
+ // // lower bound
+ // if (!fromOk) {
+ // for (int i = from; i <= to; i++) {
+ // if (words[i].charAt(idx) == c) {
+ // fromOk = true;
+ // from = i;
+ // break;
+ // }
+ // }
+ // if (!fromOk) return null;
+ // }
+ // // upper bound
+ // if (!toOk) {
+ // for (int i = to; i >= from; i--) {
+ // if (words[i].charAt(idx) == c) {
+ // toOk = true;
+ // to = i;
+ // break;
+ // }
+ // }
+ // if (!toOk) return null;
+ // }
+ // }
+ // lower bound
+ if (!fromOk) {
+ int tob = to;
+
+ int mid = (from + tob) / 2;
+ while (mid != from) {
+
+ int diff = words[mid].charAt(idx) - c;
+
+ if (diff > 0) {
+ to = mid;
+ tob = mid;
+ } else if (diff < 0)
+ from = mid;
+ else
+ tob = mid;
+
+ mid = (tob + from) / 2;
+ }
+ if (!(words[from].charAt(idx) == c)) {
+ if (words[tob].charAt(idx) == c) from = tob;
+ else return null;
+ }
+ }
+
+ // upper bound
+ if (!toOk) {
+ int fromb = from;
+ int mid = (fromb + to) / 2;
+ while (mid != fromb) {
+
+ int diff = words[mid].charAt(idx) - c;
+
+ if (diff <= 0)
+ fromb = mid;
+ else
+ to = mid;
+
+ mid = (fromb + to) / 2;
+ }
+ if (!(words[to].charAt(idx) == c)) {
+ if (words[fromb].charAt(idx) == c) to = fromb;
+ else return null;
+ }
+ }
+
+ boolean isWord = ((idx > 1) && ((words[from].length() - 1) == idx));
+
+ return new BoggleDictState((st.s() + c), idx, from, to, isWord);
+ }
+ }
+
+ private int cols, rows;
+ private BoggleDict dict;
+ private BoggleBoard board;
+ private boolean[] visited;
+ private Set<String> result;
+
+ // assume each word in the dictionary contains only [A-Z]
+ public BoggleSolverDicho(String[] dictionary)
+ {
+ dict = new BoggleDict(dictionary);
+ }
+
+ // Returns the set of all valid words in the given Boggle board
+ public Iterable<String> getAllValidWords(BoggleBoard b)
+ {
+ this.board = b;
+ this.cols = board.cols();
+ this.rows = board.rows();
+ this.result = new HashSet<String>();
+
+ BoggleDictState emptyState = new BoggleDictState(0, (dict.size() - 1));
+ for (int r = 0; r < this.rows; r++) {
+ for (int c = 0; c < this.cols; c++) {
+ this.visited = new boolean[this.rows * this.cols];
+ explore(r, c, emptyState);
+ }
+ }
+
+ return result;
+ }
+
+ //
+ private void explore(int r, int c, BoggleDictState current)
+ {
+ if ((r < 0) || (r >= rows) || (c < 0) || (c >= cols)) return;
+
+ int visitedIdx = (r * this.cols) + c;
+ if (visited[visitedIdx]) return;
+
+ char ch = board.getLetter(r, c);
+ BoggleDictState next = dict.filter(ch, current);
+ if (next == null) return;
+ if (ch == 'Q') {
+ next = dict.filter('U', next);
+ if (next == null) return;
+ }
+
+ if (next.isWord()) result.add(next.s());
+
+ visited[visitedIdx] = true;
+
+ explore((r - 1), (c - 1), next);
+ explore((r - 1), c, next);
+ explore((r - 1), (c + 1), next);
+ explore(r, (c - 1), next);
+ explore(r, (c + 1), next);
+ explore((r + 1), (c - 1), next);
+ explore((r + 1), c, next);
+ explore((r + 1), (c + 1), next);
+
+ visited[visitedIdx] = false;
+ }
+
+ // Returns the score if it is in the dictionary, zero otherwise.
+ // assume the word contains only [A-Z]
+ public int scoreOf(String word)
+ {
+ if (!dict.exists(word)) return 0;
+
+ int l = word.length();
+ if (l < 3) {
+ return 0;
+ } else if (l < 5) {
+ return 1;
+ } else if (l < 6) {
+ return 2;
+ } else if (l < 7) {
+ return 3;
+ } else if (l < 8) {
+ return 5;
+ } else {
+ return 11;
+ }
+ }
+
+ public static void main(String[] args)
+ {
+ if (args[0].equals("timing")) {
+ In in = new In("./data/dictionary-yawl.txt");
+ String[] dictionary = in.readAllStrings();
+
+ Stopwatch w = new Stopwatch();
+ BoggleSolver solver = new BoggleSolver(dictionary);
+ double dt = +w.elapsedTime();
+ System.out.println("construction : "+dt);
+
+ String s = "board-pneumonoultramicroscopicsilicovolcanoconiosis.txt";
+ BoggleBoard []boards = new BoggleBoard[5];
+ boards[0] = new BoggleBoard("./data/board-points4527.txt");
+ boards[1] = new BoggleBoard("./data/board-points13464.txt");
+ boards[2] = new BoggleBoard("./data/board-points4410.txt");
+ boards[3] = new BoggleBoard("./data/board-points1250.txt");
+ boards[4] = new BoggleBoard("./data/board-points1500.txt");
+ // boards[1] = new BoggleBoard("./data/board-rotavator.txt");
+ // boards[2] = new BoggleBoard("./data/board-16q.txt");
+ // boards[4] = new BoggleBoard("./data/" + s);
+
+
+ for (int t = 0; t < 5; t++) {
+ w = new Stopwatch();
+ for (int i = 0; i < 3000; i++) {
+ solver.getAllValidWords(boards[i % 5]);
+ }
+ dt = +w.elapsedTime();
+ System.out.println("search time : "+dt);
+ }
+ } else {
+ In in = new In(args[0]);
+ String[] dictionary = in.readAllStrings();
+ BoggleSolverDicho solver = new BoggleSolverDicho(dictionary);
+ BoggleBoard board = new BoggleBoard(args[1]);
+ int score = 0;
+ for (String word : solver.getAllValidWords(board))
+ {
+ StdOut.println(word);
+ score += solver.scoreOf(word);
+ }
+ StdOut.println("Score = " + score);
+ StdOut.println("Score = " + solver.scoreOf("REQUEST"));
+ }
+ }
+}
diff --git a/Algorithms/Part-II/4-Boggle/Makefile b/Algorithms/Part-II/4-Boggle/Makefile
index 0cd39c4..2a0c74b 100644
--- a/Algorithms/Part-II/4-Boggle/Makefile
+++ b/Algorithms/Part-II/4-Boggle/Makefile
@@ -2,7 +2,7 @@
CC = javac
ALGS4 = ../../algs4
BIN = BoggleSolver
-SRCS = BoggleSolver.java
+SRCS = BoggleSolver.java BoggleHybridTST.java
CLASSPATH = -classpath '.:$(ALGS4)/algs4.jar:$(ALGS4)/stdlib.jar'
.SUFFIXES:
@@ -11,7 +11,7 @@ CLASSPATH = -classpath '.:$(ALGS4)/algs4.jar:$(ALGS4)/stdlib.jar'
.java.class:
$(CC) -Xlint $(CLASSPATH) $<
- $(ALGS4)/bin/checkstyle $<
+ -$(ALGS4)/bin/checkstyle $<
BoggleBoard.class: BoggleBoard.java
$(CC) -Xlint $(CLASSPATH) $<
@@ -21,10 +21,26 @@ BoggleGame.class: BoggleGame.java
$(BIN): $(BIN).class
-test: $(BIN) BoggleBoard.class BoggleGame.class
- java $(CLASSPATH) $(BIN) ./data/dictionary-algs4.txt ./data/board-points4.txt
- java $(CLASSPATH) $(BIN) ./data/dictionary-algs4.txt ./data/board-points5.txt
- java $(CLASSPATH) $(BIN) ./data/dictionary-algs4.txt ./data/board-points200.txt
+test: $(BIN) BoggleHybridTST.class
+ -@rm out
+ java $(CLASSPATH) BoggleHybridTST ./data/dictionary-zingarelli2005.txt > out
+ java $(CLASSPATH) $(BIN) ./data/dictionary-algs4.txt ./data/board4x4.txt >> out
+ java $(CLASSPATH) $(BIN) ./data/dictionary-algs4.txt ./data/board-q.txt >> out
+ -@diff out ref && echo "SUCCESS" || echo "ERROR"
+
+timing: $(BIN) BoggleHybridTST.class BoggleSolverDicho.class
+ java $(CLASSPATH) $(BIN) timing
+ java $(CLASSPATH) BoggleSolverDicho timing
+
+game: $(BIN) BoggleBoard.class BoggleGame.class BoggleHybridTST.class
+ java $(CLASSPATH) BoggleGame
+
+dicho: BoggleSolverDicho.class
+ -@rm out
+ java $(CLASSPATH) BoggleHybridTST ./data/dictionary-zingarelli2005.txt > out
+ java $(CLASSPATH) BoggleSolverDicho ./data/dictionary-algs4.txt ./data/board4x4.txt >> out
+ java $(CLASSPATH) BoggleSolverDicho ./data/dictionary-algs4.txt ./data/board-q.txt >> out
+ -@diff out ref && echo "SUCCESS" || echo "ERROR"
zip: $(BIN)
$(ALGS4)/bin/findbugs $(BIN).class
diff --git a/Algorithms/Part-II/4-Boggle/out b/Algorithms/Part-II/4-Boggle/out
new file mode 100644
index 0000000..5aa7f8e
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/out
Binary files differ
diff --git a/Algorithms/Part-II/4-Boggle/ref b/Algorithms/Part-II/4-Boggle/ref
new file mode 100644
index 0000000..5aa7f8e
--- /dev/null
+++ b/Algorithms/Part-II/4-Boggle/ref
Binary files differ
generated by cgit v1.1-2-g2b99 at 2024-11-21 21:56:48 +0100