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

Question

For context Wordle is game where you have to decipher a 5 letter word in 6 or less guesses based on certain hints. The hints you get are as follows:

If a character is coloured black there are no characters that match that character in the target word.
If a character is coloured orange there is a character that matches that character in the target word but it is in a different position.
If a character is coloured green the position and the character are a match.

I am making a wordle solver program that takes in an array of word attempts and eliminates them from a list of the possible words.

I feel that the best algorithm to solve this problem is a black list where a word that breaks one of the rules is eliminated from the array. But if there is a better alternative I am open to suggestion.


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
    })
  }

The issue I am having is if a word has multiple of the same letter and one of them is a green or orange match but the other is black. I get no results because of the way I've written my algorithm.

What would be the way to correctly solve this problem?

Is a black list style of filtering the best solution? (as opposed to white list).

trincot · Accepted Answer

You need to match pairs of letters (one from the guess, one from the secret word) and strike them out, so they don't serve for any other match.

You cannot conclude from a "black" that the corresponding letter is not occurring at all in the solution. When the same letter was used twice in the guess, one may get a match (orange or green), while the other may get black.

I would suggest to manage the number of occurrences in the targeted word. A black indication means you know the maximum number of occurrences of a certain letter (which may be 0). When you get a green/orange indication, you know about a minimum number of occurrences (possibly updating the maximum so it is not inconsistent).

I made a little implementation with the following characteristics:

A Game class manages the choice of the secret word; giving feedback on a guess; and giving an indication on whether the game is over (after 6 guesses or a correct guess)
A play function which chooses a word based on previous feedback from the Game instance, and submits it as a guess, and repeats the process until the game is over.
The play logic will always make a guess (randomly) that is in line with all the feedback received during the game. NB: This is not the optimal strategy. For instance, 4 letters out of 5 may be green, but then many attempts may be needed to find that remaining character.
The play logic builds a regular expression from all the feedback it got, and only filters words with that regex.

Here is the code:

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);

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

Answers (2)

Related Questions