Skip to main content
added 65 characters in body
Source Link
200_success
  • 145.6k
  • 22
  • 191
  • 481

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 a good way to dohow 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.

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 a good way to do backtracking. 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.

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.

Source Link
200_success
  • 145.6k
  • 22
  • 191
  • 481

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 a good way to do backtracking. 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.