7
\$\begingroup\$

A lot of Wordle clones get the tile-coloring algorithm wrong: for example,

  • if the word is BURNT and you guess TOAST, the colors should be ----G (not Y---G)
  • if the word is MAXIM and you guess MAMMA, the colors should be GGY-- (not GGYYY)
  • if the word is SWIFT and you guess IIWIS, the colors should be Y-Y-Y (not YYYYY)

I've written a JavaScript implementation of the tile-coloring algorithm. I'd like to know both whether it's correct (non-buggy), and how it can be improved. In particular, if there's some way to compute just the color of the indexth tile, without computing all the tiles' colors as a side effect, that would be nice to know.

function computeColor(targetWord, guess, index) {
  let colors = Array(WORD_LENGTH).fill("wrong")
  for (var i = 0; i < WORD_LENGTH; ++i) {
    if (targetWord[i] === guess[i]) {
      colors[i] = "correct"
    } else if (targetWord.includes(guess[i])) {
      colors[i] = "wrong-location"
    }
  }
  for (var i = 0; i < WORD_LENGTH; ++i) {
    if (colors[i] == "wrong-location") {
      // Only the correct number of tiles should be colored yellow.
      const letter = guess[i]
      const targetCount = targetWord.split('').filter((ch) => ch == letter).length
      const greenCount = Array.from(Array(WORD_LENGTH).keys()).filter((j) => (guess[j] === letter && colors[j] === "correct")).length
      const maxYellowCount = targetCount - greenCount
      let currentYellowCount = 0
      for (var j = 0; j < i; ++j) {
        if (guess[j] == letter && colors[j] === "wrong-location") {
          currentYellowCount += 1
        }
      }
      if (currentYellowCount == maxYellowCount) {
        colors[i] = "wrong"
      }
    }
  }
  return colors[index]
}

console.assert(computeColor('BURNT', 'TOAST', 0) === "wrong")
console.assert(computeColor('BURNT', 'TOAST', 1) === "wrong")
console.assert(computeColor('BURNT', 'TOAST', 2) === "wrong")
console.assert(computeColor('BURNT', 'TOAST', 3) === "wrong")
console.assert(computeColor('BURNT', 'TOAST', 4) === "correct")

console.assert(computeColor('MAXIM', 'MAMMA', 0) === "correct")
console.assert(computeColor('MAXIM', 'MAMMA', 1) === "correct")
console.assert(computeColor('MAXIM', 'MAMMA', 2) === "wrong-location")
console.assert(computeColor('MAXIM', 'MAMMA', 3) === "wrong")
console.assert(computeColor('MAXIM', 'MAMMA', 4) === "wrong")

