# Wordle solver challenge

Wordle is a daily online word game that has received considerable attention recently.

# The Game

The object is to guess a secret word in the fewest attempts. Consider the following instance of the game:

The secret word is rebus, and the player's first guess was arise. The letters r, s, and e are displayed in yellow to indicate that these letters appear in the secret word, but not at these locations. Meanwhile, the letters in gray do not appear in the secret word at all. The player uses this information to formulate a second guess: route. Here, the r appears in green, indicating that r appears in the secret word at this location. Notice that each guess is an English word.

A comment on duplicated letters: If the first guess above were river, then the first r would appear in green, but the second r would appear in gray. In general, the duplicated letters are only highlighted if they are similarly duplicated in the solution, and letters appear in green whenever possible. As another example, suppose the secret is inane and we guess nanny. Then our first n will be marked in yellow, the second in gray, and the third in green. In this case, only two of our three ns are highlighted since the secret only has two ns.

# The Challenge

In this challenge, you will write code that plays Wordle as well as possible. The following link contains a curated list of 2315 common 5-letter words:

words.txt

Notably, every Wordle solution to date appears on this list, and I suspect future solutions will, too.

Your code will play Wordle by iteratively selecting words from the above .txt file and receiving Wordle-style feedback on which letters appear in the secret word. To evaluate your code, play this game 2315 times (each time using a different secret word from the above .txt file), and record the number of guesses it took to win. (While the official game terminates after six guesses, in this challenge, you may take arbitrarily many guesses.)

In the end, your score will be the histogram of the number of guesses required, arranged in a tuple. For example, (1,1000,900,414) is a 4-tuple that indicates that the code solved every word in only 4 guesses, with 414 words requiring all 4 guesses, 900 taking only 3, 1000 taking only 2, and one word being identified after a single guess. Your code must be deterministic (i.e., your first guess will be fixed), and so the first entry of your score tuple will necessarily be 1.

