Find all words that satisfy unknown letters (Hangman)

Question

I have been working on a function which might be used to solve a word game like Hangman or "Wheel of Fortune".

Basically, I wish to search from a very large WORD_LIST (>1 million unique entries) for any word which satisfies the provided letters in the word search.

An example of this might be if search is "A??LE", the resulting list will contain apple, ankle, ...

But that technically, if a letter is already provided/revealed, then it cannot also be one of the blanks eg; search= "HANG???" might return hangout, hangers but not hangman because the A/N has already been guessed.

Mainly I'm wondering if the string search speed can be increased, or if a more elegant (RegEx?) method of searching might give me faster results without losing accuracy.

def words_like(search, without_letters='', preclude_revealed_letters=True):
    if len(search) < 1:
        return []

    search = search.lower()
    without_letters = without_letters.lower()
    # Find indices of letters and blanks
    letters = [i for i, x in enumerate(list(search)) if x != "?"]
    blanks = [i for i, x in enumerate(list(search)) if x == "?"]

    if preclude_revealed_letters:
        # If a letter has been revealed, it can't also be one of the blanks
        without_letters = set(without_letters+''.join([x for x in search if x != "?"]))

    # Search our word-list for all matching "revealed" letters
    possible_words = []

    for w in WORD_LIST:
        if len(w) != len(search):
            continue
        for i in letters:
            if search[i] != w[i]:
                break
        else:
            possible_words.append(w)
    # Then remove all that use forbidden letters in the blanks
    without_possibles = []

    for w in possible_words:
        for i in blanks:
            if w[i] in without_letters:
                break
        else:
            without_possibles.append(w)
    return without_possibles

Answer 1

The solution would indeed be much simpler using regular expressions. The trick is to build the regular expression dynamically, using a negated character class like [^unwanted] to represent any character other than u, n, w, a, n, t, e, or d.

I'd suggest writing this function to return a generator expression, such that it yields matching words from WORD_LIST as it finds them, rather than waiting until all of the processing is complete.

import re

def words_like(search, without_letters='', preclude_revealed_letters=True):
    forbidden_letters = set(without_letters)
    if preclude_revealed_letters:
        forbidden_letters.update(c for c in search if c != '?')
    regex = re.compile(
        search.replace('?', '[^' + ''.join(forbidden_letters) + ']'),
        re.IGNORECASE
    )
    return filter(regex.fullmatch, WORD_LIST)

This assumes that search consists only of letters and question marks, and contains no regex metacharacters such as ..

(Note that regex.fullmatch() was added in Python 3.4. For earlier versions of Python, use regex.match, and append a $ to the regex.)

Answer 2

If you are trying to speed up the search your main objective should be to remove the cycle for w in WORD_LIST:. To do so I would simply build a trie from WORD_LIST. Then your code should just be implementing a special search over that trie. Build the set without_letters with all the letters already in search. And then search the trie with the following rules:

• If search[i] is a letter you simply move down on the trie on the path matching search[i], i.e. a normal trie search.
• If search[i] is ? you move down every path not matching a letter in without_letters.

When you reach the end of search in every path you followed you would be in a node representing a matching word, you just have to put all these matching words together and you are done.

Obviously, this has a huge upfront cost, building that trie is not cheap in time nor memory, so this only makes sense if you are doing multiple searches over the same list.

Answer 3

This is pretty much @jesm00 excellent suggestion.

Code

You create a Trie first:

def create_trie(words):
    root = {}
    for word in words:
        curr_node = root
        for letter in word:
            curr_node = curr_node.setdefault(letter, {})
        curr_node.setdefault('', True)
    return root

with open('/usr/share/dict/american-english') as wordbook:
    words = [word.strip().upper() for word in wordbook]

TRIE = create_trie(words)

And just parse it recursively to get the results directly as a generator:

