Word Chains

import os.path

try:    import cPickle as pickle #Only present in Python 2.*; Python 3 automatically imports the
except: import  pickle as pickle #new equivalent of cPickle, if it's available.
import zlib


def dist(word0,word1):
    if len(word0) == len(word1):
        d = 0
        for i in range(len(word0)):
            if word0[i] != word1[i]:
                d += 1
        return d
    return False

class Word(object):
    def __init__(self, index,word):
        self.index = index
        self.word = word

        self.path_parent = None

        self.connections = []
    def find_neighbors(self, words):
        for w in words:
            if w.word == self.word: continue

            d = dist(w.word,self.word)
            if d != False and d == 1:
                self.connections.append(w.index)

    def __repr__(self):
        return "<" + self.word + ">"

p = "words.conn"
if os.path.isfile(p):
    print("Reading cached data . . .")
    file = open(p,"rb")
    data_str = file.read()
    file.close()

    data_str = zlib.decompress(data_str)
    words = pickle.loads(data_str)
else:
    print("Loading word data . . .")
    file = open("dictionary.txt","r")
    data = file.readlines()
    file.close()

    print("Creating objects . . .")
    words = {}
    for line in data:
        line = line.strip()
        l = len(line)
        if l not in words.keys(): words[l]=[]
        words[l].append(Word( len(words[l]), line ))

    print("Finding neighbors . . .")
    for wordset in words.values():
        l = len(wordset[0].word)
        print((l,len(wordset)))
        #if l != 3: continue

        for word in wordset:
            word.find_neighbors(wordset)

    print("Caching to file . . .")
    data_str = pickle.dumps(words)
    data_str = zlib.compress(data_str,9)

    file = open(p,"wb")
    file.write(data_str)
    file.close()
print("Done!")


def get_word(s):
    wordset = words[len(s)]
    for w in wordset:
        if w.word == s:
            return w
    assert False

#List of strings excluded from search.  Add to as desired.
ignore = []
def print_path(src,dst):
    l = len(src.word)
    wordset = words[l]

    for word in wordset:
        word.path_parent = None

    openset = [src]
    while len(openset) > 0:
        word=openset[0]; openset=openset[1:]
        for iconnection in word.connections:
            connection = wordset[iconnection]
            if connection.word in ignore: continue
            if connection.path_parent == None:
                connection.path_parent = word
                openset.append(connection)

        if word == dst: break

    if dst.path_parent == None:
        print("No path found!")
    else:
        path = [dst]
        current = dst
        while current != src:
            path.append(current.path_parent)
            current = current.path_parent
            assert current != None
        for w in path[::-1]:
            print(w)

##print_path(get_word("aa"),get_word("ab"))
##print_path(get_word("bot"),get_word("car"))
##print_path(get_word("door"),get_word("hers"))
##print_path(get_word("hammer"),get_word("cheese"))
print_path(get_word("under"),get_word("stand"))