Algorithms-II : 4-Boggle: implementationalgs-II

1 files changed, 129 insertions, 13 deletions

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);
     }
 }