One letter game Issue?

Question

Recently at a job interview I was given the following problem: Write a script capable of running on the command line as python It should take in two words on the command line (or optionally if you'd prefer it can query the user to supply the two words via the console). Given those two words: a. Ensure they are of equal length b. Ensure they are both words present in the dictionary of valid words in the English language that you downloaded. If so compute whether you can reach the second word from the first by a series of steps as follows a. You can change one letter at a time b. Each time you change a letter the resulting word must also exist in the dictionary c. You cannot add or remove letters If the two words are reachable, the script should print out the path which leads as a single, shortest path from one word to the other. You can /usr/share/dict/words for your dictionary of words. My solution consisted of using breadth first search to find a shortest path between two words. But…

Accepted Answer

I wouldn't say your solution is wrong, but it is a little slow. For two reasons.

Breadth-first-search is going to visit all paths of length one shorter than is needed, plus some-to-all of paths of length needed, before it can give you an answer. A best-first-search (A*) will ideally skip most irrelevant paths.

You're checking every word in the dictionary for candidacy as a neighbor each time you look for neighbors. As Duncan suggests, you can build a data structure to essentially look up the neighbors instead of searching for them.

Here is another solution to your problem:

```
import collections
import heapq
import time

def distance(start, end):
    steps = 0
    for pos in range(len(start)):
        if start[pos] != end[pos]:
            steps += 1
    return steps

class SearchHeap(object):
    def __init__(self):
        self.on_heap = set()
        self.heap = []

def push(self, distance, word, path):
        if word in self.on_heap:
            return
        self.on_heap.add(word)
        heapq.heappush(self.heap, ((distance, len(path)), word, path))

def __len__(self):
        return len(self.heap)

def pop(self):
        return heapq.heappop(self.heap)

class OneLetterGame(object):
    _word_data = None

def __init__(self, dict_path):
        self.dict_path = dict_path

def run(self, start_word, end_word):
        start_time = time.time()
        self._word_data = collections.defaultdict(list)
        if len(start_word) != len(end_word):
            print 'words of different length; no path'
            return

found_start, found_end = self._load_words(start_word, end_word)
        if not found_start:
            print 'start word %r not found in dictionary' % start_word
            return
        if not found_end:
            print 'end word %r not found in dictionary' % end_word
            return

search_start_time = time.time()
        path = self._shortest_path(start_word, end_word)
        search_time = time.time() - search_start_time
        print 'search time was %.4f seconds' % search_time

if path:
            print path
        else:
            print 'no path found from %r to %r' % (start_word, end_word)

run_time = time.time() - start_time
        print 'total run time was %.4f seconds' % run_time

def _load_words(self, start_word, end_word):
        found_start, found_end = False, False
        length = len(start_word)
        with open(self.dict_path) as words:
            for word in words:
                word = word.strip()
                if len(word) == length:
                    if start_word == word: found_start = True
                    if end_word == word: found_end = True
                    for bucket in self._buckets_for(word):
                        self._word_data[bucket].append(word)
        return found_start, found_end

def _shortest_path(self, start_word, end_word):
        heap = SearchHeap()
        heap.push(distance(start_word, end_word), start_word, (start_word,))
        while len(heap):
            dist, word, path = heap.pop()
            if word == end_word:
                return path
            for neighbor in self._neighbors_of(word):
                heap.push(
                    distance(neighbor, end_word), 
                    neighbor, 
                    path + (neighbor,))
        return ()

def _buckets_for(self, word):
        buckets = []
        for pos in range(len(word)):
            front, back = word[:pos], word[pos+1:]
            buckets.append(front+'*'+back)
        return buckets

def _neighbors_of(self, word):
        for bucket in self._buckets_for(word):
            for word in self._word_data[bucket]:
                yield word

if __name__ == '__main__':
    import sys
    if len(sys.argv) not in [3, 4]:
        print 'Usage: python one_letter_game.py start_word end_word'
    else:
        matt = OneLetterGame(dict_path = '/usr/share/dict/words')
        matt.run(*sys.argv[1:])
```

And, a timing comparison:

```
% python /tmp/one_letter_alex.py canoe happy
The shortest path (found in 51.98 sec.) is:
=> canoe -- canon -- caxon -- taxon -- taxor -- taxer -- taper -- paper -- papey -- pappy -- happy

% python /tmp/one_letter_matt.py canoe happy
search time was 0.0020 seconds
('canoe', 'canon', 'caxon', 'taxon', 'taxor', 'taxer', 'taper', 'paper', 'papey', 'pappy', 'happy')
total run time was 0.2416 seconds
```

One letter game Issue?

Solution

Problem

Related problems