At the time of writing, the game Wordle is taking the world by storm. Quite rightly, it's genius and so is the guy who invented it.
Here's one I did earlier:
Two things to know about me:
- I'm rubbish with word games.
- I like to trick my children into thinking I'm cleverer than I am.
So having struggled a bit with Wordle I wondered if I could write some code to more efficiently (for that read cheat) find Wordle answers. For this I used my trusty Raspberry Pi, Python and the Natural Language ToolKit (NLTK) module. I'd used NLTK previously for some online data science courses so I knew it could give me a "corpus" (so set) of words to play with.
First I installed NLTK for use with Python 3 on the Raspberry Pi using this command: sudo pip3 install nltk
Then I looked at which word corpus NLTK has that I could use. There's some details here and a few places pointed me to the "Brown" corpus as a good place to start. To make this corpus available for NLTK in a Python script I opened a Python3 shell and ran these commands:
Python 3.7.3 (default, Jan 22 2021, 20:04:44)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import nltk
>>> nltk.download('brown')
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import nltk
>>> nltk.download('brown')
So that sets a corpus of words ready to use in a Python script. I won't go into the detail of how Wordle is played but overall you get 6 goes to guess a 5 letter word. With each guess, the game tells you for each letter:
- Whether it is in the final word in the exact position you guessed it it, I call these exact matches.
- Whether it is in the final word but not in the exact position you guessed it in. I call these partial matches.
- Whether it is not in the final word. I call these non-matches.
I then played around with snippets of code to examine words from the corpus and rule them in or out based upon whether they had exact matches in them or non-matches not in them. That led me overall to an algorithm of:
-Load word corpuses (at the time of writing I use Brown, Webtext and Gutenberg)
-Build a dictionary of 5 letter words and their frequency of occurrence in the corpus
-Setup data structures to log exact, partial and non-matches.
-Loop at least six times doing:
1-Make a prediction (which I then enter into Wordle) based on the data structures2-Input the result of the prediction from Wordle3-Update some data structures
(Full code is at the end of this post)
Taking step 2 above first, I simply enter the result of each Wordle round in a coded string. So take this result:
I enter this as S_E,U_N,G_N,A_P,R_P. Where _E is for exact, _N is for non-matched and _P is for partial.
Looking at step 3, I update 3 data structures based upon the input the user provides. The data structures are:
- A tuple of exact matches where the tuple contains the letter and the exact match position. So from the above it would be [('S', 0)].
- A dictionary of partial matches where the key is the letter and the value is a list of positions that the letter is not in. S from the above it would be {'A': [3], 'R': [4]}
- A list of non-matches. So from the above it would be ['U', 'G']
If it's an exact match I do two things:
1)Update the tuple of exact matches with the new matched letter/position combination.
2)Update the partial match dictionary as this is a a)new position a partial matched letter can't be in and b)it may require removal of an entry as what was previously partially matched is now fully matched.
If it's a partial match I do two things:
1)Add a new partial (with the letter position) or update the list of positions for an existing partial
2)If it's a new partial, don't just add the position it is in, add the position of all the other exact matches as the letter can't be in this position either.
If it's a non-match I just add the letter to the list of non-matches.
So for game above, the log output showed this:
Enter the result of that round in format A_E,B_P,C_N where _E for exact, _P for partial, _N for non matched:S_E,U_N,G_N,A_P,R_P
########Processing an exact match for letter S
########Processing a non match for letter U
########Processing a non match for letter G
########Processing a partial match for letter A
########Processing a partial match for letter R
########Exact matches [('S', 0)]
########Partial matches {'A': [0, 1, 3], 'R': [1, 2, 4]}
########Non matches ['O', 'E', 'P', 'T', 'U', 'G']
Finally looking at step 1, for round 1 I recommend a initial word based upon the following logic:
1)Do a letter frequency count across all the 5 letter words in the corpus.
2)Find a word in the corpus that has each of the 5 most common letters. This leads me to use "AROSE".
2)Find a word in the corpus that has each of the 5 most common letters. This leads me to use "AROSE".
Then for subsequent rounds I do the following:
1)Eliminate any words from the corpus that have the letters in the non-matching list.
2)Eliminate any words from the corpus that don't have the exact matching letters in the exact matching position.
3)Eliminate any words from corpus that don't have the partial matching letters or, if they do, have the partial matching letters in the positions logged that they can't be in.
...which results in a list of words which I augment with the frequency of occurrence in the corpus. I then print this and let the use choose the word to enter next.
The story so far is that I have played 4 games with this code and:
1)I have got the right answer every time, but
2)My 17 year old daughter has got the right answer in fewer guesses 3 times out of 4!
Full code listing:
#!/usr/bin/env python3
from nltk.corpus import brown
from nltk.corpus import webtext
from nltk.corpus import gutenberg
import sys
#Our main 5 letter word list
five_letters = {} #A dictionary of 5 letter words with frequencies
#Gets a list of 5 letter words
def add_to_list(in_word_list):
for word in in_word_list:
if word.isalpha():
if len(word) == 5:
if word.upper() not in five_letters: #as variety of case of same word could be present
five_letters[word.upper()] = 1
else:
five_letters[word.upper()] += 1
#Compares our 5 letter word corpus with the list of letter frequencies to find the best start word
#The best word has all the highest frequency letters just once
def get_start_words(letter_frequencies, start_pos):
words_found = 0 #Counts when our set of 5 high frequency letters matches a word from our corpus
list_start_pos = start_pos #Used to track where we are in our letter frequency list
word_list = []
#Loop until we've found words from the word corpus or we've exhausted the
while words_found == 0 and list_start_pos < 22: #It's 22 as this will mean we've got to positions 21,22,23,24,25 in the character frequency list
#Loop for each of the words in the corpus
for my_word in five_letters:
letter_count = 0 #Incremented if we find a letter in the word
#Then for each of the five letters identified by the outer while loop
for i in range (list_start_pos, list_start_pos + 5):
my_letter = letter_frequencies[i][0]
if my_letter in my_word:
letter_count += 1 #Count if the letter is in the word
#return word_list
#See if we found all our letters in the word. So if one letter is there twice we should not
if letter_count == 5:
word_list.append(my_word)
words_found += 1
list_start_pos += 1
#Return our word list
return word_list
print ("########Building five letter word list")
add_to_list(brown.words())
print ("Added Brown corpus and word list has {} entries".format(len(five_letters)))
add_to_list(webtext.words())
print ("Added Webtext corpus and word list has {} entries".format(len(five_letters)))
add_to_list(gutenberg.words())
print ("Added Gutenberg corpus and word list has {} entries".format(len(five_letters)))
#Calculate letter frequencies
print ("########Calculating letter frequencies")
freq_dict = {}
for my_word in five_letters:
#Build letter frequencies
for my_letter in my_word:
#See of the letter is a key in the dictionary
if my_letter in freq_dict.keys():
freq_dict[my_letter] += 1 #Increment value
else:
freq_dict[my_letter] = 1 #Add value
#Sort the dictionary to get the highest probability letters and show the user
sorted_values = sorted(freq_dict.items(), key=lambda x:x[1], reverse=True)
print (sorted_values)
#Holds the round number
round_number = 1
#Holds the exact matches. A list of tuples
exact_matches = []
#Holds the partial matches. A dictionary of key is letter, value is list of positions letter is not in
partial_matches = {}
#Holds the non-matched letters. A list
non_matches = []
#Loop for all the rounds
while round_number < 7 and len(exact_matches) < 5:
print ("######################################################")
print ("########This is round number {}".format(round_number))
#Special case for round 1
if round_number == 1:
#Get a list of possible starting words based upon the letter frequencies
print ("########Getting a list of words to start off with")
#Imagine we get 6 wrong starting words! Accoutn for each
for k in range (0,3):
start_words = get_start_words(sorted_values, k)
print ("Where we start at position {} of the letter frequencies the start words are: {}".format(k, start_words))
else:
#Step 1, rule out a bunch of words that have eliminated letters in them
print ("########Assessing data from previous round to make a recommendation")
print ("########First rule out words based on letters found not to exist in the answer")
after_non_match_check = []
for my_word in five_letters:
has_ruled_out = False
for letter in non_matches:
if letter in my_word:
has_ruled_out = True
if not has_ruled_out:
after_non_match_check.append(my_word)
print ("########At the end of this we are down to {} words".format(len(after_non_match_check)))
#Step 2, rule in a set of words based on the matched list
print ("########Second rule in words based on exact matched letters")
after_full_match_check = []
for my_word in after_non_match_check:
has_ruled_out = False
for match_tuple in exact_matches:
if my_word[match_tuple[1]] != match_tuple[0]:
has_ruled_out = True
if not has_ruled_out:
after_full_match_check.append(my_word)
print ("########At the end of this we are down to {} words".format(len(after_full_match_check)))
#print (after_full_match_check)
#Step 3, rule out a set of words where letters are in partial match positions
print ("########Third rule in words based on partial matched letters")
after_partial_match_check = []
for my_word in after_full_match_check:
has_ruled_out = False
for my_partial in partial_matches: #Loop through each dictionary entry
#First simply check the partial is in the word
if my_partial in my_word:
#Now check for the partial positions
for my_partial_pos in partial_matches[my_partial]: #Loop through each item in the partial match
if my_partial == my_word[my_partial_pos]:
has_ruled_out = True
else:
has_ruled_out = True
if not has_ruled_out:
after_partial_match_check.append(my_word)
print ("########At the end of this we are down to {} words. Recommendation:".format(len(after_partial_match_check)))
#Form an ordered list of words based on overall word frequency from the corpus that was built right at the start
suggestion_dict = {}
ordered_suggestion = {}
for word_suggestion in after_partial_match_check:
suggestion_dict[word_suggestion] = five_letters[word_suggestion]
#Order the suggestions
ordered_suggestion = sorted(suggestion_dict.items(), key=lambda x:x[1], reverse=True)
#Tell the user
if len(ordered_suggestion) < 11:
print (ordered_suggestion)
else:
#Print just the first 10
print (list(ordered_suggestion)[:10])
#Get input from the user as to what happened in that round
round_result = input("Enter the result of that round in format A_E,B_P,C_N where _E for exact, _P for partial, _N for non matched:")
#Pull round result apart and process each
result_list = round_result.split(",")
#Loop for each result
letter_pos = 0 #Holds which letter result position we're looking at
for result in result_list:
#Get the entered letter and the result
entered_letter = result[0]
letter_result = result[2]
if letter_result == "E":
print("########Processing an exact match for letter {}".format(entered_letter))
#See if we already have this exact match. If not, add it
letter_found = False
for my_tuple in exact_matches:
if my_tuple[0] == entered_letter and my_tuple[1] == letter_pos: #So we could have double letters so this checks for existence of the letter in the given position
letter_found = True
if not letter_found:
exact_matches.append((entered_letter,letter_pos))
#Update existing partial matches as well, i.e. 1)They can't be in the position of the found letter. Also, if there is already a partial for what is now exact, remove it
if entered_letter in partial_matches:
partial_matches.pop(entered_letter)
else:
for partial in partial_matches:
if letter_pos not in partial_matches[partial]:
partial_matches[partial].append(letter_pos)
elif letter_result == "P":
print("########Processing a partial match for letter {}".format(entered_letter))
if entered_letter in partial_matches:
#Look partial record, seeing if the current position is in the position list. If not, add it
if letter_pos not in partial_matches[entered_letter]:
partial_matches[entered_letter].append(letter_pos)
else:
#Entered letter not in partial matches dictionary. Add it together with the position
partial_list = []
partial_list.append(letter_pos)
#But as this is a new partial we also need to add all existing exact matches which the letter can also not be in that position
for exact in exact_matches:
partial_list.append(exact[1])
#FInal update of the partial list
partial_matches[entered_letter] = partial_list
elif letter_result == "N":
print("########Processing a non match for letter {}".format(entered_letter))
#See if we already have this non-match. If not, add it
if entered_letter not in non_matches:
non_matches.append(entered_letter)
#Update so we get the next letter position
letter_pos +=1
#Show what the structures are at the end of this round
print ("########Exact matches {}".format(exact_matches))
print ("########Partial matches {}".format(partial_matches))
print ("########Non matches {}".format(non_matches))
#End of turn Update for next loop
round_number += 1
#See how we came out of the main loop
if len(exact_matches) == 5:
print ("########You won! Way to go/cheat")
else:
print ("########All rounds completed, you lost!")
