Princeton Algorithm Assignment Boggle

普林斯顿大学算法课 Boggle

实现一个 Boggle 游戏，由自己决定采用什么数据结构和搜索方法。

基本就是字典树（Trie）的实际应用。

提供了 BogleBoard 类和 BoggleGame 类，可以很方便把自己写的 Solver 给整合进去，直接编译成可以玩的游戏，顺便也验证一下结果是否正确。

Trie 的正确实现不难，DFS 也很无脑，基本可以轻松拿到 80 到 90 分，主要是性能上的优化，想要拿满分（甚至 bonus），需要考虑：

1. 回溯优化：当某一个结点的没有孩子的时候，不需要进行 DFS；

if (node.hasChild()) {
    for (int x = -1; x <= 1; x++) {
        for (int y = -1; y <= 1; y++) {
            int newRow = row + x;
            int newCol = col + y;
            if (isValid(board, newRow, newCol) && !visited[newRow][newCol]) {
                dfs(board, newRow, newCol, visited, node);
            }
        }
    }
}

2. 单词只包含 A 到 Z，所以直接使用 26 个结点的 Trie，比 TNT 快很多（虽然占用了更多的内存）；

// Recall that the alphabet consists of only the 26 letters A through Z
// Use trie 26, more space but faster than TNT
links = new TrieNode[26];

3. DFS 中的前缀查询，通常会得到一致的结果, 只是每次长了一个字符，所以不需要每一次都进行前缀查询，保存 TrieNode 的状态，在每一次 DFS 中更新；

public TrieNode prefixNode(char c, TrieNode cache) {
    if (cache == null) {
        cache = root;
    }
    if (cache.contains(c)) {
        cache = cache.get(c);
    } else {
        return null;
    }
    return cache;
}

4. 由于 Q 之后只会包含 u，不存在 Qx 的情况，所以没必要在 Trie 中存储 Qu，只需要 Q 就可以了，处理时特判 Q，跳过 u；

if (c == 'Q') {
    i++; // Skip "Qu"
    if (i == word.length() || word.charAt(i) != 'U') {
        // Ignore "Q" and "Qx"
        return false;
    }
}
i++;

5. 不要使用 Set，在 TrieNode 中增加一个标记，表示这个单词是否被添加过，例如当访问过了之后修改这个 TrieNode 的 added 为 true，但是注意，我们会对同一个字典（Trie）执行多次 getAllValidWords，所以仅用 true/false 不足以表示这样的情况，我们在 TrieNode 中增加一个 uid 字段，每次执行 getAllValidWords 时增加 uid，判断在当前 uid 下，这个单词是不是被加入过；

public Iterable<String> getAllValidWords(BoggleBoard board) {
    answers = new ArrayList<>();
    uid++;
    // DFS
    return new ArrayList<>(answers);
}

if (node.isEnd() && node.getUid() != uid) {
  String word = node.getWord();
  if (word.length() > 2) {
      answers.add(word);
      node.setUid(uid);
  }
}

6. 不要在 DFS 中用类似 StringBuilder 的东西，在 Trie 中构造字符串，并存在 TrieNode 中，因为 Trie 只会被构建一次，这样之后 DFS 直接根据 Node 中的字符串输出单词，就会快很多。

参考解决方案的每秒查询数大概在 8000 次左右，要求 reference/student ratio 小于等于 2，即实现方案的每秒查询数大于 4000 就可以得到满分，上面这些方案的任意组合足以达到 ratio <= 1，即每秒查询 8000 次以上。

如果还想要获得 Bonus（ratio <= 0.5，即每秒查询 16000 次以上），需要额外处理：

Precompute the Boggle graph, i.e., the set of cubes adjacent to each cube. But don’t necessarily use a heavyweight Graph object: To caculate the key for every point, which means key = y * width + x, then for every point, save current key’s neighbors key in int[][] graph , therefore we need a letter array to map the key to the letter in board.

public class Trie {

    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        int i = 0;
        while (i < word.length()) {
            char c = word.charAt(i);
            if (!node.contains(c)) {
                node.put(c);
            }
            node = node.get(c);
            if (c == 'Q') {
                i++; // Skip "Qu"
                if (i == word.length() || word.charAt(i) != 'U') {
                    // Ignore "Q" and "Qx"
                    return;
                }
            }
            i++;
        }
        node.setEnd(word);
    }

    public boolean search(String word) {
        TrieNode node = root;
        int i = 0;
        while (i < word.length()) {
            char c = word.charAt(i);
            if (node.contains(c)) {
                node = node.get(c);
            } else {
                return false;
            }
            if (c == 'Q') {
                i++; // Skip "Qu"
                if (i == word.length() || word.charAt(i) != 'U') {
                    // Ignore "Q" and "Qx"
                    return false;
                }
            }
            i++;
        }
        return node.isEnd();
    }

    public TrieNode prefixNode(char c, TrieNode cache) {
        if (cache == null) {
            cache = root;
        }
        if (cache.contains(c)) {
            cache = cache.get(c);
        } else {
            return null;
        }
        return cache;
    }

}

