Lingo (word-game) guessing strategy

Question

My friend and I are kind of noobs in Python and are looking for ways to improve. We thought it would be cool if we could get some feedback on the following code. It is for a game named "Lingo", which is popular on TV in Europe.

Lingo is a popular word-guessing game show on television. The number of letters of a target word to be guessed is given, and often also the first letter. Players then make guesses subject to these restrictions (number of letters and possibly also first letter), and the game tells them which letters are correct and in the correct place, marked by a red square (X), and which letters are correct but not in the correct place, marked by a yellow circle (O). We do not use superfluous yellow circles, i.e. a letter is marked correct at most as often as it appears in the target word. If not all occurrences of the same letter can get a yellow circle this way, priority is given from left to right (but of course red squares have priority over yellow circles).

We wrote the following code with the following purpose:

First we needed to create a function compare that compares a guessed word with a target word. The two inputs are string of the same length that entirely consist of lowercase ASCII letters. The output is a string of the same length consisting of the symbols X, O and -, where X represent a red square, O represents a yellow circle and - represents nothing.

Examples:

compare("health", "teethe") must return "OX--O-",

compare("rhythm", "teethe") must return "---XX-",

compare("mutate", "teethe") must return "--O-OX",

compare("teethe", "mutate") must return "O--O-X",

Now we must solve for words of length-n, there are time constraints on how many steps it should take for our program to successfully find the right word, on average.

Constraints:

1. wordlist is a list of words (i.e. a list of strings that entirely consist of lowercase letters) you are allowed to guess. For example, all Dutch 7-letter words that start with "c".

2. 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. In any case, all words in targets are guaranteed to be in wordlist; you don't have to check this.

3. 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. Often this guess is in the target list, but it can sometimes be smart to guess a word that is not a possible target, because it has more possibilities to eliminate other words. To give an example, let dw5s be the list of all Dutch 5-letter words that start with an s.Then smart_guess(dw5s, dw5s) should return a good first word to guess. There are many good words to guess at this stage; an example of what this function could return is 'stoel'. If this guess has 'XO-OO' as compare result, then the target list is narrowed down to ['sealt', 'slegt', 'smelt', 'snelt', 'spelt'], meaning that these are the only possible words left based on our guess. If we now call smart_guess(dw5s, ['sealt', 'slegt', 'smelt', 'snelt','spelt']), we will get a smart guess for the new target list. A possible return value is 'slemp'. If this guess has 'XOX-O' as compare result, the target list will be narrowed down further to ['spelt']. So 'spelt' is the word to be guessed, and smart_guess(dw5s,['spelt']) should return 'spelt'.

○ For 5-letter words, the target must be guessed correctly within 4 turns on average.

○ For 6-letter words, the target must be guessed correctly within 3.5 turns on average.

○ And for 7- or 8- letter words, it must be guessed correctly within 3 turns on average.

4. Only imports from the standard library are allowed.

Another constraint:

If wordlist contains all Dutch words of a given length of at most 10 with a given starting letter (like in the TV show) and targets is any sublist thereof, the function call smart_guess(wordlist, targets) must finish within one second on a reasonably up-to-date computer. Again, timings will be tested on a 1.4 GHz i5 cpu, and you will have to adjust the timing requirement accordingly in case your computer speed differs wildly.

This is the wordlist we use: https://raw.githubusercontent.com/OpenTaal/opentaal-wordlist/master/wordlist.txt

import time
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)

english_words = load_words("words.txt")
dutch_words = load_words("wordlist.txt")

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)

def filter_targets(targets, guess_results):
    ''' Compare every result of targets with potential targets in wordlist and return list with potential answers '''
    end_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 end_targets  
        if temp_list == list(guess_results.values()):
            end_targets.append(target)
    return end_targets           

def distribution(guess, targets):
    ''' Return dictionairy with distribution of compared results, how good the guess is. '''
    distribution_dict = {}
    #Check how many times compared gives result
    for target in targets:
        result = compare(guess, target)
        if result not in list(distribution_dict.keys()):
            distribution_dict[result] = 1
        else:
            distribution_dict[result] += 1
                 
    return distribution_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(distribution(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
    
    #Need to find a way to pop these samples
    # samples = sample(targets, sample_size)
    samples = set([i for i in targets[0:sample_size]])
    #Pick 5 random items out of list
    # for _ in range(5):
    # random.shuffle(targets) 
    #     samples.append(targets.pop())
    
    ## NOT PERFECT YET, NEEDS TO POP ITEM
    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)
        if guess == str(guess):
            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, runs):
    n = len(target)
    wordlist = [w for w in wordlist if len(w) == n and w[0]==target[0]]
    targets = wordlist.copy()
    global average_time
    turns = 0
    while True:
        turns += 1
        if turns > 100:
            raise RuntimeError("This is going nowhere: 100 turns used.")
        t0 = time.time()
        guess = smart_guess(wordlist, targets)
        t1 = time.time()
        average_time += t1 - t0 
        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, runs)
    return total/runs

