Princeton Algorithm Assignment Boggle
普林斯顿大学算法课 Boggle
实现一个 Boggle 游戏,由自己决定采用什么数据结构和搜索方法。
基本就是字典树(Trie)的实际应用。
提供了 BogleBoard 类和 BoggleGame 类,可以很方便把自己写的 Solver 给整合进去,直接编译成可以玩的游戏,顺便也验证一下结果是否正确。
Trie 的正确实现不难,DFS 也很无脑,基本可以轻松拿到 80 到 90 分,主要是性能上的优化,想要拿满分(甚至 bonus),需要考虑:
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);
}
}
}
}
// 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];
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;
}
if (c == 'Q') {
i++; // Skip "Qu"
if (i == word.length() || word.charAt(i) != 'U') {
// Ignore "Q" and "Qx"
return false;
}
}
i++;
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);
}
}
参考解决方案的每秒查询数大概在 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.
以下代码获得 Coursera 评分 100 分:访问 GitLab仓库、GitHub仓库 和/或 博客 查看完整代码。