# Python program to find a word ladder transforming “four” to “five”

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))  ``
Posted on Categories buy elite proxies