Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving Wordle in 3.64 guesses on average, 99.4% of the time

lockwood.dev

Post reply on HN
Print view View original

171–180 of 181 posts

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#171

Post by Grustaf »

tomlockwood wrote: post #155
Grustaf wrote: post #153

Earlier quoted context omitted.

It was just a random google result, but we definitely did rebuses in pre-school at least. The rebus concept is actually a precursor to actual writing, historically speaking. Both in Mesopotamia/Egypt and in the Chinese civilisation, writing developed through a rebus phase. So it's a very natural thing, that's why it's so child friendly.

That's all cool, why's it a common word, though?

Why? I mean most pre-schoolers probably play with rebuses, simple crosswords etc. It's just a common concept in the world that most people have come across.

Unlike say an obscure linguistic term like nisba.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#172

Post by kccqzy »

returningfory2 wrote: post #103
kccqzy wrote: post #44

Earlier quoted context omitted.

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…

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 ag…

> 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.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#173

Post by SoylentOrange »

This solution feels a little like cheating because it's using the "target" list to train. The target list contains all the solutions, while the larger list contains all 5-letter words. A human would not know the target list. For a more fair solver, it should add the two lists together to train, and then test on the target list.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#174

Post by tomlockwood »

Grustaf wrote: post #171
tomlockwood wrote: post #155

Earlier quoted context omitted.

That's all cool, why's it a common word, though?

Why? I mean most pre-schoolers probably play with rebuses, simple crosswords etc. It's just a common concept in the world that most people have come across. Unlike say an obscure linguistic term like nisba.

Oh I get that they exist, commonly, I just see no evidence to suggest the word is common.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#175

Post by WordHoot »

BoorishBears wrote: post #75
bbasketball wrote: post #23

If you like Wordle you should check out https://wordhoot.com/

I thought the UI of Wordle wasn't anything special but this makes me appreciate the subtle attention to detail that went into it That website you linked doesn't lock the viewport so on my phone it's constantly panning or randomly zooming And the grid instead a keyboard layout actually matters more than I expected for how easy it is to type Having to manually start a game is a tiny thing but doesn't feel as smooth

Are you still experiencing the panning/zooming issue? If so please let me know and I will look into it. I've updated keyboard layout. Thanks!

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#176

Post by returningfory2 »

kccqzy wrote: post #172
returningfory2 wrote: post #103

Earlier quoted context omitted.

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 ag…

> 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…

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

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#177

Post by hddqsb »

ottowinter wrote: post #82
thxg wrote: post #33

This [1] solves it in 3.4212 average guesses 100% of the time and claims optimality, which is 99% of the difficulty it seems. For the limited 2671-word set of possible words, I think the question is now settled (for the whole 12k-word set, I don't think anyone tried anything). It was posted here four days ago [2]. [1] http://sonorouschocolate.com/notes/index.php?title=The_best_... [2] https://news.ycombinator.com/ite…

Neat, didn't know that existed! Definitely would have saved me some time :) FWIW, I wrote a similar solution a couple of days ago as well, and come up with the same result (3.421166 guesses on average, with starting word SALET). So that would support that result. With the following strategy: https://drive.google.com/file/d/1WvxRRzbvDVnHZUczHBZAko3hKft... , code: https://drive.google.com/drive/folders/1Y8k685PS0wxvYul…

There is a leaderboard at https://botfights.io/game/wordle for solving with all 12972 words as possible solutions, it might be of interest.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#179

Post by normalocity »

shmde wrote: post #151

Why do people need 3 guess when the solution is literally in the localStorage /s

It depends on whether you want to play the game or break it. :D

Most people are taking this as a fun algorithmic exercise, assuming imperfect knowledge.

Re: Solving Wordle in 3.64 guesses on average, 99.4% of the time

#180

Post by ford »

pxx wrote: post #70
ford wrote: post #15

Earlier quoted context omitted.

There is a wordle parody (absurdle) [0] that does exactly this. [0] https://qntm.org/files/wordle/

No it does not. It uses a heuristic at every layer of the tree. Specifically, instead of recursing down each subtree, it chooses the set with the maximum number of remaining elements, which isn't necessarily the set that is most difficult to split.

I see - I misunderstood the parent comment.

I believe you are saying that the best adversary would attempt to maximize the depth of the tree. For example a branch with "{L, B, C, R, ..}ake" requires more guesses than a balanced tree despite the fact that the two trees may have the same number of nodes.

Post reply on HN