Problem

Given two words of the same length, build a chain of words connecting the two. Each word in the chain must be in the provided dictionary and every step along the chain changes exactly one letter from the previous word. For example, a word chain from “duck” to “ruby” is [duck - dunk - dune - rune - rube - ruby]. (Source)

Try it at repl.it

Algorithm

This problem can be solved using a graph model. Words are vertices, and edges connect words that are different by only one character (“adjacent”). Presumably, we would like the shortest chain between the source and target, therefore breadth-first search is used.

  1. Maintain a queue of words to be searched and a mapping of all of the searched words and their immediate sources.
  2. At first, the queue contains only the source word and its immediate source is None.
  3. Take a word from the front of the queue, explore its adjacent words. If the adjacent word is a valid word and has not been searched, add it to the end of the queue and mark it in the mapping.
  4. Repeat the previous step until the queue is empty. If we encounter the target during the search, break out the loop and build the chain from stepping through the mapping. Otherwise, the chain does not exist.

Source Code

from collections import deque
from string import ascii_lowercase

class WordChainer:
    def __init__(self):
        with open("./dict.txt") as d:
            self.dictionary = { line.strip() for line in d }

    def find_chain(self, source, target):
        self.setup(source, target)
        while self.to_explore:
            current_word = self.to_explore.popleft()
            self.explore_word(current_word)
            if self.found:
                self.output_chain()
                return
        print("Could not find a chain")

    def setup(self, source, target):
        self.explored = { source: None } # key: word; value: the previous word
        self.to_explore = deque([source]) # a dequeue containing words to be explored
        self.target = target
        self.found = False

    def explore_word(self, current_word):
        for adjacent_word in self.adjacent_word_gen(current_word):
            self.explored[adjacent_word] = current_word
            if adjacent_word == self.target:
                self.found = True
                return
            self.to_explore.append(adjacent_word)

    def adjacent_word_gen(self, current_word):
        for index, current_letter in enumerate(current_word):
            for new_letter in ascii_lowercase:
                if new_letter == current_letter:
                    continue
                candidate = current_word[:index] + new_letter + current_word[index + 1:]
                if candidate in self.dictionary and candidate not in self.explored:
                    yield candidate

    def output_chain(self):
        print("Chain found")
        chain = self.build_chain()
        print(chain)

    def build_chain(self):
        reversed_chain = []
        current_word = self.target
        while current_word:
            reversed_chain.append(current_word)
            previous_word = self.explored[current_word]
            current_word = previous_word
        chain = reversed_chain[::-1]
        return chain

wc = WordChainer()
print("Example: wc.find_chain('duck', 'ruby')")
wc.find_chain('duck', 'ruby')