3

对于上下文 Wordle 是一个游戏，您必须根据某些提示在 6 次或更少的猜测中破译 5 个字母的单词。你得到的提示如下：

  1. 如果一个字符被涂成黑色，则目标单词中没有与该字符匹配的字符。
  2. 如果一个字符是橙色的，那么在目标词中就有一个与该字符匹配的字符，但它位于不同的位置。
  3. 如果一个字符是绿色的，则位置和字符是匹配的。

我正在制作一个 wordle 求解器程序，该程序接受一系列单词尝试并将它们从可能的单词列表中消除。

我觉得解决这个问题的最佳算法是一个黑名单，其中一个违反规则的单词被从数组中删除。但如果有更好的选择，我愿意接受建议。


const text =
[
  [
    ["N","black"],["i","black"],["g","black"],
    ["h","black"],["t","green"]
  ],
  [
    ["b","black"],["e","black"],["l","orange"],
    ["o","orange"],["w","black"]
  ]
]

const words = "dozen,brave,apple,climb,outer,pitch,ruler,holds,fixed,costs,calls, ...etc"

const solver = (text: any) => {
    this.resultingWords = words.split(",").filter(word => {
      word = word.toUpperCase()
      for (var i = 0; i < text.length; i++) {
        for (var j = 0; j < 5; j++) {
          let currentText = text[i][j]
          currentText[0] = currentText[0].toUpperCase()
          if (currentText[0] == '') { continue }
          if (currentText[1] == "green" && (word[j] != currentText[0])) {
            return false
          }
          if (currentText[1] == "black" && word.includes(currentText[0])) {
            return false;
          }
          if (currentText[1] == "orange" &&
          (word[j] == currentText[0] || !word.includes(currentText[0]))) {
            return false
          }
        }
      }
      return true
    })
  }

我遇到的问题是，如果一个单词有多个相同的字母，其中一个是绿色或橙色匹配，而另一个是黑色。由于我编写算法的方式，我没有得到任何结果。

正确解决此问题的方法是什么？

过滤黑名单样式是最佳解决方案吗？（相对于白名单）。

4

2 回答 2

1

你正在建立一个候选人名单，我认为这是一个好的开始。您是否将其列入白名单或黑名单并不重要，结果是候选人名单。唯一需要担心的是，您可以通过猜测不在候选列表中的单词来更快或更可靠地获得解决方案。为什么？因为这样你可以一次引入更多的新字母来检查单词是否包含它们。也许这两种策略的混合是最好的，如果不先测试就很难说。

  • “绿色”没问题。
  • “黑色”需要计算猜测中字母的非黑色出现次数，并且可以消除所有不包含该字母确切数量的单词（以及那些字母在黑色位置的单词）。
  • “橙色”是可以的，但可以改进：您可以在猜测中计算字母的非黑色出现次数，并减少包含该字母的所有单词（检查最小外观，而不仅仅是一次），并且您已经拥有的内容适用：字母不能位于橙色位置。

有很多改进的想法。首先，我会在浏览单词之前创建过滤器。使用与上述类似的逻辑，您将获得四种不同规则类型的集合：字母必须或不能位于特定位置，或者字母必须准确出现（可能为 0）或至少出现特定次数。然后你浏览这些单词并使用这些规则进行过滤。否则，某些工作可能会多次完成。通过首先在猜测中收集相同的字母来创建这样的过滤器是最简单的。如果存在确切数量的出现规则，那么您显然可以为同一个字母删除最小数量的出现规则。

为了快速猜出这个词，我会创建一个评估函数来找到候选者中最有希望的下一个猜测。可能的得分值：

  • 引入了多少新字母（尚未猜到的字母）。
  • 还可以考虑新字母的概率。例如，一个单词包含特定字母的可能性有多大。甚至看看字母之间的相关性：比如如果我有一个 Q，那么我可能也有一个 U，或者如果最后一个字母是 D，那么倒数第二个是 E 的可能性非常高。
  • 你甚至可以查看每个候选人的所有可能答案，看看哪个猜测平均消除了最多的单词或类似的东西。尽管这可能需要很长时间，除非以某种方式近似。
