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

Question

对于上下文 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
    })
  }

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

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

黑名单过滤方式是最好的解决方案吗？ (与白名单相反)。

Answer 1

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

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

我建议管理目标词的出现次数。黑色指示表示您知道某个字母的最大 出现次数(可能为 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);