Generate "Word Path" Between Two Words

word_path.py

#goal is to compute the 'path' from one valid word to another by only changing one letter at a time (forming valid words inbetween)

#example:
# cat -> dog
# cat -> cot -> cog -> dog
import sys
import string

alphabet = string.ascii_lowercase

word_dict = dict()
def load_dictionary():
    dict_file = open('/usr/share/dict/words', 'r')
    for line in dict_file:
        trimmed = line[:len(line)-1]
        word_dict[trimmed] = True

def is_valid_word(word):
    return word in word_dict

def sub_at_index(word, index, letter):
    return word[:index] + letter + word[index+1:]

def permute_possible_words(word):
    #for each letter, change to any letter that is not the current letter, test if that makes a valid word
    new_words = []
    
    for index in range(0, len(word)):
        c = word[index]
        for new_c in alphabet:
            if c != new_c:
                new_word = sub_at_index(word, index, new_c)
                if is_valid_word(new_word):
                    new_words.append(new_word)

    return new_words

def compute_path(word1, word2):

    if len(word1) == 0:
        print "Error: Invalid word length"
        sys.exit(1)

    if len(word1) != len(word2):
        print "Error: Words are not the same length"
        sys.exit(1)

    if word1 == word2: 
        return [word1, word2]

    state_queue = [(word1, [word1])]

    while len(state_queue) != 0:
        word, path = state_queue.pop(0)
        
        for new_word in permute_possible_words(word):
            if not( new_word in path ):
                new_path = path[:]
                new_path.append(new_word)

                if new_word == word2:
                    return new_path
                else:
                    state_queue.append( (new_word, new_path ) )

    return path
    
if __name__ == "__main__":
    load_dictionary()
    word1 = sys.argv[1]
    word2 = sys.argv[2]

    path = compute_path(word1, word2)

    for word in path:
        print word