Find a path from one word to another

transform_word.py

#!/usr/bin/env python
"""
Given the start word and end word find one of the
shortest possible paths from one word to the other
that can be achieved by substituting a single
character (where each word in the path is a valid
English word)

Usage:

./tranform_words.py <word1> <word2>

e.g.

$ ./tranform_words.py chai tame
$ ['chai', 'chat', 'coat', 'cost', 'cast', 'case', 'came', 'tame']
"""
from argparse import ArgumentParser, ArgumentDefaultsHelpFormatter
from heapq import heappush, heappop
from string import lowercase
from urllib import urlopen

WORDLIST_URL = 'https://raw.githubusercontent.com/mattt/mobius/master/data/english-wordlist'


def load_wordlist():
    return set(urlopen(WORDLIST_URL).read().split())


def find_shortest_path(wordlist, start, end):
    # Routes is a heap of (deviations, negative_index, path)
    routes = [(0, (start,))]
    visited = set()  # words that we've already seen

    while routes:
        deviations, path = heappop(routes)
        word = path[-1]
        for index in range(len(word)):
            for char in lowercase:
                new_word = word[:index] + char + word[index + 1:]
                if new_word == end:
                    return list(path) + [end]
                if new_word in wordlist:
                    if new_word in visited:
                        continue
                    # Augment deviations if end[index] != char
                    new_deviations = deviations if end[index] == char else deviations + 1
                    # Update the path if you're changing a character
                    new_path = path if word == new_word else path + (new_word,)
                    visited.add(new_word)
                    heappush(routes, (new_deviations, new_path))
    return 'No path connecting the words provided'


def main():
    parser = ArgumentParser(description=__doc__,
                            formatter_class=ArgumentDefaultsHelpFormatter)
    parser.add_argument('word1', help='The initial word')
    parser.add_argument('word2', help='A word of length identical to word1')

    args = parser.parse_args()

    if len(args.word1) != len(args.word2):
        print 'The two words must contain the same number of characters'
    else:
        wordlist = load_wordlist()
        print find_shortest_path(wordlist, args.word1.lower(), args.word2.lower())


if __name__ == '__main__':
    main()