The "worst-case number of guesses" objective considered here is pretty insensitive to differences in quality of the decision tree. It seems to me that a better objective would be: minimize the number of secret words that take more than 6 guesses (hopefully to zero), then minimize how many that take 6 guesses, and so on.
What you described is not what joshbuckler described.
joshbuckler wants an algorithm that has the fewest words that take at least 6 guesses, and also among all algorithms that tie for that number of words that take at least 6 guesses, has the fewest number of words that take at least 5 guesses, and also among all the algorithms that tie for that number of words that take at least 6 and at least 5 guesses, has the fewest number of words that take at least 4 guesses, and also...
The page you linked to doesn't seem to say it does that.
As I noted, adversarial wordle shows that no words take 6 guesses and only 2 words take 5 guesses (BOOZY and BOOBY.)
If you removed just 1 of those 2 words (leaving 2312 possible Wordles) all Wordles can be solved in max 4 guesses.
Ignoring the 2 scenarios where your first two "optimal" guesses are the Wordle
X% of the time you have 1 word left (guesses= 3)
Y% of the time you have 2 words left (guesses =3.5)
(100-Y-X)% of the time there is a pool of words left, requiring one more "optimal" guess
And either your optimal guess #3 is the Wordle Z% of the time (guess=3) or there is now one word remaining (guess ≈ 4)
Where Z in this case is just a function of the number of words remaining (ie Y is just a special case of Z)
So you want to maximize X and the weighted average of Z across pools.
By sheer brute force you can do so
1) for each 2 guess combo
2) discard any "suboptimal" combo where for any remaining response state word pool there is no optimal guess #3 (ie not possible to definitively guess in 4 guesses)
3) calculate avg remaining guesses
4) identify optimal word 1 (minimum of sum of step 2 per first guess)
5) within combos with word 1, identify optimal guess 2 for each response state
And the weighted average of step 3 for these combos is the global minimum for Wordle.
I believe this is the algorithm you're after? In this case, we're making a first guess that maximizes the chance we will get 3 guesses instead of 4.
If you then diagonalize that connection matrix, you can get constant time (though you might have to make a special case for starting at the `5` key):
"Diagonalization can be used to efficiently compute the powers of a matrix..." [1]
Diagonalizing the matrix makes it easier to calculate the exponent by making it a series of numeric exponentials, but calculating the exponent of a number is still a log(n) operation.
Also given that this is a discrete problem moving to floating points like you'd likely have to do when you diagonalize could easily lead to errors in the final answer.
I tried but Wolfram Alpha doesn't take inputs that long hah. In any case even if it works you will likely get irrational terms which will make it only theoretically nice but not practically computable, like the closed-form Fibonacci formula.
Instant-runoff is a terrible voting system and should never be used, see http://zesty.ca/voting/sim/ . Approval voting is simpler and better. Condorcet is best except that it is somewhat complicated.
I had dug into the math behind this at some point and recall that Borda was argued (e.g. by Saari's "Basic Geometry of Voting") to be the "best" in the sense of invariance under impossible-to-satisfy group preference cycles (A > B > C >A), with Condorcet a close second.
If you have any references arguing for Condorcet over Borda, I would be very interested to read them.
Edit: For people unfamiliar with the jargon, Borda is ranked-list voting, with the winner being the candidate with the highest average rank. Condorcet is pairwise-comparison voting with the winner being the candidate that wins the highest fraction of pairwise comparisons.
In this jargon, "first past the post" systems select the person with the highest fraction of being ranked first; this is argued in the literature to be intimately tied to the two-party dominance in the US.
