path: root/Algorithms/Part-II/4-Boggle/BoggleSolverDicho.java

/* 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"));
        }
    }
}