Algorithms-II : 4-Boggle: implementationalgs-II

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
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