Python Implementation of a Word Hunt Game Using Dictionary Trees

Word hunt is a very common type of game where you are given a list of letters and then asked to find as many words as you can within those letters. There are different variations of this game, one where you can reuse the letters many times (this game is called word hunt), or you can only use each letter once (this game is called reorganize the letters). The longer the word you group together the higher the score, and the highest score is achieved by using all the letters.

These types of games are 'easy' for computers to go through, and it's important to emphasize a rather useful data structure called a 'trie'.

solution strategy

Let's take out a word first「MAINE」。

The first thing to do is to decide how we want to approach the problem. If the problem is letter reorganization, then we can try all possible combinations of letters and see if they are words. This is an okay solution for letter reorganization, but it won't help us much for word hunting because letters can be reused. So while you may have found the word "name" you will never find the word "nine" again. Obviously we can't try to exhaust all possible combinations of these letters because we don't know how many times a word may be repeated. Because of this, we step back to searching a dictionary to see if the word can be made up of only the letters we have. This can take a lot of time when there is a large dictionary and you have to repeat this step every time you change a word.

As an alternative, we need a way to search the dictionary that can quickly tell us if a word is in the dictionary. This is where the predictive text structure Trie Dictionary Tree comes in.

What is a Trie?

A Trie is a tree data structure - instead of the original tree node storing a value associated with a key - this node now stores the key itself. The values in the node can be used to assign order to certain leaf nodes or probability values based on the number of traversals.

An example of a Trie from Wikipedia

The above example of a Trie is generated by "A", "to", "tea", "ted", "ten", "i", "in" and "inn". "ten", "i", "in" and "inn". Once a Trie Dictionary tree structure like this has been generated, it is O(n) complexity to determine if any of the words are in the Trie Dictionary tree. If I'm searching for "ted", I'll consume O(1) to find "t", and then consume O(1) from the "t" node to find " e", and then O(1) from the "te" node to "d".

Faced with the question, "Is this bunch of letters in this dictionary?" It's a"Very."Quick answer program. The first thing we need to do is build the dictionary.

In Python, this step is simple. Each node should look like a dictionary. So we need to start with an empty dictionary, and then for each word in the dictionary, check letter by letter to see if the next letter is in our Trie dictionary tree structure, and add it if it's not. Now, this sounds quite time consuming, and in some ways it is, but it only needs to be done once. Once the Trie is built, you can use it directly without any other overhead.

Creating a Trie Dictionary Tree

We need to start with a list filled with all possible words (there are plenty of resources for this on the web), and then our dictionary loading function might look something like the following:

def load():
    with open('') as wordFile:
        wordList = ().split()
 
    trie = {}
    for word in wordList:
        addWordToTrie(trie, word)
   
    return trie

We need a function to add words to the Trie. We do this by taking a quick look at the Trie and examining each letter to see if we need to add a new key. since we retrieve the dictionary in python by key, we don't need to store a value at each node. this is a new dictionary with its own key value.

def addWordToTrie(trie, word, idx = 0):
    if idx >= len(word):
        return       
    if word[idx] not in d:
        d[word[idx]] = {}
    addWordToTrie(d[word[idx]], word, idx+1)

Here's a simple idea. The arguments we receive are the Trie dictionary tree for the current location (note that in this example, all nodes in the Trie are also a Trie), the word, and the index of the letter we're looking at in the word.

If the index exceeds the length of the word, we stop! If it doesn't, we need to check if the letter is already in the Trie. If the letter is not in the next level of the Trie, then we add a new dictionary at that level, with the current letter as the key of the dictionary, and then we call this function recursively, passing in the dictionary (aka Trie) for the current letter, the word, and the next index position.

Using these two functions, we have constructed the Trie dictionary tree shown above. But there is a problem in front of us. How do we know that we are finding a"Word."and not a real word in front of the word"Part"What about it? For example, in the Trie example above, we want "in" to be returned as a word like "inn", but don't want "te" to be returned as a word in the dictionary.

