Untitled

#!/usr/bin/python
import sys

class WordTable:
    """
    Describes a data structure that allows for easy and fast fetching of
    all the words that are different from a given word by exactly one letter
    """

    def __init__(self):
        # A list whose index is the word with one letter replaced by its number
        self.prefixes = dict()
        # A list of prefixes that we only see for the first time
        self.pregatory = dict()
        # Also, a list of whole words - jsut for the validity checks
        self.words = set()

    def add_word(self, word):
        self.words.add(word)
        for i in xrange(len(word)):
            prefix = word[:i] + '.' +  word[i+1:]
            if prefix not in self.pregatory:
                self.pregatory[prefix] = word
            else:
                if self.pregatory[prefix] == True:
                    self.prefixes[prefix].append(word)
                else:
                    self.prefixes[prefix] = [word, self.pregatory[prefix]]
                    self.pregatory[prefix] = True

    def find_matches(self, word):
        """
        Find all the words that differ from a given one by a single letter
        """
        matches = []
        for i in xrange(len(word)):
            prefix = word[:i] + '.' + word[i+1:]
            if prefix in self.prefixes:
                matches += self.prefixes[prefix]
        return matches

    def has_word(self, word):
        return word in self.words


dictionary = WordTable()
def read_dict(filename):
    f = open(filename)
    for line in f:
        dictionary.add_word(line.rstrip().lower())
    f.close()

def path(a, b):
    pending = [a]
    tried = {a : None}
    while len(pending) > 0:
        top = pending.pop(0)
        if top == b:
            chain = []
            cur = top
            while cur != None:
                chain.insert(0, cur)
                cur = tried[cur]
            return chain
        for word in dictionary.find_matches(top):
            if word not in tried:
                tried[word] = top
                pending.append(word)
    return None

def print_path(p):
    if p == None:
        print "ERROR: no path"
        return
    print ' > '.join(p), "(%d)" % len(p)

def main():
    read_dict(sys.argv[1])

    while True:
        try:
            pair = raw_input("ENTER WORDS:").rstrip()
            words = pair.split(' ')
            if (len(words) != 2):
                print "ERROR: input must be two words separated by a space"
                continue
            if (len(words[0]) != len(words[1])):
                print "ERROR: words must be of the same length"
                continue
            if not dictionary.has_word(words[0]) or not dictionary.has_word(words[1]):
                print "ERROR: at least one of the words is not in the dictionary"
                continue
            p = path(words[0], words[1])
            print_path(p)
        except EOFError:
            sys.exit()

main()