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