BoggleSolver.java

/*
Correctness:  13/13 tests passed
Memory:       3/3 tests passed
Timing:       8/9 tests passed
Aggregate score: 92.78%
[ Compilation: 5%, API: 5%, Style: 0%, Correctness: 60%, Timing: 10%, Memory: 20% ]

////////////////////////////////////////////////////////////////////////////////////

Test 2: timing getAllValidWords() for 5.0 seconds using dictionary-yawl.txt
        (must be <= 2x reference solution)
    - reference solution calls per second: 9288.02
    - student   solution calls per second: 4513.83
    - reference / student ratio:           2.06

=> passed    student <= 10000x reference
=> passed    student <=    25x reference
=> passed    student <=    10x reference
=> passed    student <=     5x reference
=> FAILED    student <=     2x reference

Total: 8/9 tests passed!
*/


import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import java.util.HashSet;

public class BoggleSolver {

    private final TrieSET26 trie;
    private int rows;
    private int cols;
    private boolean[] marked;
    private StringBuilder prefix;
    private HashSet<String> validWords;
    private Bag<Integer>[] adj;

    // Initializes the data structure using the given array of strings as the dictionary.
    // (You can assume each word in the dictionary contains only the uppercase letters A through Z.)
    public BoggleSolver(String[] dictionary) {
        trie = new TrieSET26();
        for (String w : dictionary) {
            trie.add(w); // Build 26-way trie
        }
    }

    // Returns the set of all valid words in the given Boggle board, as an Iterable.
    public Iterable<String> getAllValidWords(BoggleBoard board) {
        cols = board.cols();
        rows = board.rows();
        int n = cols * rows;
        validWords = new HashSet<>(); // all the valid words that can be created from letter at [c][r]
        marked = new boolean[cols * rows]; // if a letter has already been used in this prefix-word only
        prefix = new StringBuilder(); // the prefix used to search words starting with letter located at [i][j]

        // Precompute the set of cubes adjacent to each cube
        adj = new Bag[n];
        for (int i = 0; i < cols; i++) { // build the adj array for every positions in board
            for (int j = 0; j < rows; j++) {
                int k = cols * j + i; // kth position of letter[i][j] in 2D grid starting at 0
                adj[k] = adj(k);
            }
        }
        for (int cube = 0; cube < n; cube++) { // in board. One new prefix for each starting board letter.
            char letter = getLetter(board, cube);
            append(letter);
            DFS(board, cube);
        }
        return validWords;
    }

    // Returns the score of the given word if it is in the dictionary, zero otherwise.
    // (You can assume the word contains only the uppercase letters A through Z.)
    public int scoreOf(String word) {
        return trie.contains(word) ? points(word) : 0;
    }

///////////////////// UTILITIES  /////////////////////

    private void DFS(BoggleBoard board, int k) {
        marked[k] = true;
        for (int x : adj[k]) { // for all the adjacent letters
            if (!marked[x]) {
                char letter = getLetter(board, x);
                append(letter);
                String word = prefix.toString();

                if (trie.hasKeysWithPrefix(word)) { // at least one key with prefix word exists in dictionary
                    if (word.length() >= 3) {
                        if (trie.contains(word))
                            validWords.add(word); // found a matched word !! duplicates are skipped as validWords is a HashSet!
                    }
                    DFS(board, x); // keep on searching for longer prefixes
                } else {
                /* backtracking optimization: when the current path corresponds to a string that is not
                a prefix of any word in the dictionary, there is no need to expand the path further. */
                    backTrack(x, letter);
                }
            }
        }
        char letter = getLetter(board, k);
        backTrack(k, letter);
    }

    private Bag<Integer> adj(int c) {
        Bag<Integer> res = new Bag<>();
        int i = c % cols;
        int j = c / cols;
        int n, s, e, w, se, sw, ne, nw;

        // north?
        if (j > 0) {
            n = c - cols;
            res.add(n);
        }
        // south?
        if (j < rows - 1) {
            s = c + cols;
            res.add(s);
        }
        // east?
        if (i < cols - 1) {
            e = c + 1;
            res.add(e);
        }
        // west?
        if (i > 0) {
            w = c - 1;
            res.add(w);
        }
        // southeast?
        if (j < rows - 1 && i < cols - 1) {
            se = c + cols + 1;
            res.add(se);
        }
        // southwest?
        if (j < rows - 1 && i > 0) {
            sw = c + cols - 1;
            res.add(sw);
        }
        // northeast?
        if (j > 0 && i < cols - 1) {
            ne = c - cols + 1;
            res.add(ne);
        }
        // northwest?
        if (j > 0 && i > 0) {
            nw = c - cols - 1;
            res.add(nw);
        }
        return res;
    }

    private int points(String w) {
        int e = w.length();
        if (e < 3) return 0;
        if (e == 3 || e == 4) return 1;
        if (e == 5) return 2;
        if (e == 6) return 3;
        if (e == 7) return 5;
        else return 11;
    }

    private void append(char letter) {
        prefix.append((letter == 'Q') ? "QU" : letter); // construct one letter longer new prefix-word with QU counting as one
    }

    private void backTrack(int x, char letter) { // from position x remove letter from prefix
        marked[x] = false; // reset for further search via different path
        prefix.deleteCharAt(prefix.length() - 1); // remove the last char in prefix
        if (letter == 'Q') { // we remove a further char corresponding to the added extra 'U'
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    private char getLetter(BoggleBoard board, int k) {
        if (rows == 1) return board.getLetter(0, k);
        if (cols == 1) return board.getLetter(k, 0);
           else return board.getLetter(k / cols, k % cols);
    }

    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);
        }
        StdOut.println("Score = " + score);
    }
}