console.assert(computeColor('SWIFT', 'IIWIS', 0) === "wrong-location")
console.assert(computeColor('SWIFT', 'IIWIS', 1) === "wrong")
console.assert(computeColor('SWIFT', 'IIWIS', 2) === "wrong-location")
console.assert(computeColor('SWIFT', 'IIWIS', 3) === "wrong")
console.assert(computeColor('SWIFT', 'IIWIS', 4) === "wrong-location")
```
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

REVISED


Code should be correct, maintainable, robust, reasonably efficient, and, most important, readable.


Wordle is a clever, challenging, and fun game implemented by a skilled software engineer.

Hi, I'm Josh [Wardle].
https://powerlanguage.co.uk/

Wordle is daily word guessing game I made.

The Wordle tile coloring rules are:

Guess the WORDLE in six tries.

Each guess must be a valid five-letter word. Hit the enter button to submit.

After each guess, the color of the tiles will change to show how close your guess was to the word.

Green: The letter is in the word and in the correct spot.

Yellow: The letter is in the word but in the wrong spot.

Gray: The letter is not in the word in any spot.


Review 1 is a code review that critiques the OP's code and provides a revised, simplified version of the OP's code that conforms to Wordle rules. The revised code efficiently satisfies the rule that five letters must be entered before the color of the tiles change by returning a five letter array of tile colors.


In a comment on Review 1, the OP says: "the "wordle.js" I'm plugging this into expects a function with the given signature [(word, guess, index)]; I wanted to surgically replace just the buggy coloring function."

Review 2 refactors the revised solution from Review 1 to provide an efficient function with the expected signature: (word, guess, index).



REVIEW 1

I'd like to know whether it's correct

Your code is complicated. It's hard to prove it is correct.


Production executable code, like Wordle, is minified, use spacing and useful comments to enhance readability.

The letter background colors will be used both inside and outside the function. Use outside the function color constants.

Simplify your code. In particular, eliminate extraneous methods: split, filter, from, keys, and so on. Some of these methods implement implicit loops, which, inside a for loop, have O(n**2) complexity. The simplified code has only two loops with O(n) complexity.

Don't use var for variable declarations. Use let or const.

Don't use == for equality; use === for strict equality.

There is no reason to limit the function to five letter words and guesses. However, check the function word and guess length equality invariant.

The simplfied code, as required by Wordle, returns a complete array of letter background colors. The original function only returns the color for a single letter. There is (times five) computational rundundancy to color all five letters of a guess.

Using jsbench.me, coloring a five letter guess using the original code is over 90% slower than the simplified code.


Here is a simplified version of your code:

// letter background colors
const COLOR_NOT_ENTERED   = "White";
const COLOR_CORRECT_SPOT  = "Green";
const COLOR_WRONG_SPOT    = "Yellow";
const COLOR_NOT_ANY_SPOT  = "Gray";

// guessColors returns an array of guess letter background colors.
function guessColors(word, guess) { 
    let colors = new Array(guess.length);
    if (word.length !== guess.length) {
        return colors.fill(COLOR_NOT_ENTERED);
    }

    // color matched guess letters as correct-spot, 
    // and count unmatched word letters
    let unmatched = {}; // unmatched word letters
    for (let i = 0; i < word.length; i++) {
        let letter = word[i];
        if (letter === guess[i]) {
            colors[i] = COLOR_CORRECT_SPOT;
        } else {
            unmatched[letter] = (unmatched[letter] || 0) + 1;
        }
    }

    // color unmatched guess letters right-to-left, 
    // allocating remaining word letters as wrong-spot,
    // otherwise, as not-any-spot
    for (let i = 0; i < guess.length; i++) {
        let letter = guess[i];
        if (letter !== word[i]) {
            if (unmatched[letter]) {
                colors[i] = COLOR_WRONG_SPOT;
                unmatched[letter]--;
            } else {
                colors[i] = COLOR_NOT_ANY_SPOT;
            }
        }
    }

    return colors;
}


if there's some way to compute just the color of the indexth tile, without computing all the tiles' colors as a side effect.

There is not. Why do you want to do that?


Consider a word

[ A X A A A ] 

and a partial (index 0) guess of

[ X - - - - ] 

which evaluates to colors

[ Yellow, ------, ------, ------, ------ ]

Now, add another letter to the guess, a partial (index 1) guess of

[ X X - - - ] 

which evaluates to colors

[ Grey,   Green,  ------, ------, ------ ]

Partial colors evaluation is not always stable.



REVIEW 2


Here is a revised, simplified version of the OP's code to provide a more readable, more efficient function with the expected signature: (word, guess, index).

Using jsbench.me, the OP's code is about 96% slower than the following simplified code. The simplified code is about 25 times faster. The simplified code only has one loop. The simplified code does not contain extraneous code.

Wordle rules:

Each guess must be a valid five-letter word.
Hit the enter button to submit.
After each guess, the color of the tiles will change.

For an official, accurate Wordle guess tile color, on each call to the function "guess must be a five-letter word." Wait until the guess is submitted: "Hit the enter button to submit."

A simple example illustrates the problem. Using Wordle rules, tile color depends on guess letters before and after guess[index]:

AXAAA
X
[ 'Yellow', 'Gray', 'Gray', 'Gray', 'Gray' ]
AXAAA
XX
[ 'Gray', 'Green', 'Gray', 'Gray', 'Gray' ]

The tile color for guess[0] varies depending on how many guess letters are entered.

Also, coloring tiles before the guess is complete would ruin the game by making it too easy.


// Wordle letter tile background colors
const COLOR_CORRECT_SPOT  = "Green";
const COLOR_WRONG_SPOT    = "Yellow";
const COLOR_NOT_ANY_SPOT  = "Gray";

// guessColor returns the guess[index] letter tile background color.
// 
// Wordle tile coloring rules: 
// Each guess must be a valid five-letter word. 
// Hit the enter button to submit. 
// After each guess, the color of the tiles will change.
// Green:   The letter is in the word and in the correct spot.   
// Yellow:  The letter is in the word but in the wrong spot.   
// Gray:    The letter is not in the word in any spot.   
function guessColor(word, guess, index) {
    // correct (matched) index letter
    if (guess[index] === word[index]) {
        return COLOR_CORRECT_SPOT;
    }

    let wrongWord = wrongGuess = 0;
    for (let i = 0; i < word.length; i++) {
        // count the wrong (unmatched) letters
        if (word[i] === guess[index] && guess[i] !== guess[index] ) {
            wrongWord++;
        }
        if (i <= index) {
            if (guess[i] === guess[index] && word[i] !== guess[index]) {
                wrongGuess++;
            }
        }

        // an unmatched guess letter is wrong if it pairs with 
        // an unmatched word letter
        if (i >= index) {
            if (wrongGuess === 0) {
                break;
            } 
            if (wrongGuess <= wrongWord) {
                return COLOR_WRONG_SPOT;
            }
        }
    }

    // otherwise not any
    return COLOR_NOT_ANY_SPOT;
}

function testGuessColor(tests) {
    for (let [word, guess] of tests) {
        console.log(word);
        console.log(guess);
        let colors = [];
        for (let i = 0; i < word.length; i++) {
            colors.push(guessColor(word, guess, i));
        }
        console.log(colors);
    }
}

let tests = [
    ['BURNT', 'TOAST'],
    ['MAXIM', 'MAMMA'],
    ['SWIFT', 'IIWIS'],
    ['ABBEY', 'BOBBY'],
    ["ABCDE", "ABCDE"],
    ["ABCDE", "VWXYZ"],
];
testGuessColor(tests);

$ node wordle.js
BURNT
TOAST
[ 'Gray', 'Gray', 'Gray', 'Gray', 'Green' ]
MAXIM
MAMMA
[ 'Green', 'Green', 'Yellow', 'Gray', 'Gray' ]
SWIFT
IIWIS
[ 'Yellow', 'Gray', 'Yellow', 'Gray', 'Yellow' ]
ABBEY
BOBBY
[ 'Yellow', 'Gray', 'Green', 'Gray', 'Green' ]
ABCDE
ABCDE
[ 'Green', 'Green', 'Green', 'Green', 'Green' ]
ABCDE
VWXYZ
[ 'Gray', 'Gray', 'Gray', 'Gray', 'Gray' ]
$ 
\$\endgroup\$
3
  • \$\begingroup\$ I could disagree with a lot of your comments, but ultimately your implementation was the most helpful in rewriting mine. The idea of looping first over the targetWord, then over the guess, is clever. Re "Why do you want to do that?": Because the "wordle.js" I'm plugging this into expects a function with the given signature; I wanted to surgically replace just the buggy coloring function. Your example shows why we need to look at all 5 letters in order to compute the color of tile 0, but it doesn't prove that we need to compute all 5 tiles' final colors just in order to compute tile 0's. \$\endgroup\$ Feb 22 at 13:52
  • \$\begingroup\$ Re keys, filter, etc: The "wordle.js" I'm plugging this into gets away (somehow) with no other for-loops; I was introducing the only for-loops (and thus the only semicolons) in the entire script. So I was feeling a bit guilty about that, and looking for ways to express "count the Xs in Y" without for-loops. My efforts didn't even pay off: I ended up with three(!) for-loops anyway! But anyway, that's the story of why I didn't just write for-loops to do the counting at first. I think for (let i in guess) would work for both of these loops, but I assume that'd be considered obfuscatory... \$\endgroup\$ Feb 22 at 13:58
  • \$\begingroup\$ @Quuxplusone: See my revised answer, especially, the Review 2 section. \$\endgroup\$
    – peterSO
    Feb 27 at 18:13
2
\$\begingroup\$

My very first thought was, let's change the function signature to computeColors(targetWord, guess) and have it return all the colors as a 5-character string in your specified format: G for green, Y for yellow, and - for gray. computeColor currently throws away a lot of good work, only to return the appraisal of a single letter in guess, when we could be returning the colors for the entire guess.

Your algorithm is correct as far as I can tell; I tried a few more test cases from my previous Wordle reviews and they all passed. That being said, the nested iterating & tracking for currentYellowCount makes this an \$O(n^2)\$ solution when an \$O(n)\$ solution is possible — although to be fair, this doesn't really matter in practice when \$n\$ is so small) — but I do think the nested loops make the code harder to read.

We really only need two passes: in the first pass we identify the green letters, and in the second pass we iterate over the remaining letters and classify them as either yellow or gray. See the example implementation below.


Some JavaScript-specific nits:

  • let colors can be const colors, and the vars used for for loop indices should be changed to lets to limit variable scope & avoid JavaScript's variable hoisting.
  • all your equality checks can and should be using strict equality ===.

Example implementation:

const WORD_LENGTH = 5;

function computeColors(targetWord, guess) {
  const colors = Array(WORD_LENGTH).fill(null);
  const indicesOfIncorrectLettersInGuess = [];
  // Tracks the letters (and counts of those letters)
  // in `targetWord` that were not used up by `guess`
  const targetLetters = {};

  for (let i = 0; i < WORD_LENGTH; ++i) {
    let targetLetter = targetWord[i];

    if (targetLetter in targetLetters) {
      targetLetters[targetLetter]++;
    } else {
      targetLetters[targetLetter] = 1;
    }

    if (guess[i] === targetLetter) {
      colors[i] = "G";
      targetLetters[targetLetter]--;
    } else {
      indicesOfIncorrectLettersInGuess.push(i);
    }
  }

  for (const i of indicesOfIncorrectLettersInGuess) {
    let guessLetter = guess[i];

    if (guessLetter in targetLetters && targetLetters[guessLetter] > 0) {
      colors[i] = "Y";
      targetLetters[guessLetter]--;
    } else {
      colors[i] = "-";
    }
  }

  return colors.join("");
}

function test(targetWord, guess, expectedOutput) {
  const actualOutput = computeColors(targetWord, guess);
  console.assert(
    expectedOutput === actualOutput,
    {targetWord, guess, expectedOutput, actualOutput}
  );
}

test(
  "BURNT",
  "TOAST",
  "----G"
);

test(
  "MAXIM",
  "MAMMA",
  "GGY--"
);

test(
  "SWIFT",
  "IIWIS",
  "Y-Y-Y"
);

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.