3 ms·
That's exactly my approach. I wrote a very simple O(N^3) algorithm to determine that: for each possible actual word and the guessed word, figure out whether or
by kccqzy 5y ago
That's exactly my approach.
I wrote a very simple O(N^3) algorithm to determine that: for each possible actual word and the guessed word, figure out whether or not a word is eliminated. Then calculate a score based on how many words can be eliminated from a particular guessed word, averaged over all possible actual words.
(I originally thought O(N^3) would be way too slow to be useful. But it runs fast enough with a few thousand words.)
Like a sibling comment, I also found that the best initial guess is RAISE, although when I tried a different word list, I got different words like LARES (I don't think it's in the Wordle list).
One thing that surprises me is that by the time you get to the mid-game stage (after 2 guesses or so), occasionally it can be more optimal to guess a word with repeated letters; I did not originally expect that because I thought repeated letters are wasted opportunity to test more letters, but it turns out Wordle's handling of repeated letters can give you helpful information about the number of occurrences of a letter. (For example if you picked a word with 2 a's, the first one can be green the second one can be black, essentially telling you there is exactly one letter "a" in the word.)
- carry_bit 5y agoI also implemented essentially this algorithm. For guesses I always consider the full list of possible words, not just the list of possible answers. Doing so requires a check so words that have been excluded are only used if they're better than words that haven't been.
- returningfory2 5y agoFWIW, 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 agoYeah, 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).