为什么我的 Wordle 解算器在出现重复字符时会失败？

Question

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

如果字符为黑色，则表示目标词中没有匹配该字符的字符。
如果一个字符是橙色的，则表示在目标词中有一个字符与该字符匹配，但它位于不同的位置。
如果字符为绿色，则位置和字符匹配。

我正在制作一个 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
    })
  }

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

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

黑名单过滤方式是最好的解决方案吗？（与白名单相对）。

Answer 1

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

“绿色”可以。
"black" 需要计算字母在猜测中出现的 non-black 次，并且可以消除所有不包含该字母确切数量的单词（以及那些字母位于黑色位置）。
"orange" 还可以，但可以改进：您可以计算 non-black 字母在猜测中出现的次数，并减少所有包含该字母的单词的次数（检查最少的外观而不是至少一次）并且你已经拥有的也适用：字母不能在橙色位置。

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

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

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

Answer 2

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

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

我建议管理目标词的出现次数。黑色指示表示您知道某个字母的最大出现次数（可能为 0）。当您收到 green/orange 指示时，您知道出现的最小次数（可能会更新最大次数以使其不一致）。

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

A Game class 管理密语的选择；对猜测给予反馈；并给出游戏是否结束的指示（在 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);

为什么我的 Wordle 解算器在出现重复字符时会失败？

Why is my Wordle solver failing when there are repeated characters?

javascript

algorithm

wordle-game