A comment on implementation: There are a few ways to organize things (and to encourage participation, I don't want to impose any one way), but one approach is to write three programs: the game, the player, and the evaluator. The game receives a secret and a guess (both from words.txt) and outputs Wordle-style feedback. The player interacts with the game for some fixed secret word. The evaluator makes the player play the game for each secret word from words.txt. (One might use submissions from Build a Mastermind engine to write the game program, but for this challenge, the interesting program is the player.)

# The Winner

Scores will be compared in lexicographic order. That is, shorter tuples are better, and tuples of the same size are first compared in the last entry, then second-to-last entry, etc. For example:

(1,1000,900,414) < (1,1000,899,415) < (1,999,900,415) < (1,998,900,415,1)

Lowest score wins.

• So, just to clarify, our program will take in a word from the provided list as input, receive some feedback on the accuracy of the letters of the input (how will the program get this feedback?), then output the next guess? This looks like a very interesting challenge, but seems to be unclear (at least to me) on a few bits. For example, would the interactive tag apply here, for the feedback part? Commented Jan 14, 2022 at 16:04
• @cairdcoinheringaahing - There are a few ways to organize things (and to encourage participation, I don't want to impose any one way), but one approach is to write three programs: the game, the player, and the evaluator. The game receives a secret and a guess (both from words.txt) and outputs Wordle-style feedback. The player interacts with the game for some fixed secret word. The evaluator makes the player play the game for each secret word from words.txt. (Here, the interesting program is the player.) Commented Jan 14, 2022 at 16:14
• Out of curiosity, why is the metric not "lowest total number of guesses"? Commented Jan 15, 2022 at 5:52
• @Jonah - I think by "total" you mean add the numbers of guesses required for each of the 2315 secret words. Minimizing this is equivalent to minimizing the average number of guesses required. I'm more interested in the worst-case behavior, i.e., I want a player that solves every instance in at most 4 guesses, say. But given two such players, the better player is the one who spends 4 guesses on fewer words, etc. This is what the lexicographic order encodes. Commented Jan 15, 2022 at 11:29
• Does this answer your question? Build a Mastermind engine Commented Jan 15, 2022 at 21:04

# Python 3, (1, 149, 945, 1118, 102)

from collections import Counter

# history: a list of tuple of (guess, feedback)
# feedback: a list of length 5, each element can be MISS, CLOSE, or MATCH
def play(history):
# Hard coded first guess
turn = len(history) + 1
if turn == 1:
return 'trace'

# When there are few words left
remaining_words = [word for word in WORDS if all(get_feedback(guess, word) == feedback for guess, feedback in history)]
if len(remaining_words) <= 2:
return remaining_words[0]

# Hardcoded hard case
if turn == 3 and history == [('trace', [MISS, CLOSE, MISS, MISS, CLOSE]), ('risen', [CLOSE, MISS, MISS, MATCH, MISS])]:
return 'howdy'

guess_list = WORDS if turn > 2 and len(remaining_words) < 100 else remaining_words
return find_best_guest(guess_list, remaining_words)

def find_best_guest(guess_list, secret_list):
R = []
secret_set = set(secret_list)
for guess in guess_list:
c = Counter([tuple(get_feedback(guess, secret)) for secret in secret_list])
R.append([guess, len(c), guess in secret_set, -max(c.values())])
best_guess = max(R, key=lambda t:t[1:])
return best_guess[0]


Try it online!

Scorer

# Big idea

Each time, I pick the guess from the list of remaining words (words matching all previous guesses), such that the guess maximize the number of possible outcomes. For example, at the start, we guess "trace". This splits the possible secrets into 150 groups, only one of which is possible based on the feedback. For the second guess, if we guess a word from that group, then there is 1 universe where we guess correctly. Thus in total, we have 150 universes where we guess correctly within the first 2 turns. By maximizing the number of groups each turn, we can make sure that there are more universes where we guess correctly early on.

Following the naive strategy above, the result is (1, 149, 1044, 904, 178, 31, 7, 1). If we score by lexicographical order from left to right, without caring about the length of the tuple, then this is the largest tuple possible. Heuristically, this is good since if the left entries of the tuple are as large as possible, then the right most entries will be small. However, because the most important criteria is the length of the tuple, I have to tweak this algorithm a bit to get rid of all cases that have >5 turns.

# Optimization

• If we have too few remaining words, then we might have to guess a word outside of those, to get the best split. Specifically, I allow selecting from outside if we're at the 3rd guess (or after) and there are less than 100 remaining words.
• I brute forced search a some hard subtrees (e.g. 'trace' -> 'risen') to get the worst case at most 5 guesses.
• If instead of the negative of the maximum count you consider the negative of the reverse sorted counts (keeping everything else the same) you'll get 111 as the final value. That is R.append([guess, len(c), [-1*v for v in sorted(c.values(), reverse=True)]]) Commented Jan 16, 2022 at 21:44
• Oh, and of course best_guess = max(R, key=lambda t:t[1:]) ...Tiny TIO tinyurl.com/2p8v6zw6 Commented Jan 16, 2022 at 21:57
• In your TIO scorer, I commented out the condition after guess_list = WORDS, so that it would always pick from the full dictionary, and obtained [1, 81, 1181, 968, 81, 3]. Maybe it is possible to hardcode those 3 cases too, for a nicer count of fives? Commented Jan 24, 2022 at 14:55

# Python 3, [1, 49, 871, 1354, 40]

Idea

1. Use Knuth's minimax algorithm for Mastermind as default strategy. That is, minimize the number of remaining words for worst case group.
2. Find good starting words. 'alter', 'cater', 'close', 'crate', 'crone', 'lance', 'react', 'slant', 'stole', 'trace' are some of the good words (best 10 in my opinion). 'trace' and 'crate' score [1, x, x, x, 9x, 1] and 'alter', 'cater', 'trace' words score [1, x, x, x, 100]. Other words have 110 5th guess or less. (All using default strategy)
3. Do this recursively.
• For each nth word, for each worst case group which results in at least one 5th guess, try every single word and find 10 best word that minimizes number of 5th guess.

For example, first guess 'lance' and feedback CLOSE, CLOSE, MISS, MISS, MATCH leaves 2 5th guesses using second move from default strategy 'blast'. One can find that using either 'sight', 'smart', 'sharp', or 'fight' reduces number of 5th guess to 1 and one can recursively continue from there.

from collections import Counter

hard_codes = {(): 'lance', (0, 1, 0, 0, 0): 'sport', (1, 1, 0, 0, 2): 'sight', (0, 2, 0, 0, 0): 'storm', (0, 2, 0, 0, 1): 'straw', (0, 0, 0, 0, 1): 'posit', (0, 0, 0, 0, 1, 0, 0, 0, 0, 0): 'defer', (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 1): 'berry', (0, 0, 0, 0, 1, 0, 0, 0, 0, 1): 'deter', (0, 0, 0, 0, 1, 0, 2, 0, 0, 0): 'rowdy', (0, 0, 0, 0, 1, 0, 0, 0, 1, 0): 'drier', (0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 2): 'fiber', (0, 0, 0, 0, 1, 0, 0, 1, 0, 0): 'sever', (0, 0, 1, 0, 1): 'sewer', (1, 0, 0, 0, 1, 0, 0, 0, 2, 2): 'disco', (0, 0, 0, 0, 0): 'frost', (0, 0, 0, 0, 0, 0, 0, 0, 0, 0): 'pudgy', (0, 0, 0, 0, 0, 0, 0, 1, 0, 0): 'buddy', (0, 0, 0, 0, 0, 0, 0, 2, 0, 0): 'woody', (0, 0, 0, 0, 0, 0, 2, 2, 0, 0): 'buddy', (0, 0, 0, 0, 0, 0, 0, 0, 1, 0): 'mushy', (1, 0, 0, 0, 0): 'still', (1, 0, 0, 0, 0, 0, 0, 0, 1, 0): 'plumb', (1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0): 'flood', (1, 0, 0, 0, 0, 0, 0, 0, 2, 1): 'fudge', (0, 0, 0, 0, 2): 'first', (0, 0, 1, 0, 0): 'wrist', (0, 0, 1, 0, 0, 0, 0, 0, 0, 0): 'nymph'}

# history: a list of feedbacks, flattened
# feedback: a list of length 5, each element can be MISS, CLOSE, or MATCH
def play(history, remaining_words):
history = tuple(history)
if history in hard_codes:
return hard_codes[history]

if len(remaining_words) <= 2:
return remaining_words[0]

key = lambda g: max(Counter(tuple(get_feedback(g, c)) for c in remaining_words).values())
return min(WORDS, key=key)



Try it online!

Some interesting results outside of code golf (they have larger word set for guessing and the strategy cannot be applied to this challenge):

• Welcome to Code Golf, and nice answer! Commented Feb 6, 2022 at 3:04

# BQN

┌─
╵ 1  2   3   4   5   6  7  8 9
1 56 407 861 722 210 44 13 1
┘


The strategy is very basic, this just chooses the first word in the word lists that is still possible according to the previous results. I will improve on that later, but for now I just wanted to get the "infrastructure" up.

#!/usr/bin/env bqn

# Judge takes the correct and word and a guess, and returns a pair of vectors
# The first has 1's at green letters, the second one 1's at yellow letters
Judge ← { word 𝕊 guess:
wrong ← ¬correct ← word=guess
misplaced ← (+⊸×wrong)⊏0∾word(⊒∘⊢<·+˝=⌜)○(wrong⊸/)guess
correct⋈misplaced
}

# Game takes a path to the word list,
# plays every single word, and returns an histogram
Game ← { 𝕊 file:
words ← •FLines file
1↓˘⊒˜⊸≍≠¨⊔˜ {𝕩⊸Judge _Player words}¨ words
}

# The Player takes a monadic judge as its left operand and a word list as the right argument
# It has to guess until it finds the right word and return its score ( Don't cheat ;) )
_Player ← { Ju _P words:
score ← Ju attempt←⊑words
¬∧´⊑score ? 1+Ju _P words/˜(score≡Judge⟜attempt)¨ words ; 1
}

•Show Game "words.txt"


This should be run in the same directory as the words.txt file. You can try a modified version with only 100 words online here, the full program is a bit too much for the JS interpreter.

• Cool. Apparently, some people online play "hard mode" Wordle, wherein you're only allowed to guess words that are consistent with all of the information obtained so far. This strategy plays in hard mode. Unfortunately, that means that the worst-case performance isn't so great, because it gets stuck on words like "tatty" after learning that it is of the form "_a__y". Commented Jan 15, 2022 at 20:31

# Clojure, (1 59 1051 1166 38)

(def lookup {
;; turn 1
"" "stole",
;; turn 2
"*-*--" "prawn", "*----" "prank", "*--++" "spiel", "-+-+-" "final", "--+-*" "gourd", "*-*+-" "whoop", "*-*-*" "ranch", "-+*--" "truth", "++--+" "buyer", "+---*" "ranch", "--*+-" "dwarf", "--**-" "diner", "--*--" "droop", "-+++-" "total", "-+--*" "birch", "+--+-" "pubic", "*---*" "chirp", "---*+" "wordy", "-+-*-" "baggy", "---++" "rival", "-*--+" "utter", "-+-*+" "wound", "--+--" "hardy", "+-+-+" "verso", "*+--+" "sweep", "-++++" "motel", "*--+*" "smack", "+---+" "purer", "-+*+-" "graft", "+-+-*" "morph", "-+-+*" "earth", "*--*-" "ralph", "--*+*" "vegan", "---+*" "gland", "--*-+" "epoxy", "-++-+" "motor", "*+--*" "unzip", "**--*" "vigor", "-+---" "truth", "*+-+-" "split", "---+-" "brain", "*+*--" "churn", "**---" "prank", "+++--" "trash", "+--+*" "pulse", "---**" "aping", "*+---" "faith", "*--+-" "clink", "--+-+" "rocky", "-+*-*" "trove", "-++-*" "route", "++--*" "wrath", "+-*--" "rigid", "--++-" "local", "--+++" "mover", "+--++" "welsh", "**-*-" "still", "+-+--" "bacon", "*--**" "shale", "-+-++" "craft", "*--*+" "wimpy", "-+--+" "taint", "**--+" "drank", "----*" "guard", "+----" "champ", "--+*-" "dwarf", "***-*" "trunk", "***--" "murky", "----+" "cedar", "-----" "cramp", "---*-" "diary", "--*-*" "drank", "+-++-" "lousy", "-+-**" "blink", "++*--" "roost", "*-+--" "sonar", "+-*-*" "woman", "*-++-" "salvo", "++---" "dairy", "*---+" "preen", "-++--" "burnt",
;; turn 3
"----+-+--*" "unify"
})

(defn pick-guess [words]
(let [nwords (count words)
candidates (if (> 3 nwords) words dict)
comparator #(let [f (frequencies (for [word words] (game word %)))]
(- (* 100 (apply max (vals f))) (count f) (if (some #{%} words) 1 0)
(reduce (fn [a [k v]] (+ a (* (/ v nwords) (/ (Math/log (/ nwords v)) (Math/log 2))))) 0 f)))
counts (into {} (map (juxt identity comparator) candidates))]
(apply min-key counts candidates)))

(defn player [blackbox]
(loop [depth 1 history "" words dict]
(let [guess (or (lookup history) (pick-guess words))
feedback (blackbox guess)]
(println guess)
(println feedback)
(if (= feedback "*****") depth
(recur (inc depth) (str history feedback) (filter #(= feedback (game % guess)) words))))))


Player

Evaluator

## Strategy

Good heuristic rules behind picking the best next guess have already been discussed in the answers by Surculose Sputum and didgogns. However, any heuristics can still arrive quite far from the optimal solution, that's why it is always helpful to include some kind of more extensive evaluation of possible guesses, even if we don't undertake the daunting exercise of exhaustive search through all possible subtrees.

In this solution instead of fixing problematic cases in the deeper branches of the guessing tree, I decided to add an extensive enumeration step early in the process. In essence, this algorithm uses 2 predefined guesses instead of 1:

• For the 1st guess, the word stole was chosen as it produced the most promising results.
• For the 2nd guess, a (semi-)exhaustive enumeration was run. For any possible feedback from the game after the 1st guess that still leaves more than 2 valid secret candidates, further simulation was run with each of the top 200 words by heuristic score, and those that produced the best results were encoded in the lookup table used to pick the guess.
• 3rd & later guesses are normally picked using the heuristic. This procedure alone results in the overall score of (1 59 1051 1164 40), which at the time of writing, ties the best answer for the number of 5-guesses, but gets an edge in 4-guesses. Then, I went further into some worse-case branches and found a better guess in the 3rd turn that saves another 2 points. Other such improvements are likely possible.

## Heuristic score

Since the challenge asks to optimize for the worst case, the primary factor for picking the best guess should be the minimax - the least among the maximum numbers of remaining secrets in each group. For the tie breaker score, I tried throwing in a mix including:

• The count of different possible feedbacks from a guess
• An indicator, if the word is still valid as a guess itself
• The information gain from the guess (as explained in 3Blue1Brown video)

However, the exact definition of the score that will yield better overall results at this stage becomes pretty much hit or miss, so that performing more exhaustive search seems like a more promising direction for potential further improvement.

# JavaScript (Node.js)

## [ 1, 101, 650, 1000, 465, 87, 11 ]

A simple algorithm computing the list of remaining possible words and picking either the first one if there are less than 3 of them, or the one located at a precomputed index otherwise. (This is therefore playing in 'hard mode'.)

The precomputed values are based on a hash of the list of remaining words and were simply found with a naive random search running for a while. They are probably very far from optimal ones.

const GRAY    = 0;
const YELLOW  = 1;
const GREEN   = 2;

let wordList = require('fs').readFileSync(0).toString().split(' ');

let stat = [];

wordList.forEach(secret => {
let hist = solve(word => guess(word, secret)),
n = hist.length;

console.log('[' + secret + '] ' + hist.join(' '));
stat[n] = -~stat[n];
});

console.log(stat.slice(1));

function solve(blackBox) {
let list = [...wordList],
hist = [],
w, j;

for(j = 1;; j++) {
let key = list.join(''),
md5 = require('crypto').createHash('md5').update(key).digest('hex').slice(0, 8);

w = list[list.length < 3 ? 0 : LOOKUP[md5]];
hist.push(w);

let res = blackBox(w);

if(res.every(c => c == GREEN)) {
break;
}
list = filter(list, w, res);
}
return hist;
}

function filter(list, w, res) {
let cnt = {};
let exact = {};
res.map((c, i) => c == GRAY ? (cnt[w[i]] = ~~cnt[w[i]], exact[w[i]] = true) : cnt[w[i]] = -~cnt[w[i]]);
let pattern = RegExp(res.map((c, i) => c == GREEN ? w[i] : '[^' + w[i] + ']').join(''));
let newList = list.filter(word => pattern.test(word));

res.forEach((_, i) => {
if(cnt[w[i]] !== undefined) {
newList = newList.filter(word => {
let n = [...word].reduce((p, c) => p += c == w[i], 0);
return exact[w[i]] ? n == cnt[w[i]] : n >= cnt[w[i]];
});
}
});
return newList;
}

function guess(word, secret) {
let misplaced = {};

[...secret].forEach((c, i) => c != word[i] ? misplaced[c] = -~misplaced[c] : 0);

return [...word].map((c, i) => c == secret[i] ? GREEN : misplaced[c] ? (misplaced[c]--, YELLOW) : GRAY);
}


Try it online!

# Python

[1, 108, 696, 952, 436, 101, 17, 4]

Of course, the fact that there are 8 elements sucks, but I'll update the answer as I improve my algorithm.

Complete code, including scoring:

# Wordle challenge.

with open('words.txt', 'r') as wordsFile:

resultsDict = {} # dictionary format is easier, but then it will be converted to a tuple.

def best(pool): # it's a function that determines the word with the "most common" letters.
best_word = ''

for _ in range(5):
best_word += max('abcdefghijklmnopqrstuvwxyz', key=lambda letter: len([w for w in pool if w.startswith(best_word + letter)]))

return best_word

def get_feedback(guess, wo): # it's a function to give feedback.
return [
'LET' * (guessed in wo) + 'POS' * (guessed in wo and guessed == actual)
for guessed, actual in zip(guess, wo)
]

for word in words:
guesses = 0
cur_words = words

while True:
cur_guess = best(cur_words) # guess the best word.
feedback = get_feedback(cur_guess, word) # "word" is only accessed here. Nowhere else.
guesses += 1
if all([x == 'LETPOS' for x in feedback]): # mission accomplished
break

# set "cur_words" to a new set based on the feedback.

cur_words = [
w
for
w
in cur_words
if
all([w[i] == cur_guess[i] for i in range(5) if feedback[i] == 'LETPOS'])
and
all([cur_guess[i] in w and w[i] != cur_guess[i] for i in range(5) if feedback[i] == 'LET'])
and
all([cur_guess[i] not in w for i in range(5) if feedback[i] == ''])
]

if resultsDict.get(guesses):
resultsDict[guesses] += 1
else:
resultsDict[guesses] = 1

print(resultsDict, words.index(word))

resultsTuple = [resultsDict.get(i) or 0 for i in range(1, max(resultsDict.keys()) + 1)]
print(resultsTuple)


All I do here is pick the word with the most common letters each time. For instance, if there are 5 words:

abcde
abcfg
aedri
bbbbb
cdegh
`

It goes through the first letters: a, a, a, b, and c. It sees that a is the most common, so it starts with a. Its guess so far is: a

Same for the second letters: as it has isolated a as the first letter, it only considers b, b, and e. (of the first three words). It sees that b is more common, so it adds b. Its guess so far is: ab

Same for third letters: abc

Fourth letter: both d and f are equally common, so in picking the maximum it just chooses the first one: d

Now the only option is e, so its guess is abcde.