To accomplish this, when we finish a word, the"Must."Store a value in this node. Let's go back and revisit our addWordToTrie function and set the key "leaf" to "True" if this node represents a complete word.

def addWordToTrie(d, word, idx):
    if idx >= len(word):
        d['leaf']=True
        return
    if word[idx] not in d:
        d[word[idx]] = {'leaf':False}
    addWordToTrie(d[word[idx]], word, idx+1)

Now, whenever we complete a word, we set the "leaf" value of this current dictionary node to True, or we add a new node whose "leaf" value is " False".

When we load this function to initialize, it should be the same setting {'leaf': False}, so we won't need to take an empty string and return it as a valid word.

That's it! We've created our Trie structure, now it's time to use it.

vocabulary test

Find a way to experiment: start with an empty list. For each letter in our word, check our Trie dictionary tree to see if it's in there. If it's in, get that dictionary subtree and start again (so we can check for duplicate letters). Keep this going until we find a node with the leaf flag bit true, or we can't find any letters in the word in the next level of the dictionary subtree. If we find a node with the leaf flag, add the word to the list. If we don't find the next dictionary subtree, we return and execute the next letter.

def findWords(trie, word, currentWord):
    myWords = [];
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if (trie[letter]['leaf']):
                (newWord)
            (findWords(trie[letter], word, newWord))
    return myWords

Notice here that we're building a new word to pass into the list, but we're also recursively looking for new words to use to expand our list.

Some readers may have spotted the next problem. What if the letters are repeated? For example, our word is "「TEEN」" and we're now on the "TE" node, and we've checked "t" in the subtree, which is fine, and then we checked "e" in the subtree " and find that "tee" is a word. We add "tee" to the list. But the next letter of the word is "e" again, so we find "tee" again. There are a few ways to go about solving this problem, but one of the easiest is to use a collection instead of a list.

def findWords(trie, word, currentWord):
    myWords = set()      
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if trie[letter]['leaf']:
                (newWord)
            myWords = (findWords(trie[letter], word, newWord))
    return myWords
 

Now no matter how many times we find the same word, we can guarantee uniqueness in the list. We can also de-duplicate the letters in the input word, which in turn saves processing time.

That's it! Using these three functions it is possible to find all the possible words in the dictionary by the letters we enter. Let's wrap this up in a main function and give an input to the exact steps we've done.

def main():
    print('Loading dictionary...')
    wordTrie = load()
    print('Done\n')
 
    word = raw_input("What letters should we use: ")
    minLength = int(raw_input("What is the minimum word length: "))
    print("")
 
    count = 0;
    for word in sorted(findWords(wordTrie, word, "")):
        if len(word) >= minLength:
            count = count+1
            print(word)
    print(str(count) + " words found.")

Since we're not word reorganization, we find the"Too."Multi-word. Using the example mentioned above「MAINE」And one of the dictionaries I found - which has about 370,000 words - found 208 words for this degree. That's why I added a minimum word length. Limiting the word length to at least seven, we get the following result:

Loading dictionary…
 
Done
 
What letters should we use: maine
 
What is the minimum word length: 7
 
amninia
 
anaemia
 
anamnia
 
animine
 
emmenia
 
enamine
 
manienie
 
mannaia
 
meminna
 
miminae
 
minaean
 
11 words found.

Loading the dictionary consumed about half a second, and the later word lookups were largely unremarkable.

It's inefficient to rebuild the tree every time for a word, so it's best to reuse it, either by saving the entire data structure or by trying to find multiple words in a single loop.

summarize

Hopefully, this article will provide you with a basic introduction to Trie and make it easy for you to work on some word problems. Trie is a great data structure to use when you want some automated supplemental completion of a task. Text messages, searches and even directions can all use the data in your system to build a Trie to help predict what the user will want to type next. As we've seen, it's also a great structure to use when one is searching through a large number of existing paths, which in this case is valid words.

Above is Python using dictionary tree to realize the details of the word hunting game, more information about Python dictionary tree please pay attention to my other related articles!