Algorithm to transform one word to another through valid words

Question

I have been practicing backtracking and I wanted to know how I can improve my code. For eg, I don't want to use global. Also, I am not sure if my code will work for all the cases.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only
# one letter at a time.  The new word you get in each step must be in the
# dictionary.

# def transform(english_words, start, end):

# transform(english_words, 'damp', 'like')
# ['damp', 'lamp', 'limp', 'lime', 'like']
# ['damp', 'camp', 'came', 'lame', 'lime', 'like']


def is_diff_one(str1, str2):
    if len(str1) != len(str2):
        return False

    count = 0
    for i in range(0, len(str1)):
        if str1[i] != str2[i]:
            count = count + 1

    if count == 1:
        return True

    return False


potential_ans = []


def transform(english_words, start, end, count):
    global potential_ans
    if count == 0:
        count = count + 1
        potential_ans = [start]

    if start == end:
        print potential_ans
        return potential_ans

    for w in english_words:
        if is_diff_one(w, start) and w not in potential_ans:
            potential_ans.append(w)
            transform(english_words, w, end, count)
            potential_ans[:-1]

    return None


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like'])
transform(english_words, 'damp', 'lame', 0)

Answer 1

Always Return An Answer

Whenever you're writing an algorithm, it should return the answer. Not print and return, not just print. Just return. If you want to print, you can always write print some_algo(...).

is_diff_one

