Is there any way to more efficiently check if all the letters in a word are in a list?

user_13034360 0
Viewed 188

For a research paper, I am simulating rounds of the Channel 4 Program Countdown's letters round. Essentially, a board of 9 random letters are put up, and players must try and find words made up of the letters given of as high length as they can.

I'm currently using the code:

for word in sowpods:
        testboard = list(board)
        count = 0
        for letter in word:
            if letter in testboard:
                testboard.remove(letter)
                count += 1
        if len(word) == count:
            length.append(len(word))
    if len(length) == 0:
        return 0
    return max(length)

to create a list of dictionary words (a SOWPODS .txt file imported into the kernel) that can be created from the board, and then returning the longest word possible for statistical analysis (this is part of a function that simulates a round of Countdown). But, from what I can imagine is due to the repeated for loops, if statements and list edits, this is extremely slow when scaled up to larger samples of 500 or so boards. Is there a more efficient way to check if a word can be created from the board?

I tried using sets; my original test was:

set(word) <= set(board)

but this method ignored repeats, so for example if the board was [a, e, h, s, l,..) it would count "Hassle" as a possible word despite only one S being available. Ideally I'd love a datatype halfway between a list and a set, where order doesn't matter but number of the same element does, but that doesn't seem to exist.

python-3.x python
3 Answers

One speed-up you can implement is to reorganizer the logic so that the letter-by-letter loop ends the moment a non-matching letter is encountered. This will speed up your code, on average, in direct proportion to the number of letters not allowed. 

def wordsearch(board, sowpods):
    length = []
    for word in sowpods:
        testboard = list(board)
        count = 0
        for letter in word:
            if letter in testboard:
                testboard.remove(letter)
                count += 1
        if len(word) == count:
            length.append(len(word))
    if len(length) == 0:
        return 0
    return max(length)

def find_matches(allowed, dictionary):
    allowed_list = list(allowed)
    match_words = []
    for word in dictionary:    
        good = True
        for letter in word:
            if letter not in allowed_list:
                good = False
                break
        if good == True:
            match_words.append(len(word))    
    return max(match_words)

import timeit
start_time = timeit.default_timer()
allowed = 'iptneazol'
result = wordsearch(allowed, sb_list)
# code you want to evaluate
elapsed = timeit.default_timer() - start_time
print(elapsed)
>>>0.6867701730000135

start_time = timeit.default_timer()
allowed = 'iptneazol'
result = find_matches(allowed, sb_list)
elapsed = timeit.default_timer() - start_time
print(elapsed)
>>>0.10806877499999246

This also solves the issue of an allowed letter appearing twice since the code does not transform the allowed list. For even more efficiency, you could rewrite the for loops as list comprehensions that call service functions, or use iterators/generators.

user_45519450

a datatype halfway between a list and a set, where order doesn't matter but number of the same element does

collections.Counter does what you want. You'll have to implement the comparison logic yourself, though.

user_5236120

I felt bad that my Counter solution ended up being a lot slower than I thought, so I took your updated code and sped it up a bit:

def check_board(sowpods, board):
    length = []
    board = list(board)  # only perform once
    for word in sowpods:
        if len(word) > len(board):
            continue  # short circuit when too long
        on_board = True
        testboard = board.copy()  # our temp board
        for letter in word:
            if letter not in testboard:
                on_board = False
                break
            else:
                testboard.remove(letter)
        if on_board:
            length.append(len(word))
    return max(length)

Testing speed with board = 'eoamctcwy'.upper(), we have:

  • Your original code:

    # 398 ms ± 40.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

  • Your updated code:

    # 185 ms ± 24 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

  • This code:

    # 83.4 ms ± 2.99 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

The short circuit avoids checking letters for words that you know are too long to fit on the board. This will have diminishing returns if you use larger boards, and you won't see any effect from it if you use a board as large as the largest words in the dictionary.

By avoiding creating a list every iteration, you basically avoid some overhead and save a few milliseconds. Apparently list.copy() is faster than building a list from data, or at least it was on my machine when I tested with and without that change.

I also tried replacing the list for length with length = 0 and just update it to max(length, len(word)) when appropriate, but that didn't seem to save any time.

user_24645970
Related