def words_like(pattern, trie=TRIE, already_taken=None, temp=''):
    pattern = pattern.upper()
    if not already_taken:
        already_taken = {letter for letter in pattern if letter != '?'}
        already_taken.add('')
    if pattern:
        letter = pattern[0]
        if letter == '?':
            for node in trie:
                if node not in already_taken:
                    yield from words_like(pattern[1:], trie[node],
                                          already_taken, temp + node)
        else:
            yield from words_like(pattern[1:], trie.get(letter, {}),
                                  already_taken, temp + letter)
    else:
        if trie.get(''):
            yield temp

print(list(words_like('A??LE')))
# ['AISLE', 'AGILE', 'ADDLE', 'AMPLE', 'AMBLE', 'APPLE', 'ANKLE', 'ANGLE']
print(list(words_like('HANG???')))
# ['HANGERS', 'HANGOUT']

Performance

The first part will be slow (300ms on my laptop). It doesn't depend on the pattern, so you could calculate it once and cache it with pickle or JSON. pickle.loads(dumped_trie) took less than 100ms.

The second part is really fast though. For 'HANG???', the trie version is more than 1500 times faster than @200_success' code (40 µs vs 68 ms). The trie code gets a bit slower with more ? placeholders, it's always a few orders of magnitude faster than the other answers, though.

Answer 4

