Python program to find a word ladder transforming "four" to "five"

Question

I saw this Puzzling problem and thought I would try to write a Python program to solve it. The task is to transform "four" to "five", forming a new four-letter word at each step, replacing one letter at each step, in as few steps as possible.

But turns out I don't know how to optimize recursion, so I'm posting here for help. I'm mostly just confused on why the code to change the past needs to be at the top of the function, but I would also like advice on how to speed this up in general. Right now it takes about 10x as long for each step up max_depth gets on my computer.

There won't be any matches until you change max_depth - I didn't want anyone copy-pasting and lagging out. There should be a solution at depth 5, according to Puzzling. However, my words file doesn't have the Foud or the word Fous, which that answer uses. Bumping up to max_depth six will take my computer ~10 minutes, which I don't want to try yet.

def hamming(string1, string2):
 assert len(string1) == len(string2)
 return sum(char1 != char2 for char1, char2 in zip(string1, string2))
max_depth = 3
start_word = "five"
end_word = "four"
all_words = open("/usr/share/dict/words", "r").read().lower().splitlines()
all_words = list(filter(lambda word: word.isalpha(), all_words))
all_words = list(filter(lambda word: len(word) == len(start_word), all_words))
sequences = []
def search(current_word, past = []):
 # Needs to be first to be fast for some reason
 past = past[:]
 past.append(current_word)
 if len(past) > max_depth:
 sequences.append(past)
 return
 for word in all_words:
 if hamming(word, current_word) == 1 and word not in past:
 search(word, past)
search(start_word)
sequences = [sequence[:sequence.index(end_word) + 1] for sequence in sequences if end_word in sequence]
if len(sequences) == 0:
 print("No matches")
else:
 print(min(sequences, key=len))

Answer 1

By performing recursion, you are performing a depth-first search of four-letter words. However, this task involves finding a shortest path, and shortest-path problems are generally better done using breadth-first search. With BFS, the first solution you encounter will be an optimal solution — which is not the case with DFS.

• Alex F: How would I implement that?
• 200_success: There are plenty of word ladder solutions to study on this site already. There are also many breadth-first-search implementations you can study.
• Alex F: Thanks, this worked really well. Runs in under 6 seconds now.