We can write this a little cleaner. There is a zip() function in the Python standard library that can walk multiple iterables at once. (In Python 2.7, we should use itertools.izip() since that won't generate a whole list up front). The advantage here is that we can write:

count = 0
for a, b in zip(str1, str2):
    if a != b:
        count += 1
        if count > 1:
            # quit early
            return False

# in case we're equal
return count == 1

Try to avoid patterns like:

if expr:
    return True
return False

That's the same as return expr

Backtracking

This line:

potential_ans[:-1]

doesn't actually do anything. It will return a slice of potential_ans, but it doesn't actually modify it. What you wanted to do was

potential_ans.pop()

But this is error-prone (and relies on global state). Instead of modifying potential_ans, what we can do is provide a new object to each recursive instantiation. This leads me to...

Your algorithm

Now, you want this to be entirely self-contained. You're right in wanting to avoid global variables - and you have most of the right idea in that we want to recursively call down with the next word. The one change is the last argument. count isn't really meaningful here. What you want instead is the path you've come so far:

def transform(english_words, start, end, cur_path):
    if start == end:
        return [cur_path]

That way, our path is local rather than global. Then we just walk the rest of the words as you're doing:

results = []
for w in english_words:
    if is_diff_one(w, start) and w not in cur_path:
        solutions = transform(english_words, w, end, cur_path + [w])
        results.extend(solutions)
return results

Note that I'm changing your return type from list to list of lists. Now this will return a list of all the possible transformation lists.

Of course, we'd need a sensible default cur_path. Let's avoid the user having to come up with one:

def transform(english_words, start, end, cur_path=None):
    if cur_path is None:
        cur_path = [start]

Answer 2

There are four other answers here, and they all have very sensible advice. But none of them, as far as I can see, points out the terrible runtime complexity of the chosen algorithm, so I think an additional answer is necessary.

1. Bug

>>> english_words = set('bar bat cat war'.split())
>>> transform(english_words, 'bar', 'war', 0)
['bar', 'bat', 'cat', 'war']

As pointed out by Barry, ths is because the line

potential_ans[:-1]

is a mistake for:

potential_ans.pop()

In what follows, I'm going to assume that the bug is fixed.

2. Abstracting the problem

The problem being solved here can be thought of as a problem on a graph, in which each word is a node of the graph, and two words are connected if they differ by one letter. Supposing that the words are cake, came, camp, dame, damp, dike, dime, lake, lame, lamp, like, lime, and limp, then the graph looks like this:

A transformation of one word to another corresponds to a path in this graph. For example one possible transformation of cake to limp corresponds to the highlighted path here:

Finding the shortest transformation between two words corresponds to finding the shortest path between the two nodes in the graph.

There are several benefits of thinking about a problem in terms of abstract data structures like graphs, including:

1. There are standard terms for describing the problem: here nodes, edges, paths.

2. There are concrete representations of the data structure that support efficient operations.

3. You can look up the best known algorithms for solving the problem, instead of having to invent your own.

3. Description and complexity of algorithm

With the bug noted in §1 fixed, what your program does is to generate all the simple paths (paths with no repeated nodes) in the graph of words beginning at start, until it finds a path that leads to end.

But this can take a very very long time:

>>> from timeit import timeit
>>> english_words = set('bar bat cat eat fat hat mat oat pat rat sat tat vat war'.split())
>>> timeit(lambda:transform(english_words, 'bar', 'war', 0), number=1)
['bar', 'war']
2732.44891167

Why does the algorithm take three-quarters of an hour to find this result? Well, the graph being searched looks like this:

The algorithm starts at bar and keeps adding nodes to its path until it can't go any further without repeating a node. For example (depending on the order in which the words are retrieved from the set), it might end up with this path:

After backtracking a couple of steps, it will find this path:

and so on. You'll see that it will explore every path that starts bar—bat and then visits all the —at words. There are \$ 11! = 39,916,800 \$ such paths, and only when it has explored them all will it consider the path bar—war.

Checking to see if two words with \$ m \$ letters differ by one letter takes time \$ O(m) \$, so if there are \$ n \$ words of \$ m \$ letters each, the total runtime is \$ O(n!m) \$.

4. Better algorithm

It is possible to do much better than this if you use one of the standard graph search algorithms such as Dijkstra's or A*. Here's an implementation using the latter.

from collections import defaultdict, namedtuple
from heapq import heappush, heappop

class NotFound(Exception):
    pass

def word_ladder(words, start, end):
    """Return a word ladder (a list of words each of which differs from
    the last by one letter) linking start and end, using the given
    collection of words. Raise NotFound if there is no ladder.

    >>> words = 'card care cold cord core ward warm'.split()
    >>> ' '.join(word_ladder(words, 'cold', 'warm'))
    'cold cord card ward warm'

    """
    # Find the neighbourhood of each word.
    placeholder = object()
    matches = defaultdict(list)
    neighbours = defaultdict(list)
    for word in words:
        for i in range(len(word)):
            pattern = tuple(placeholder if i == j else c
                            for j, c in enumerate(word))
            m = matches[pattern]
            m.append(word)
            neighbours[word].append(m)

    # A* algorithm: see https://en.wikipedia.org/wiki/A*_search_algorithm

    # Admissible estimate of the steps to get from word to end.
    def h_score(word):
        return sum(a != b for a, b in zip(word, end))

    # Closed set: of words visited in the search.
    closed_set = set()

    # Open set: search nodes that have been found but not yet
    # processed. Accompanied by a min-heap of 4-tuples (f-score,
    # g-score, word, previous-node) so that we can efficiently find
    # the node with the smallest f-score.
    Node = namedtuple('Node', 'f g word previous')
    open_set = set([start])
    open_heap = [Node(h_score(start), 0, start, None)]
    while open_heap:
        node = heappop(open_heap)
        if node.word == end:
            result = []
            while node:
                result.append(node.word)
                node = node.previous
            return result[::-1]
        open_set.remove(node.word)
        closed_set.add(node.word)
        g = node.g + 1
        for neighbourhood in neighbours[node.word]:
            for w in neighbourhood:
                if w not in closed_set and w not in open_set:
                    next_node = Node(h_score(w) + g, g, w, node)
                    heappush(open_heap, next_node)
                    open_set.add(w)

    raise NotFound("No ladder from {} to {}".format(start, end))

Suppose that there are \$ n \$ words of \$ m \$ letters, and \$ e \$ edges in the graph of words. Then this algorithm takes \$ O(m^2n) \$ to find the edges and then \$ O(e + mn + n \log n) \$ to find the shortest path.

So this finds shortest ladders on large sets of words in a reasonable amount of time:

>>> dictionary = [w.strip() for w in open('/usr/share/dict/words') if w == w.lower()]
>>> five_letter_words = [w for w in dictionary if len(w) == 5]
>>> len(five_letter_words)
8497
>>> from timeit import timeit
>>> timeit(lambda:print(' '.join(word_ladder(five_letter_words, 'above', 'below'))), number=1)
above amove amoke smoke smoky sooky booky booly bolly bally balli balai balao baloo balow below
0.3188382713124156

Answer 3

is_diff_one()

You have chosen to require both strings to be the same length. That's fine, but perhaps you would like to also consider adding or removing one letter to be a difference of one.

A simpler way to write this function would be

def is_diff_one(str1, str2):
    return 1 == sum(c1 != c2 for c1, c2 in zip(str1, str2))

The drawback is that it won't short-circuit as soon as it finds a second difference. For short words like your test case, I don't think that matters.

Recursion and backtracking

potential_ans[:-1] has no effect. It produces and discards a copy of potential_ans with the last element omitted. You probably wanted potential_ans.pop().

But that's not how I would recommend doing backtracking, if you are still confused by how to pass data around. The good options are either:

1. Use recursion properly, and store all of the state information you need in the call stack, or
2. Use your own list as a stack, in which case I would recommend looping instead of recursing.

Option 2 is rather tricky to implement, so I recommend that you should stick to your recursive approach.

Recursion

When doing recursion, you should not think of functions as procedures with side-effects. Rather, treat them as functions in a mathematical sense: the function must produce one deterministic answer based solely on its parameters, and result in no side-effects.

def transform(dictionary, goal, chain):
    if chain[-1] == goal:
        return chain
    for word in dictionary:
        if is_diff_one(word, chain[-1]) and word not in chain:
            result = transform(dictionary, goal, chain + [neighbor])
            if result:
                return result

print transform(english_words, 'lame', ['damp'])

You could possibly improve efficiency by using append() and pop(), but you should be sure to fully understand how to do recursion properly before you mess with such mutation operations, because they have side-effects.

I've removed the count parameter, since it was just a cumbersome way to initialize the chain.

Answer 4

I'm going to focus on implementing the recursion.

First, let's avoid the globals. The easiest way is to keep the same structure, but move it into a local namespace:

def transform(english_words, start, end):
    potential_ans = [start]
    results = []
    def recursion(start_, end_):
        if start_ == end_:
            results.append(list(potential_ans))
            return
        for w in english_words:
            if is_diff_one(w, start_) and w not in potential_ans:
                potential_ans.append(w)
                recursion(w, end_)
                potential_ans.pop()
    recursion(start, end)
    return results

english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
    print(answer)

I've mainly just made transform a function sets up the right arrays, and then converted the original implementation into the nested function recursion. Notice I've created a results array for storing the results. Also notice the need to make a copy of the potential answer when storing it as a result, since we will continue to modify potential_ans.

I've also modified the list of words so there is more than one result.

I assume you want to obtain all answers; it shouldn't be hard to modify this to end the recursion as soon as an answer is discovered... however, a better approach will be described below.

Given this change, the arguments to recursion are redundant: it can be changed to the following. (if you're really serious, you should profile this change, to determine whether it actually makes things faster)

def transform(english_words, start, end):
    potential_ans = [start]
    results = []
    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            results.append(list(potential_ans))
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                potential_ans.append(w)
                recursion()
                potential_ans.pop()
    recursion()
    return results

Now, a better way to generate a sequence of results is to, well, use a generator:

def transform(english_words, start, end):
    potential_ans = [start]
    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            yield list(potential_ans)
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                potential_ans.append(w)
                yield from recursion()
                potential_ans.pop()
    yield from recursion()

english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
    print(answer)

Note the use of yield and yield from for yielding results. Using generators has a number of advantages including: you get to see results as they're created, you can stop iterating when you're happy with a result, rather than having to wait for the entire recursion to finish, you don't waste memory/time creating a list of all the results.

Generators take a little bit of time to get used to, but they're well worth it, and should often be preferred to returning lists of results.

Finally, one last neat trick; the general pattern of "make a change ... do stuff... undo the change" can be error prone; it can be easy to forget to undo the change, or an odd code path (e.g. an exception) skips the change.

The other answers suggest making copies; however, backtracking algorithms like this can often suffer massive performance penalties from such a change, so it's worth knowing a pattern that mitigates this problem without introducing copies.

We can use a context manager to do this automatically, such as below. (this post is not meant to be a tutorial on context managers)

from contextlib import contextmanager

def transform(english_words, start, end):
    potential_ans = [start]

    @contextmanager
    def push(word):
        potential_ans.append(word)
        yield
        potential_ans.pop()

    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            yield list(potential_ans)
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                with push(w):
                    yield from recursion()
    yield from recursion()

Finally, one may dislike the fact that useful functionality is buried in nested functions; we can pull the nested functions out:

@contextmanager
def temp_push(seq, ele):
    seq.append(ele)
    yield
    seq.pop()

def transform_recursion(english_words, end, potential_ans):
    tail = potential_ans[-1]
    if potential_ans[-1] == end:
        yield list(potential_ans)
        return
    for w in english_words:
        if is_diff_one(w, tail) and w not in potential_ans:
            with temp_push(potential_ans, w):
                yield from transform_recursion(english_words, end, potential_ans)


def transform(english_words, start, end):
    yield from transform_recursion(english_words, end, [start])

Answer 5

Proviso I have not checked the logic of your code, mostly just the styling and language features you could have used but missed.

Make your functions single use

This is a general rule of programming, but one I have found especially good to enforce in Python, particularly because lots of small, single-use functions just look so beautiful when you code them up in PEP-style (which I am far from good at myself). So I'm not sure why you're printing in transform. Generally, you should try to keep logging as its own function, separate from calculations and the like. This is especially true in your function where you print the result and then return it. Why not return and then print wherever you return from, to make your code easier to maintain and understand?

It's easy to avoid globals in Python

You mentioned that you didn't want to use global variables. You don't have to. You can pass a variable to a function whenever you find yourself worrying about manipulating globals. You don't want your function in any way to depend on the name of a global if you can avoid it. There are many ways to fix this. One is to wrap your global in some kind of sensible class object. Additionally, and complementary, you should pass everything into your function as a parameter, even if it is a global, so you can do something like this:

def transform(english_words, start, end, count, potential_ans):

Python is passing something like a reference, so the changes you make to potential_ans will persist, at least when you do things like appending letters. Read more on this from this SO post.

Efficiency

Seems like you go through your english_words more than you need to. Why don't you break out of your for loop once you find the match you need?

Also on efficiency, I'd recommend doing the start==end check after the count check.

You can eliminate the if count == 0 step altogether if you make use of a nice feature of Python that [] is a false value. Then you can initially pass in an empty list and build it up with your recursive calls. Once you're passing potential_ans as a parameter, initially pass in an empty list and then use this statement:

potential_ans = potential_ans or [start]

This might be more efficient (easy to test) and it's certainly clearer and more succinct than the count check you are using now.

Confusing parts of your code

What does count do in transform? I see you increment it sometimes in transform and you also use it in is_diff_one. As a reader of your code, I wish you'd comment on whether there counts are related...is this some funky global variable manipulation or just your favorite count variable name? This is exactly where comments can save your reader a lot of work.

Actually, why do you set up potential_ans as a global variable when you redefine it inside your function anyway? Why don't you just initialize it yourself and keep passing it as a parameter (see above). This is a design decision, so you should comment here to explain to your otherwise puzzled reader.

What is the point of your last expression in your for loop over english_words, this one: potential_ans[:-1]. This one has really got me puzzled. Are you changing something? So far as I know Python syntax, you're simply referring to the last element of this list but not doing anything to/with it. Am I missing something? If so, a comment would help here. If not, this should be deleted as it doesn't affect the program at all apart from running an unnecessary expression.