前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Princeton Algorithms, Boggle

Princeton Algorithms, Boggle

作者头像
凝神长老
发布2020-11-25 17:50:00
5340
发布2020-11-25 17:50:00
举报
文章被收录于专栏:凝神长老和他的朋友们

Princeton Algorithm Assignment Boggle

普林斯顿大学算法课 Boggle

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

基本就是字典树(Trie)的实际应用。

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

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

  1. 回溯优化:当某一个结点的没有孩子的时候,不需要进行 DFS;
代码语言:javascript
复制
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);
            }
        }
    }
}
  1. 单词只包含 A 到 Z,所以直接使用 26 个结点的 Trie,比 TNT 快很多(虽然占用了更多的内存);
代码语言:javascript
复制
// 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];
  1. DFS 中的前缀查询,通常会得到一致的结果, 只是每次长了一个字符,所以不需要每一次都进行前缀查询,保存 TrieNode 的状态,在每一次 DFS 中更新;
代码语言:javascript
复制
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;
}
  1. 由于 Q 之后只会包含 u,不存在 Qx 的情况,所以没必要在 Trie 中存储 Qu,只需要 Q 就可以了,处理时特判 Q,跳过 u;
代码语言:javascript
复制
if (c == 'Q') {
    i++; // Skip "Qu"
    if (i == word.length() || word.charAt(i) != 'U') {
        // Ignore "Q" and "Qx"
        return false;
    }
}
i++;
  1. 不要使用 Set,在 TrieNode 中增加一个标记,表示这个单词是否被添加过,例如当访问过了之后修改这个 TrieNode 的 added 为 true,但是注意,我们会对同一个字典(Trie)执行多次 getAllValidWords,所以仅用 true/false 不足以表示这样的情况,我们在 TrieNode 中增加一个 uid 字段,每次执行 getAllValidWords 时增加 uid,判断在当前 uid 下,这个单词是不是被加入过;
代码语言:javascript
复制
public Iterable<String> getAllValidWords(BoggleBoard board) {
    answers = new ArrayList<>();
    uid++;
    // DFS
    return new ArrayList<>(answers);
}
代码语言:javascript
复制
if (node.isEnd() && node.getUid() != uid) {
  String word = node.getWord();
  if (word.length() > 2) {
      answers.add(word);
      node.setUid(uid);
  }
}
  1. 不要在 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.

以下代码获得 Coursera 评分 100 分:访问 GitLab仓库、GitHub仓库 和/或 博客 查看完整代码。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-11-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 凝神长老和他的朋友们 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档