One thing to think about is what is being run how many times. That depends somewhat on the use case. No matter what, you're performing the len(w) != len(search) check every time you run this function. Instead, you can just separate the words by length up front; create a dictionary where keys are integers and the values are lists of words of that length. The next question is whether you envision this function being run once for a puzzle, or repeatedly every time a new letter is guessed. If the latter, @200_success 's answer will be recreating regexes for each letter that are only slightly different from the previous letter, when you only need to check the new letter. So suppose you have a function get_positions that returns a list that is empty if the puzzle is finished, otherwise the first entry is the last letter guessed, and the second entry is the positions that letter appeared (if the letter didn't appear, then the list is empty).

while True:
    new_positions = get_positions()
    if new_positions == []:
        break
    new_letter = new_positions[0]
    positions = new_positions[1]
    new_word_list = [word for word in old_word_list if
                     all([(word[i]==new_letter)==(i in positions) 
                     for i in range(len(word))])
                     ]
    old_word_list = new_word_list

You could also try a regex to create new_word_list and see whether it's faster.

If you want to run this just once per puzzle, you could just iterate through letters, but that likely wouldn't be optimal.

Answer 5

Ok,

I am not sure if this would faster or not, but I have a non-regular expression based solution, which tends to find all the possible combinations and then checks if they are in WORDLIST.

Why I think it might be faster is because searches on WORDLIST are done as a set search, which I expect to be faster than a regex search.

This is how this it would go:

import itertools
import string
import gzip

WORDLIST = set([x.upper().strip() for x in gzip.open("words.txt.gz").readlines()])

def grouper(iterable, n):
    while True:
        yield itertools.chain([iterable.next()], itertools.islice(iterable, n-1))

def words_like(search, preclude_revealed_letters=True):
    max_members_memory = 100000
    search = search.upper()
    if preclude_revealed_letters:
        options = list(set(string.ascii_uppercase).difference(set(list(search))))
    else:
        options = string.ascii_uppercase

    search = map(lambda x:x if x!= "?" else options, list(search))

    real_words = []

    for x in grouper(itertools.imap("".join, itertools.product(*search)), max_members_memory):
        real_words.extend(list(WORDLIST.intersection(set(x))))

    return real_words

print words_like("HA??????")

With my WORDLIST, this produces (1min:56sec):

[
 'HACKBUTS', 'HACKBOLT', 'HACKNEYS', 'HACKLIER', 'HACKLING', 'HACKLERS', 'HACKSTER', 'HACKTREE', 'HACKWOOD', 'HACKWORK', 'HABENDUM', 'HABILITY', 'HABITUDE', 'HABITURE', 'HABITING', 'HABITUES', 'HABSBURG', 'HABROWNE', 'HAEMOPOD', 'HAEREDES', 'HADDOCKS', 'HADFIELD', 'HADRONIC', 'HAGBERRY', 'HAGECIUS', 'HAGGERTY', 'HAGGISES', 'HAGGLING', 'HAGGLERS', 'HAGSTROM', 'HAGSTONE', 'HAGRIDER', 'HAGRIDES', 'HAGUETON', 'HAFFLINS', 'HAFNIUMS', 'HAFTOROT', 'HAILWEED', 'HAILWOOD', 'HAIRCUTS', 'HAIRBELL', 'HAIRGRIP', 'HAIRIEST', 'HAIRBIRD', 'HAIRPINS', 'HAIRLINE', 'HAIRLIKE', 'HAIRLOCK',
 'HAIRNETS', 'HAIRLESS', 'HAIRWORK', 'HAIRWEED', 'HAIRWORM', 'HAIRWOOD', 'HAMBONED', 'HAMBONES', 'HAMBURGS', 'HAMETUGS', 'HAMFORRD', 'HAMIFORM', 'HAMILTON', 'HAMITISM', 'HAMITOID', 'HAMMERER', 'HAMMERED', 'HAMMIEST', 'HAMMOCKS', 'HAMLETED', 'HAMPERED', 'HAMPERER', 'HAMSTERS', 'HAMULOUS', 'HAMULOSE', 'HALCYONE', 'HALCYONS', 'HALBERTS', 'HALBERDS', 'HALECRET', 'HALENESS', 'HALESOME', 'HALEWEED', 'HALFCOCK', 'HALFLIFE', 'HALFNESS', 'HALFLING', 'HALFMOON', 'HALFUNGS', 'HALFTIME', 'HALFWORD', 'HALFWISE', 'HALFTONE', 'HALIBUTS', 'HALICORE', 'HALIDOMS', 'HALIDOME', 'HALIBIOS', 'HALIMOUS', 'HALIOTIS', 'HALINOUS', 'HALIPLID', 'HALLCIST', 'HALLETTE', 'HALLMOTE', 'HALLMOOT', 'HALLICET', 'HALLOING', 'HALLTOWN', 'HALLOWER', 'HALLOOED', 'HALLROOM', 'HALLOWED', 'HALLUCES', 'HALLOPUS', 'HALOBIOS', 'HALLWOOD', 'HALOGENS', 'HALOSERE', 'HALOLIKE', 'HALOXENE', 'HALUCKET',
 'HALUTZIM', 'HALTERED', 'HALTERES', 'HALTLESS', 'HANDBILL', 'HANDBOLT', 'HANDEDLY', 'HANDCUFF', 'HANDBOOK', 'HANDBELL', 'HANDBLOW', 'HANDLOOM', 'HANDLINE', 'HANDGRIP', 'HANDLESS', 'HANDLERS', 'HANDGUNS', 'HANDLIKE', 'HANDIEST', 'HANDLOCK', 'HANDLING', 'HANDIRON', 'HANDLIST', 'HANDFEED', 'HANDFULS', 'HANDOUTS', 'HANDPICK', 'HANDREST', 'HANDSFUL', 'HANDSEWN', 'HANDSLED', 'HANDSPEC', 'HANDPOST', 'HANDSELS', 'HANDSETS', 'HANDOFFS', 'HANDSOME', 'HANDYMEN', 'HANGBIRD', 'HANDWORM', 'HANDWORK', 'HANDWRIT', 'HANGDOGS', 'HANGINGS', 'HANGFIRE', 'HANGMENT', 'HANGOVER', 'HANGNEST', 'HANGOUTS', 'HANGWORM', 'HANFORRD', 'HANIFISM', 'HANIFITE', 'HANKERER', 'HANKERED', 'HANKSITE', 'HANNOVER', 'HANSBORO', 'HANSELED', 'HANSFORD', 'HANSTEEN', 'HANZELIN', 'HAQUEBUT', 'HAQUETON', 'HAPLITIC', 'HAPLITES', 'HAPLOIDY', 'HAPLOSES', 'HAPLONTS', 'HAPLODON', 'HAPLOIDS', 'HAPLOSIS', 'HAPLOMID', 'HAPPENED', 'HAPPIEST', 'HAPSBURG', 'HAPTENIC', 'HAPTENES', 
 'HAPTERON', 'HASIDISM', 'HASKNESS', 'HASKWORT', 'HASPICOL', 'HASPLING', 'HASSOCKS', 'HASSOCKY', 'HASSLING', 'HASTENER', 'HASTENED', 'HASTIEST', 'HASTIFLY', 'HASTEFUL', 'HASTINGS', 'HARCOURT', 'HARBESON', 'HARBINGE', 'HARBOURS', 'HARBORER', 'HARBISON', 'HARBORED', 'HAREBELL', 'HAREMISM', 'HAREMLIK', 'HAREFOOT', 'HARELIPS', 'HARELIKE', 'HAREWOOD', 'HARDIEST', 'HARDBOOT', 'HARDCOPY', 'HARDESTY', 'HARDENER', 'HARDEDGE', 'HARDENED', 'HARDCORE', 'HARDFERN', 'HARDFIST', 'HARDNOSE', 'HARDLINE', 'HARDNESS', 'HARDWEED', 'HARDWICK', 'HARDTNER', 'HARDWOOD', 'HARDTOPS', 'HARDWIRE', 'HARICOTS', 'HARINGEY', 'HARKENER', 'HARKENED', 'HARKNESS', 'HARMINES', 'HARMINIC', 'HARMLESS', 'HARMONIE', 'HARMONIC', 'HARLETON', 'HARLOTRY', 
 'HARPISTS', 'HARPLESS', 'HARPINGS', 'HARPLIKE', 'HARPOONS', 'HARPSTER', 'HARPRESS', 'HARPWISE', 'HARSLETS', 'HARRELLS', 'HARRIERS', 'HARRIETT', 'HARROWED', 'HARRIOTT', 'HARRISON', 'HARROWER', 'HARRYING', 'HARUNOBU', 'HARUSPEX', 'HARTFORD', 'HARTNETT', 'HARTNELL', 'HARTLINE', 'HARTMUNN', 'HARTTITE', 'HARTZELL', 'HARTWICK', 'HARTWELL', 'HARTWOOD', 'HARTWORT', 'HARWILLL', 'HARVESTS', 'HARVISON', 'HARVIELL', 'HARYNGES', 'HAUBERKS', 'HAUERITE', 'HAULIERS', 'HAULMIER', 'HAULSTER', 'HAUNTING', 'HAUNTERS', 'HAUSTRUM', 'HAURIENT', 'HAUTBOYS', 'HAUTEURS', 'HAUTESSE', 'HAUTBOIS', 'HAUYNITE', 'HATBOXES', 'HATELESS', 'HATFIELD', 'HAWKEYES', 'HAWKBILL', 'HAWKINGS', 'HAWKLIKE', 'HAWKNOSE', 'HAWKWEED', 'HAWKWISE', 'HAVENING', 'HAVENFUL', 'HAVELOCK', 'HAVELESS', 'HAVENNER', 'HAVERING', 'HAVERELS', 'HAVIORED', 'HAVIOURS', 'HAVOCKER', 'HAVOCKED', 'HAYCOCKS', 'HAYFIELD', 'HAYFORKS', 'HAYLOFTS', 'HAYSEEDS', 'HAYRICKS', 'HAYRIDES', 'HAYWIRES', 'HAZELINE', 'HAZELESS', 'HAZELNUT', 'HAZELTON', 'HAZINESS', 'HAZLETON'
]

EDIT:

As Eric mentions, the initial solution was very memory expensive and for larger problems it can become problematic. This is because it was storing all the possible combinations before check. An updated version is to only check a few each time. Being that itertools.product generates an iterator, one does not really need to check everything at the same time.

The variable max_members_memory in the function allows to balance speed vs. memory usage, the bigger it is, the least list.extend and set.intersection are needed.