testcases = [4, 5, 6, 7, 8, 9, 10]
runs = 100
for item in testcases:
    print(f"Calculating {runs} runs for {item} letter words...")
    result = turn_count_simulation(item, dutch_words, runs)
    print(f"Averaged out at: {result}")
    print("Average time taken: ", average_time / runs)

We are looking for ways in which we can probabilistic optimize our code and we also wonder if we are better of using sets or lists on some occasions. We are open for any suggestions that improve the speed of our program, this has been a great learning experience but we find it very hard to arrive at new solutions independently after working on this problem for a few weeks.

Answer 1

compare

Your goal is to compare all possible guesses (the word list) against all possible target words, looking for the best distribution of results. With N words in the word list and M target words, you will be calling compare N*M times. This means you will want your compare function to be as efficient as possible.

You use result = list(target) to create your initial target list. The values in this list are never used; they are all replaced with an 'X', 'O' or '-'. Really, you just need a list of the desired length. result = ['-'] * len(target) gives you a list of the correct length pre-filled with incorrect guess markers.

Next, you loop over the letters in target, and call target.count(letter) for each one. This is inefficient. For each letter of target, you visit each letter of target to count occurrences of the current letter, which is an \$O(N^2)\$ operation. Additionally, if your target word teethe, you will be counting 't' twice, and 'e' 3 times, overwriting previous counts with the same value. Python has a convenient Counter class which allows you to count occurrences of each element of a sequence in a single pass, using a single statement: letter_dict = Counter(target)

Then, you look for letters which are correctly guessed in the proper spots. You use for idx in range(len(index_list)), which is a horrible construct. Anytime you see for idx in range(len(container)), and you access container[idx] in the body of the loop, it is time to use enumerate instead. In this case, you're looping over two containers in parallel, so you want to zip them together:

for idx, (guess_letter, target_letter) in enumerate(zip(guess, target)):

No more need for the slower guess[idx] and target[idx] indexing!

The letter_dict[guess[idx]] = letter_dict[guess[idx]] - 1 statement is inefficient, again doing the guess[idx] indexing two more times. Using guess_letter avoids that, letter_dict[guess_letter] = letter_dict[guess_letter] - 1, but this still leaves 2 indexings into letter_dict. We can reduce this to one: letter_dict[guess_letter] -= 1.

We can do similar modifications to the next loop which marks correctly guessed letters in the wrong positions.

The following is my cleanup of your compare() function. Additionally, I've added examples from the question to the """docstring""" as doctests, to verify the new version is working correctly:

from collections import Counter

def compare(guess: str, target: str) -> str:
    """
    Compare two words, marking an 'X' where a letter is in the correct
    place, and an 'O' where a correct letter is in the incorrect place.
    No superfluous marks are used.  I.e. a letter is marked correct at
    most as often as it appears in the target word.  If not all
    occurrences of the same letter can get 'O', priority is given from
    left to right (but of course 'X' ha psriority over 'O').

    >>> compare("health", "teethe")
    'OX--O-'

    >>> compare("rhythm", "teethe")
    '---XX-'

    >>> compare("mutate", "teethe")
    '--O-OX'

    >>> compare("teethe", "mutate")
    'O--O-X'
    """

    # Count occurences of letters in target word
    letter_count = Counter(target)

    # Initial result is no letter matches
    result = ['-'] * len(target)

    # Handle letters which are guessed in correct places
    for idx, (guess_letter, target_letter) in enumerate(zip(guess, target)):
        if guess_letter == target_letter:
            result[idx] = 'X'
            letter_count[target_letter] -= 1

    # Handle other correctly guessed letters in incorrect places
    for idx, (guess_letter, target_letter) in enumerate(zip(guess, target)):
        if guess_letter != target_letter and letter_count[guess_letter] > 0:
            result[idx] = 'O'
            letter_count[guess_letter] -= 1

    return "".join(result)
    

if __name__ == '__main__':
    import doctest

    doctest.testmod()

Exactly 3 passes have been made over the target word letters. The first time to count occurrences of each letter, the second to mark correct letters in the correct spot. The third pass only uses target_letter to find where guess_letter is incorrect, avoiding the need for constructing index_list and subsequently searching it to remove indices. letter_count[guess_letter] returns 0 for letters which did not exist in target, so there is no need to guard it with guess_letter in target.

filter_targets

All (both) calls to this function look like:

targets = filter_targets(targets, {guess: result})

A dictionary containing 1 key-value pairs is created and passed as the second argument.

In the function, the for guess in guess_results can only loop once, because the dictionary contains exactly one pair. Therefore, temp_list will only have one item added to it. list(guess_results.values()) will have one item in it because the dictionary only has one entry.

In short, the function can be simplified by taking the guess-result pair as two parameters instead of a dictionary:

def filter_targets(targets: list[str], guess: str, result: str) -> list[str]:
    '''...'''

    end_targets = []  
    for target in targets:
        if compare(guess, target) == result:
           end_targets.append(target)
    return end_targets           

or using list comprehension:

def filter_targets(targets: list[str], guess: str, result: str) -> list[str]:
    '''...'''

    return [target for target in targets if compare(guess, target) == result]

distribution

Again, using the Counter class, this code can be simplified to one-line:

def distribution(guess: str, targets: list[str]) -> Counter[str, int]:
    '''...'''
    return Counter(compare(guess, target) for target in targets)                 

There is absolutely no need for the list(...) call in result not in list(distribution_dict.keys()). That unnecessarily turns the dictionary key view into a list, which is just busy work, and results in a slower \$O(N)\$ search; testing result not in distribution_dict.keys() or simply result not in distribution is sufficient and a faster \$O(1)\$ test, but the Counter class makes even this test unnecessary.

smart_guess

Your "best guess" strategy computes the distribution of results of the target words for each guess in a sample set, determines the maximum frequency in each distribution, and selects the guess with the smallest maximum. This is a good approach. Let's see if we can make it better.

If you have 20 target words, the distribution for one guess might be "6, 4, 4, 3, 2, 1". The distribution for another guess might be "6, 3, 3, 2, 2, 2, 1, 1". Your strategy would categorize both these distributions with the same maximum value, 6, and not prefer one over the other. I think the second distribution is better, since the second most likely bin has 4 in the first distribution and 3 in the second distribution. You should prefer it. If the first bins are equal, and the second bins are equal, they you would compare the third bins. While that seems complicated, since Python sequences are compared in this exact fashion, this just becomes a sequence comparison. Eg)

>>> [6, 3, 3, 2, 2, 2, 1, 1] < [6, 4, 4, 3, 2, 1]
True

The Counter class has a most_common() method which will return the key-value pairs in order of decreasing frequency, so

biggest_value_in_distr = max(distribution(guess, targets).values())

could become

frequencies = [val for key, val in distribution(guess, targets).most_common()]

Initialize min_frequencies = [len(wordlist)], and test frequencies < min_frequencies in your search for the best_guess.

    min_frequencies = [len(wordlist)]
    for guess in samples:
        frequencies = [val for key, val in distribution(guess, targets).most_common()]
        if frequencies > min_frequencies:
            min_frequencies = frequencies
            best_guess = guess

Note: .most_common() takes an optional argument... the number of values to return. Instead of all bins, you could use the 5 most common or 10 most common. More values will give better results, but will be slower. Less values will be faster. Tune as desired. At the limit, .most_common(1) will effectively be the same as your max(...), so don't go below 2!

This searching a container for an item which gives the maximum or minimum value is a common operation. Python has build-in functions for it: max() and min(). When the item is used to produce another value which is what is needed for the maximum/minimum comparison, these functions take a key=... parameter to define the translation.

def smart_guess(wordlist: list[str], targets: list[str]) -> str:
    '''...'''

    # Nested function turning a guess into a distribution.
    # Note: uses `targets` from outer function
    def guess_value(guess: str) -> list[int]:
        return [val for _, val in distribution(guess, targets).most_common()]

    samples = sample_targets(targets)

    best_guess = min(samples, key=guess_value)

    return best_guess

Thinking of this another way, the first distribution has 6 possible results, where as the second distribution has 8. This makes the second distribution categorize the 20 target words into 8 categories, instead of 6. With the 20 target words separated into more categories, you would get better identification out of that guess.

def smart_guess(wordlist: list[str], targets: list[str]) -> str:
    '''...'''

    def guess_value(guess: str) -> int:
        return len(distribution(guess, targets))

    samples = sample_targets(targets)

    best_guess = max(samples, key=guess_value)

    return best_guess

Can we combine these two approaches? Select maximum distribution width, and then minimum distribution values? It is a little harder because we want to sort by maximize one quantity and minimizing another, but it can be done by negating that first value. The maximum distribution width produces the most negative value, so we want the minimum of the negative of the distribution width and the minimum distribution values ... and the min() function again works.

def smart_guess(wordlist: list[str], targets: list[str]) -> str:
    '''...'''

    def guess_value(guess: str) -> list[int]:
        distrib = distribution(guess, targets)
        frequencies = [val for _, val in distrib.most_common()]

        return [-len(distrib)] + frequencies

    samples = sample_targets(targets)

    best_guess = min(samples, key=guess_value)

    return best_guess

sample_targets

The above smart_guess function simplifications reveal a possible bug. The wordlist is not being used!

Often this guess is in the target list, but it can sometimes be smart to guess a word that is not a possible target, because it has more possibilities to eliminate other words.

samples = sample_targets(targets)

You are taking only the target words and creating a group of sample words. You aren't taking any from wordlist, as you describe as possibly useful in your problem description.

Perhaps you meant to also pass wordlist to sample_targets(...)???