Words Blog Post Snippets

sorted.py

import itertools

class Dictionary(object):
    def __init__(self):
        self.words = {}

    def insert(self, word):
        letters = "".join(sorted(word))
        if letters not in self.words:
            self.words[letters] = [word]
        elif word not in self.words[letters]:
            self.words[letters].append(word)

    def getAnagrams(self, word):
        letters = "".join(sorted(word))
        words = self.words.get(letters, [])
        return words

    def getScrabbleWords(self, letters):
        words = []
        letters = "".join(sorted(letters))
        for n in xrange(2, len(letters)+1):
            for combination in itertools.combinations(letters, n):
                candidate = "".join(combination)
                w = self.words.get(candidate, [])
                if w:
                    words.extend(w)

        words = list(set(words))
        words.sort()
        return words

d = Dictionary()
with open("words.txt") as f:
    for word in f:
        d.insert(word)

d.getAnagrams("ehllo")
d.getScrabbleWords("ehllo")

trie.py

class Trie(object):
    def __init__(self):
        self.trie = {}

    def insert(self, word):
        trieNode = trie
        for letter in word:
            if not letter in trieNode:
                trieNode[letter] = {}
            trieNode = trieNode[letter]
        trieNode[EOW] = 1

    def depthFirstWords(self, letters, trieNode, accumulator):
        for letter, node in trieNode.iteritems():
            if letter != EOW and node:
                if node.get(EOW, False):
                    accumulator.append("".join(letters + letter))
                self.depthFirstWords(letters+letter, node, accumulator)
        return accumulator

    def getWordsFromTrieWithTransform(self, trie, letters, transform):
        trieNode = trie
        letters = transform(letters)
        for letter in letters:
            trieNode = trieNode.get(letter, None)
            if not trieNode:
                return None

        words = []
        if trieNode.get(EOW, False):
            words.append("".join(letters))

        self.depthFirstWords(letters, trieNode, words)

        words = [transform(word) for word in words]
        words.sort()
        return words

    def getWordsStartingWith(self, letters):
        identity = lambda x: x
        return self.getWordsFromTrieWithTransform(self.trie, letters, identity)

trie = Trie()
with open("words.txt") as f:
    for word in f:
        trie.insert(word)

trie.getWordsStartingWith("hello")

words_simple.py

"""
This works but is considerably slower because it has to check
every permutation of the letters.
"""

import itertools
import sys

dictionary = {}

def getScrabbleWords(letters):
    letters = letters.strip().lower()
    words = []
    for x in xrange(2, len(letters)+1):
        for permutation in itertools.permutations(letters, x):
            word = "".join(permutation)
            if word in dictionary:
                words.append(word)
    words.sort()
    return words

with open("words.txt") as f:
    for word in f:
        dictionary[word.strip().lower()] = 1
print getScrabbleWords("ehllo")