于 2022-02-04T10:05:33.487 回答
1

您需要匹配成对的字母（一个来自猜测，一个来自秘密单词）并将它们剔除，因此它们不会用于任何其他匹配。

您不能从“黑色”中得出相应的字母在解决方案中根本没有出现的结论。当在猜测中使用相同的字母两次时，一个可能会得到匹配（橙色或绿色），而另一个可能会得到黑色。

我建议管理目标单词中的出现次数。黑色指示表示您知道某个字母的最大出现次数（可能为 0）。当您获得绿色/橙色指示时，您知道出现的最小数量（可能会更新最大值，因此它不会不一致）。

我做了一个小实现，具有以下特点：

  • 一个Game类管理秘密词的选择；对猜测提供反馈；并提示游戏是否结束（在 6 次猜测或正确猜测后）

  • 一个play函数，它根据来自实例的先前反馈选择一个单词Game，并将其作为猜测提交，并重复该过程直到游戏结束。

  • play逻辑总是会做出与游戏期间收到的所有反馈一致的猜测（随机）。注意：这不是最佳策略。例如，5 个字母中有 4 个可能是绿色的，但可能需要多次尝试才能找到剩余的字符。

  • 该play逻辑从它获得的所有反馈中构建一个正则表达式，并且仅使用该正则表达式过滤单词。

这是代码：

class Game {
    #solution; // Private
    constructor(words) {
        this.#solution = words[Math.floor(Math.random() * words.length)];
        this.turnCount = 0;
        this.state = "playing";
    }
    guess(guessed) {
        if (guessed.length !== 5) throw "Invalid length";
        if (this.state !== "playing") throw "Game is already over";
        this.turnCount++;
        let attempt = [...guessed];
        let correct = [...this.#solution];
        attempt.forEach((ch, i) => {
            if (correct[i] === ch) correct[i] = attempt[i] = null;
        });
        this.state = !attempt.some(Boolean) ? "won" : this.turnCount >= 6 ? "lost" : "playing";
        return attempt.map((ch, i) => {
            if (ch == null) return [guessed[i], "green"];
            let j = correct.indexOf(ch);
            if (j >= 0) {
                correct[j] = null;
                return [ch, "orange"];
            }
            return [ch, "black"];
        });
    }
}

function play(words) {
    let game = new Game(words);
    let allowed = Array(5).fill("abcdefghijklmnopqrstuvwxyz");
    let letters = {}; // Letters with their minimum and maximum frequency
    while (game.state === "playing") {
        let regex = RegExp(Object.entries(letters).map(([ch, {min,max}]) =>
            max ? `(?=^[^${ch}]*(?:${ch}[^${ch}]*){${min},${max}}$)`
                : `(?!.*${ch})`
        ).join("") + allowed.map(s => "[" + s + "]").join(""), "i");
        words = words.filter(word => regex.test(word));
        // Pick a random word from the list of potential candidates
        let word = words[Math.floor(Math.random() * words.length)];
        let result = game.guess(word);
        console.log(words.length + " options. Guessing: " + word + " - feedback: " + result.map(([ch, color]) => color[0]).join(""));
        letters = {}; // This always starts from scratch
        result.forEach(([ch, color], i) => {
            if (letters[ch]) {
                letters[ch].max = color === "black" ? letters[ch].min : Math.max(++letters[ch].min, letters[ch].max);
            } else {
                letters[ch] = color === "black" ? { min: 0, max: 0 } : { min: 1, max: 5 };
            }
            allowed[i] = color === "green" ? ch : allowed[i].replace(ch, "");
        });
    }
    console.log("Game over. I " + game.state + " after " + game.turnCount + " attempts.");
}

const words = "dozen,brave,apple,climb,outer,pitch,ruler,holds,fixed,costs,calls"
    .match(/\w+/g);
play(words);

于 2022-02-04T11:51:43.360 回答