For a school project I have to program a Wordle game. Now, I'm pretty much done with it, but there's still one requirement I need to complete. A certain function needs finish within 1 second, hoewever mine is taking nearly 6 seconds to finish. The function is called 'smart_guess', it takes two arguments: 'wordlist' and 'targets'. 'Wordlist' is a list of words you are allowed to guess. 'Targets' is a list of possible target words, based on previous guesses. When no guesses have been made yet, targets will be equal to wordlist. The return value is a word (i.e. string) that appears in wordlist. It is supposed to be a smart guess that helps to find the actual target in very few turns.
def smart_guess(wordlist, targets):
''' Returns best guess after comparing the distributions of each sampled guess '''
#Get randomized sample from targetlist
samples = sample_targets(targets)
#Get big number to start with
min_largest_value = len(wordlist)
best_guess = ""
#Iterate trough samples
for guess in samples:
#Find the biggest number in distribution
biggest_value_in_distr = max(distributions(guess, targets).values())
#Check if biggest number is the smallest of all, if so, add the guess to best_guess
if biggest_value_in_distr < min_largest_value:
min_largest_value = biggest_value_in_distr
best_guess = guess
if min_largest_value <= 2:
return best_guess
return best_guess
def sample_targets(targets):
#Get randomized sample from targetlist and add a total random word
len_word = len(targets[0])
decr = 10
if len_word == 4:
sample_size = 100
decr -= 1
if len_word == 5:
sample_size = 100
decr -= 1
if len_word == 6:
sample_size = len_word * decr
decr -= 1
if len_word == 7:
sample_size = 60
decr -= 1
if len_word == 8:
sample_size = len_word * decr
decr -= 1
if len_word == 9:
sample_size = 8
decr -= 1
if len_word == 10:
sample_size = 5
samples = set([i for i in targets[0:sample_size]])
samples.add(random.choice(targets))
samples.add(random.choice(targets))
samples.add(random.choice(targets))
return samples
This is the function I want to make run faster. And for it to be more clear, I'll add my whole program down here:
import random
def load_words(file):
result = set()
with open(file) as f:
for line in f.readlines():
word = line.strip().lower()
if word.isalpha() and word.isascii():
result.add(word)
return sorted(result)
def compare(guess, target):
''' Compare two words and give string with 'X' letter is in good place, 'O' not in good place but in word and '-': not in the word. '''
result = list(target)
index_list = list(range(len(guess)))
letter_dict = {}
for letter in target:
letter_dict[letter] = target.count(letter)
# Iterate list of indexes
for idx in range(len(index_list)):
# Look which letters are in good place
if guess[idx] == target[idx]:
# Decrease letter count
letter_dict[guess[idx]] = letter_dict[guess[idx]] - 1
# Delete index from list add 'X'
result[idx] = "X"
index_list.remove(idx)
for idx in index_list:
#Check if letter still is in letter_dict and in target
if guess[idx] in target and letter_dict[guess[idx]] > 0:
# Remove lettercount from dict
letter_dict[guess[idx]] = letter_dict[guess[idx]] - 1
# Add 'O' to place in guess_list
result[idx] = "O"
else:
result[idx] = "-"
return "".join(result)
dutch_words = load_words("wordlist.txt")
d6 = [word for word in dutch_words if len(word) == 6]
d6q = [word for word in d6 if word.startswith("q")]
def filter_targets(targets, guess_results):
final_targets = []
for target in targets:
#Create list with compared results
temp_list = []
for guess in guess_results:
temp_list.append(compare(guess, target))
#Compare results are the same, add to final_targets
if temp_list == list(guess_results.values()):
final_targets.append(target)
return final_targets
def distributions(guess, targets):
distr_dict = {}
#Check how many times compared gives result
for target in targets:
result = compare(guess, target)
if result not in list(distr_dict.keys()):
distr_dict[result] = 1
else:
distr_dict[result] += 1
return distr_dict
def smart_guess(wordlist, targets):
''' Returns best guess after comparing the distributions of each sampled guess '''
#Get randomized sample from targetlist
samples = sample_targets(targets)
#Get big number to start with
min_largest_value = len(wordlist)
best_guess = ""
#Iterate trough samples
for guess in samples:
#Find the biggest number in distribution
biggest_value_in_distr = max(distributions(guess, targets).values())
#Check if biggest number is the smallest of all, if so, add the guess to best_guess
if biggest_value_in_distr < min_largest_value:
min_largest_value = biggest_value_in_distr
best_guess = guess
if min_largest_value <= 2:
return best_guess
return best_guess
def sample_targets(targets):
#Get randomized sample from targetlist and add a total random word
len_word = len(targets[0])
decr = 10
if len_word == 4:
sample_size = 100
decr -= 1
if len_word == 5:
sample_size = 100
decr -= 1
if len_word == 6:
sample_size = len_word * decr
decr -= 1
if len_word == 7:
sample_size = 60
decr -= 1
if len_word == 8:
sample_size = len_word * decr
decr -= 1
if len_word == 9:
sample_size = 8
decr -= 1
if len_word == 10:
sample_size = 5
samples = set([i for i in targets[0:sample_size]])
samples.add(random.choice(targets))
samples.add(random.choice(targets))
samples.add(random.choice(targets))
return samples
def simulate_game(target, wordlist):
n = len(target)
wordlist = [w for w in wordlist if len(w) == n and w[0] == target[0]]
if target not in wordlist:
raise ValueError("Target is not in wordlist, thus impossible to guess.")
targets = wordlist.copy()
turns = 0
while True:
num_words = len(targets)
print(f"There {'is' if num_words==1 else 'are'} {num_words} possible"
f" target{'s' if num_words!=1 else ''} left.")
turns += 1
guess = smart_guess(wordlist, targets)
print("My guess is: ", guess.upper())
result = compare(guess, target)
print("Correctness: ", result)
if result == n * "X":
print(f"Target was guessed in {turns} "
f"turn{'s' if turns!=1 else ''}.")
break
else:
targets = filter_targets(targets, {guess: result})
def count_turns(target, wordlist):
n = len(target)
wordlist = [w for w in wordlist if len(w) == n and w[0]==target[0]]
targets = wordlist.copy()
turns = 0
while True:
turns += 1
if turns > 100:
raise RuntimeError("This is going nowhere: 100 turns used.")
guess = smart_guess(wordlist, targets)
result = compare(guess, target)
if result == n * "X":
break
else:
targets = filter_targets(targets, {guess: result})
return turns
def turn_count_simulation(word_length, wordlist, runs=100):
wordlist = [word for word in wordlist if len(word) == word_length]
total = 0
for _ in range(runs):
target = random.choice(wordlist)
total += count_turns(target, wordlist)
return total/runs
There are many steps to reducing runtime.
Step one: Make vars one liners.
Lets say I have
x=1andy=2. Instead of writing them on 2 lines you would dox,y=1,2.Step 2: Remove bool values in statements. Lets say I have a while statement,
while x == True:. I would replace this withwhile x:and if x is false then I would do,while not x:.Step 3: Make one liners. Python is slower when there are a lot of lines. We can remove about 40% of our lines by using one liners. Instead of doing something like
x+=1,y+=1. We can dox+=1; y+=1.Conclusion: There are many steps to optimize code in python, these are just three of them. I would recommend you research these three steps to get a general idea of how to implement them.