A solution to the word chains problem, described below in markdown. Implemented in Python using /usr/share/dict/words as dictionary source.

permute_dictionary.py

from Queue import Queue
from collections import defaultdict
import warnings

def permute_word(dictionary,start,end):
    if not isinstance(dictionary,set):
        warnings.warn('dictionary is not a set, use set for fastest lookup')

    if start not in dictionary or end not in dictionary:
        raise LookupError('One of the input words is not a valid dictionary word')
    
    parent = {}
    q = Queue()
    q.put(start)
    while not q.empty():
        current = q.get()
        for i in xrange(len(current)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if char is not current[i]:
                    nxt = current.replace(current[i],char) 
                    if nxt not in parent and nxt in dictionary:
                        parent[nxt]=current
                        q.put(nxt)
    
    if end not in parent.keys():
        return None
    
    output = []
    output.append(end)
    cur = end
    while cur is not start:
        cur = parent.get(cur)
        output.append(cur)
    return output

if __name__ == '__main__':
    dictionary = set([line.strip().lower() for line in open('/usr/share/dict/words','r')])
    print permute_word(dictionary,'boar','fear')

test.py

import unittest
from permute_dictionary import permute_word

__dictionary__ = set([line.strip().lower() for line in open('/usr/share/dict/words','r')])

class Test(unittest.TestCase):

    def setUp(self):
        self.dictionary = __dictionary__
        self.valid_starts = ['cat','boar']
        self.valid_ends = ['far','fear']
        self.invalid_inputs = ['asdfggs','asdfsdf']

    def test_valid(self):
        for i in xrange(len(self.valid_starts)):
            path = permute_word(self.dictionary,self.valid_starts[i],self.valid_ends[i])
            self.assertIsInstance(path,list)

    def test_invalid(self):
        self.assertRaises(LookupError,permute_word,self.dictionary,self.invalid_inputs[0],self.invalid_inputs[1])

if __name__ == '__main__':
    unittest.main()

WordChains.md

#Word Chains

Given a source string and a destination string write a program to display sequence of strings to travel from source to destination by changing a word at a time.

Rules for traversing:

1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary

Example: Given source word CAT and destination word DOG , one of the valid sequence would be CAT -> COT -> DOT -> DOG Another valid sequence can be CAT -> COT - > COG -> DOG