public class TrieNode {
    private final TrieNode[] links;
    private boolean hasChild;
    // Unique ID here indicates the different getAllValidWords() call, to see if it should be added
    private int uid;
    // Build string here, because the trie will be built only once
    // Do not build strings in the DFS
    private String word;

    public TrieNode() {
        // Recall that the alphabet consists of only the 26 letters A through Z
        // Use trie 26, more space but faster than TNT
        links = new TrieNode[26];
        hasChild = false;
        uid = 0;
        word = null;
    }

    public boolean isEnd() {
        return word != null;
    }

    public void setEnd(String w) {
        this.word = w;
    }

    public TrieNode get(char c) {
        return links[c - 'A'];
    }

    public void put(char c) {
        links[c - 'A'] = new TrieNode();
        hasChild = true;
    }

    public boolean contains(char c) {
        return links[c - 'A'] != null;
    }

    public boolean hasChild() {
        return hasChild;
    }

    public void setUid(int uid) {
        this.uid = uid;
    }

    public int getUid() {
        return uid;
    }

    public String getWord() {
        return word;
    }
}

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;
import java.util.ArrayList;

public class BoggleSolver {

    private final Trie trie = new Trie();
    private ArrayList<String> answers = null;
    private int uid = 0;

    // 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) {
        if (dictionary == null) {
            throw new IllegalArgumentException();
        }
        for (String word : dictionary) {
            trie.insert(word);
        }
    }

    // Returns the set of all valid words in the given Boggle board, as an Iterable.
    public Iterable<String> getAllValidWords(BoggleBoard board) {
        if (board == null) {
            throw new IllegalArgumentException();
        }
        answers = new ArrayList<>();
        uid++;
        boolean[][] visited = new boolean[board.rows()][board.cols()];
        for (int row = 0; row < board.rows(); row++) {
            for (int col = 0; col < board.cols(); col++) {
                clearVisited(visited);
                dfs(board, row, col, visited, null);
            }
        }
        return new ArrayList<>(answers);
    }

    private void clearVisited(boolean[][] visited) {
        for (boolean[] b : visited) {
            Arrays.fill(b, false);
        }
    }

    private boolean isValid(BoggleBoard board, int row, int col) {
        return row >= 0 && row < board.rows() && col >= 0 && col < board.cols();
    }

    private void dfs(BoggleBoard board, int row, int col, boolean[][] visited, TrieNode cache) {
        char c = board.getLetter(row, col);
        visited[row][col] = true;
        TrieNode node = trie.prefixNode(c, cache);
        // Add a sign in TrieNode, to know if this word has already been added
        // Instead of using a Set
        if (node != null) {
            if (node.isEnd() && node.getUid() != uid) {
                String word = node.getWord();
                if (word.length() > 2) {
                    answers.add(word);
                    node.setUid(uid);
                }
            }
            // Make sure that you have implemented the critical backtracking optimization
            // Means when next trie node is null, no need to dfs more
            if (node.hasChild()) {
                for (int x = -1; x <= 1; x++) {
                    if ((x == -1 && row == 0) || (x == 1 && row == board.rows() - 1)) {
                        continue;
                    }
                    for (int y = -1; y <= 1; y++) {
                        if ((y == -1 && col == 0) || (y == 1 && col == board.cols())) {
                            continue;
                        }
                        if (x == 0 && y == 0) {
                            continue;
                        }
                        int newRow = row + x;
                        int newCol = col + y;
                        if (isValid(board, newRow, newCol) && !visited[newRow][newCol]) {
                            dfs(board, newRow, newCol, visited, node);
                        }
                    }
                }
            }
        }
        visited[row][col] = false;
    }

    // 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) {
        if (trie.search(word)) {
            int length = word.length();
            if (length < 3) {
                return 0;
            } else if (length <= 4) {
                return 1;
            } else if (length == 5) {
                return 2;
            } else if (length == 6) {
                return 3;
            } else if (length == 7) {
                return 5;
            } else {
                return 11;
            }
        } else {
            return 0;
        }
    }

    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;
        int count = 0;
        for (String word : solver.getAllValidWords(board)) {
            StdOut.println(word);
            score += solver.scoreOf(word);
            count++;
        }
        StdOut.println("Score = " + score);
        StdOut.println("Count = " + count);
    }

}