13
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ 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? \$\endgroup\$ Jan 14 at 16:04
  • \$\begingroup\$ @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.) \$\endgroup\$ Jan 14 at 16:14
  • \$\begingroup\$ Out of curiosity, why is the metric not "lowest total number of guesses"? \$\endgroup\$
    – Jonah
    Jan 15 at 5:52
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Jan 15 at 11:29
  • \$\begingroup\$ Does this answer your question? Build a Mastermind engine \$\endgroup\$
    – Fmbalbuena
    Jan 15 at 21:04
8
\$\begingroup\$

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.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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)]]) \$\endgroup\$ Jan 16 at 21:44
  • 1
    \$\begingroup\$ Oh, and of course best_guess = max(R, key=lambda t:t[1:]) ...Tiny TIO tinyurl.com/2p8v6zw6 \$\endgroup\$ Jan 16 at 21:57
  • 1
    \$\begingroup\$ 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? \$\endgroup\$
    – Kirill L.
    Jan 24 at 14:55
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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". \$\endgroup\$
    – A. Rex
    Jan 15 at 20:31
2
\$\begingroup\$

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;

const LOOKUP = {'14143202':1,'26364370':2,'30190943':3,'38882992':23,'43995839':2,'46997544':2,'47100915':2,'58773399':2,'70621541':3,'76111564':0,'78629445':0,'83279074':4,'53c11c74':2100,'921bd960':36,'2528c69d':1,'7964d0cf':11,'2e48ad14':2,'8b3ca4cb':0,'79c8a291':121,'8cf4eed6':3,'67c21ff2':1,'bc7835a4':33,'26270c62':16,'5095e262':0,'6fc77853':90,'aa78d00f':2,'efd5ee03':13,'f7e85504':0,'9ed6869a':13,'2f28d552':2,'ebadec4c':9,'dd657502':1,'75e99b72':9,'9e4d1e39':1,'6b1ee6bc':0,'94847f8e':2,'d69854c6':1,'79f08c51':29,'975ea22e':5,'74a4f766':4,'93913d7d':1,'f5a80453':3,'834b3950':10,'d311f685':3,'cf69c214':0,'3c1bb448':1,'eea7d694':7,'67980f55':2,'5bc6e50f':1,'b6a74c7f':1,'41086a3f':5,'c42acaa3':5,'f1ed7962':19,'f013f6de':1,'e2c19ca8':6,'bd62ab41':2,'31850f4c':14,'a65e6c62':1,'d8d65610':0,'0b60b7a3':7,'377f178d':1,'bed253cc':2,'55417f48':21,'2a195973':2,'89b99ca0':0,'5734ec44':1,'d994dab6':6,'747ac68c':1,'5cbfb6df':4,'6d145f3f':9,'cd7cd6dd':4,'ef04be81':2,'4332f7de':4,'9d0bdd07':1,'dc12394d':9,'90ae0678':2,'c76b85f1':4,'ec06d2ca':2,'c1c8a84f':10,'e8c899d1':0,'cc022066':14,'48f50318':3,'cac2bc3a':3,'e25292bb':1,'48a08d77':5,'14db746d':1,'f086993f':0,'5ce89220':9,'f9ad9ada':1,'229f8965':0,'0c4905a7':0,'0302235f':0,'96f622f5':0,'54252eab':2,'0c8e25a6':3,'9286bc52':3,'d2d53386':2,'c8f8fb4e':166,'702bb5a4':16,'38cbb5d6':0,'4474aa82':18,'d96b3f5d':28,'30ec466d':4,'8796640a':2,'5ccf8034':4,'f397de6b':18,'40ba7a83':38,'85ee6b8a':2,'1ee95569':0,'e6881291':1,'165b616c':0,'bb9a5866':0,'79fbfdcf':27,'b43dee5f':2,'50f28e4b':197,'f2ba2523':23,'fdef66e9':1,'e53b6fb5':1,'d6d16e7d':15,'708ab8ab':13,'c1214176':1,'453b0ab9':1,'bf525f76':6,'9baaa801':12,'99a34529':3,'e8cdc21c':1,'a1d69531':3,'43cb5c4e':4,'f2cc4081':3,'4497f9dd':3,'2c4dd2f4':3,'7f76ec38':1,'216cf28f':6,'427af08e':1,'5565ea4a':3,'ab97f7e6':5,'d621e228':2,'ac239f20':6,'ab593aad':1,'e1a6be75':0,'07a70237':1,'e5849d40':1,'0771e66f':0,'f0b2ccad':3,'5263f0b5':4,'dc007dc6':1,'8061bddc':2,'1b738423':7,'9c3c3eb4':3,'2c207b38':3,'1e560e0c':1,'9d483c9c':1,'a54ad297':3,'adf1e213':1,'8ece546f':0,'2868ded4':1,'0be47967':2,'76c48ab0':1,'ec5a2986':5,'08f02724':4,'2f1e8fe0':13,'61b01746':2,'a945af43':2,'b3298621':0,'c902c85d':0,'59b4b3a6':0,'65adc148':7,'da2d4f4f':1,'bdabc7b7':1,'363a673f':78,'57df5665':21,'4dff9da8':2,'0e86ae9c':7,'6c77953e':1,'714ca992':2,'32f55d3c':0,'8f730c78':4,'bef4237c':9,'0cd58e64':1,'9782b612':1,'46e616b4':5,'d8aea010':1,'9928cb50':12,'49a9a502':0,'899b630b':2,'e62dc0ee':0,'5e422bc1':1,'028f178c':1,'0d18106f':1,'73318b3f':1,'f99ae1c9':34,'e1cd8425':4,'4dfed81f':3,'add3dd22':10,'3b3db49a':0,'f1034ad7':2,'4a5046f3':1,'7ac5ce28':2,'28536ff5':0,'75ea6e53':1,'63fea0b1':2,'ab09cc25':2,'d6ceba64':2,'bfc4bed7':3,'960d9151':0,'cd868422':3,'11a4d91c':1,'83a7119c':0,'6c552bd4':0,'77095d30':10,'c8bcfcac':2,'ba21e593':0,'3d336693':5,'fba36a94':2,'10f9f1ed':2,'6204e786':0,'6e07f888':2,'2bb3482a':10,'d686a716':2,'e31d35d2':2,'dce35a86':0,'78d964ba':1,'851c0f3b':1,'37f4f3b4':2,'fe75e788':1,'93d09506':5,'604107e8':0,'44c077ae':13,'0f7f452d':1,'7c9bce8b':4,'7e6687c7':2,'7e58e0a8':5,'7dbabf3c':0,'65aec92b':74,'5b0b56f2':4,'ce548f7e':1,'f37040ba':0,'61a3de73':0,'6e752063':1,'f70d8eb1':0,'3855ec7a':4,'ec9b1d60':1,'a9de0559':2,'5db0cc60':3,'09ac011b':1,'06f2bd54':19,'c0abb288':1,'7740b151':8,'a2e3e28b':0,'f4c7948d':2,'dd7e56a0':2,'257e38eb':2,'8ec556e6':2,'fad4a8aa':2,'007da174':3,'48a5ee80':8,'daf0805d':1,'2c0bbd90':22,'a68704dd':2,'2edc16a2':0,'bdd7d751':1,'12fa8a9c':2,'bd6c82c1':5,'daa03ebb':2,'14a007cc':3,'b057a058':3,'fe2e6048':3,'930b8a67':2,'e6021a93':0,'715f9f50':2,'3bb3f9c8':2,'314ae620':2,'bf9d0ff9':3,'d6f78470':3,'6ffd5525':0,'bfa4d989':7,'2fcb4ed3':1,'8dff3605':2,'cc0e1441':2,'510e2239':2,'932cad71':4,'8a2babae':7,'b5069042':2,'870facb1':2,'81dc1545':2,'a366065a':2,'7f92a451':1,'17e04242':1,'00f397da':1,'5c792244':0,'d0bb4351':0,'98ffa283':3,'78bac9e6':2,'14f2bafd':0,'d086c2ee':2,'08a38507':0,'5fd0ea1d':3,'2ba1913e':0,'117654e7':1,'f5eea614':7,'b811e17b':1,'69dda9de':3,'46b94977':2,'7b766732':3,'af195935':2,'b1eb20d4':3,'8b66476e':2,'aa533625':0,'be9f3907':0,'743ce282':3,'02a97dc8':4,'42bec4ec':0,'5f8be41b':2,'4e053217':17,'efaf99ff':2,'558976a8':3,'f61dff94':2,'13784ef6':0,'05354011':0,'382e4364':1,'6f20b790':1,'e1b754bf':2,'c979fdaf':1,'ddd9b414':1,'2a2dddfc':3,'7f585610':2,'dc70293f':12,'7f328e23':2,'bbc51714':4,'d970cf9e':1,'f1db083f':3,'c698465c':1,'d67bb6a4':2,'6bf5c971':0,'a5dad7ee':3,'c20230d7':2,'6c69bcc4':2,'ddaa91fc':0,'aceffaa8':3,'5ac4f937':0,'fb589434':0,'e3f3c1d7':2,'062698f6':0,'67cff0e7':0,'2c367774':1,'5f163080':0,'c526fc35':0,'b77cce91':0,'f69aa500':2,'9f5bb9b2':1,'88c58554':2,'4524f59e':1,'d8d3541e':1,'c007c12f':0,'71a48e89':4,'897fcd24':0,'8f6a94fe':0,'4ab727d1':3,'95d7089e':0,'44b3c427':4,'689a27db':2,'42f43571':3,'b02a73cd':0,'c4310e8c':1,'e605072f':5,'cea8ea81':1,'072fdcc0':1,'bb4c095c':1,'bb6830d5':2,'ae22f8fb':1,'ffa4e084':1,'79aec494':2,'db71d0dc':2,'8f481b7a':4,'5e30001f':1,'0e114e8c':1,'6ecfeac0':0,'da3c8846':1,'bb77b1b0':1,'3d8d6830':3,'063be66d':0,'b07584b9':1,'e6aa8602':2,'00ee7c82':4,'8a0b3a9b':1,'fff50a02':2,'9522070e':2,'9fb93302':2,'f5c487bb':1,'f3becf6c':2,'7acd7d34':1,'e39973c9':0,'48a2f6d7':10,'c556b389':0,'aae28d8b':2,'26394f7b':2,'6987fcb5':1,'3c8b70b5':1,'0ec76191':3,'bede1e43':3,'e9e75a90':2,'93ecaaaf':7,'9c85d484':0,'6cfc5c54':4,'0e956f0c':0,'e0ee2ae6':2,'ae37d2b7':6,'e7356cc4':1,'191bee62':4,'34ac52df':2,'edf40c22':1,'a3c46eae':1,'07c59ea8':0,'cebc4b79':2,'b83825b1':4,'967d3108':2,'52674dd2':1,'ad289b28':0,'671ce983':5,'3f340614':1,'99027f41':4,'96da67b7':0,'4a8871e3':0};

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!

\$\endgroup\$
1
\$\begingroup\$

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:
    words = wordsFile.read().split('\n')

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.