3 ms·

FWIW, your O(N^3) algorithm can be equivalently implemented in O(N^2) by using the following observation: a word is not eliminated by a guess if and only if the

FWIW, your O(N^3) algorithm can be equivalently implemented in O(N^2) by using the following observation: a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution. Using this, you can implement the algorithm like so: for a given solution, partition all of the guesses based on the result of testing them against that solution. This partitioning takes O(N). Then, the set of words that will be left over from a guess is equal to all the words in the same partition as the guess. This makes it easy to calculate "how many words can be eliminated from a particular guessed word". I'm making this comment because I started with the same O(N^3) approach and then realized this. :)

kccqzy 5y ago
> a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution That's not true. Suppose the actual word is "abcdx" but the guessed word is "xefgh". The result of testing is Yellow-Black-Black-Black-Black. Now suppose you have other words like "xijkl" that will test against the solution in exactly the same way (Yellow-Black-Black-Black-Black), but you know won't be the correct solution because in the first round the misplaced "x" already tells you "x" should be present at a different position. So now we have a word that can be eliminated even if it tests against the solution in the way the guessed word does.
- returningfory2 5y ago
  Yeah, I think I messed up which things you need to partition. Given a set of possible solutions, and a guess, you partition the solutions based on which result Wordle gives back. Then you can calculate the expected number of solutions that will be left after you make that guess. This takes O(N). Going this for all guesses is then O(N^2).

kccqzy 5y ago

> a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution That's not true. Suppose the actual word is "abcdx" but the guessed word is "xefgh". The result of testing is Yellow-Black-Black-Black-Black. Now suppose you have other words like "xijkl" that will test against the solution in exactly the same way (Yellow-Black-Black-Black-Black), but you know won't be the correct solution because in the first round the misplaced "x" already tells you "x" should be present at a different position. So now we have a word that can be eliminated even if it tests against the solution in the way the guessed word does.

returningfory2 5y ago
Yeah, I think I messed up which things you need to partition. Given a set of possible solutions, and a guess, you partition the solutions based on which result Wordle gives back. Then you can calculate the expected number of solutions that will be left after you make that guess. This takes O(N). Going this for all guesses is then O(N^2).