Skip to main content
added 242 characters in body
Source Link
user14393
user14393

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)

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)

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)

Source Link
user14393
user14393

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.

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])