# Word Morph (changing one letter at a time)

Below is my implementation of Word Morph solver in Python.

The challenge consists of transforming one word into another word by changing one letter at a time. Each word in the chain should be an English word (part of a dictionary). One should output all such chains of the minimal possible length. Examples: 'tree' to 'fled' chain is ['tree', 'free', 'flee', 'fled'], 'man' to 'spa' chains are ['man', 'may', 'say', 'spy', 'spa'] and ['man', 'men', 'sen', 'sea', 'spa'].

Comments on algorithm (I only compare the leaves of the trees because it is more efficient) and general comments would be much appreciated.

Test cases have not been implemented properly, but they are not my primary concern for this code.

import enchant
from functools import total_ordering
from string import ascii_lowercase

@total_ordering
class WordWithPath:
dictEng = enchant.Dict("en_US")

def __init__(self, newWord, ancestor = None):
self.word = newWord
if ancestor == None:
self.path = []
else:
self.path = [ancestor.word] + ancestor.path
def __eq__(self, other):
if (other == None):
return False
return (self.word == other.word)
def __lt__(self, other):
return (self.word < other.word)

#for the result outputting
def concatenatePath(self, rhs):
result = [self.path[i] for i in range(len(self.path)-1, -1, -1)] + [self.word] + rhs.path
return result

@staticmethod
def checkWord(w):
return WordWithPath.dictEng.check(w)

#find all words that are 1 letter different
def findNextWords(self):
w = self.word #a shortcut
result = []
# all words before w
for pos in range(len(w)):
originalLetter = w[pos]
for c in ascii_lowercase:
w = w[:pos] + c + w[pos+1:]
if c == originalLetter:
break
if WordWithPath.dictEng.check(w):
result.append(WordWithPath(w, self))

for pos in range(len(w)-1, -1, -1):
originalLetter = w[pos]
for c in ascii_lowercase:
if c <= originalLetter:
continue
w = w[:pos] + c + w[pos+1:]
if WordWithPath.dictEng.check(w):
result.append(WordWithPath(w, self))
w = w[:pos] + originalLetter + w[pos+1:]

return result

def mergeSortedLists(list1, list2):
i1 = 0; i2 = 0
result = []
while (True):
if (i1 < len(list1)) and (i2 < len(list2)):
if (list1[i1] < list2[i2]):
result.append(list1[i1]); i1 = i1+1
else:
result.append(list2[i2])
if (list1[i1] == list2[i2]): # avoid duplicates
i1 = i1+1
i2 = i2+1
continue
elif (i1 < len(list1)):
result += list1[i1:]
elif (i2 < len(list2)):
result += list2[i2:]
return result

def mergeManySortedLists(allLists):
if len(allLists) == 0:
return []
if len(allLists) == 1:
return allLists[0]
i = 0
newAllLists = []
while (2*i) < len(allLists):
if (2*i+1) < len(allLists):
newAllLists.append(mergeSortedLists(allLists[2*i], allLists[2*i+1]))
else:
newAllLists.append(allLists[2*i])
i = i+1
allLists = []# clear memory
return mergeManySortedLists(allLists = newAllLists)

def findOverlaps(list1, list2):
result = []
i1 = 0; i2 = 0
while (i1 < len(list1)) and (i2 < len(list2)):
if (list1[i1] == list2[i2]):
result.append((list1[i1], list2[i2]))
i1 = i1+1; i2 = i2+1
elif (list1[i1] < list2[i2]):
i1 = i1+1
else:
i2 = i2+1
return result

def removeOverlaps(listToClean, listReference):
i1 = 0; i2 = 0
while (i1 < len(listToClean)) and (i2 < len(listReference)):
if (listToClean[i1] == listReference[i2]):
del listToClean[i1]
i2 = i2+1
elif (listToClean[i1] < listReference[i2]):
i1 = i1+1
else:
i2 = i2+1

def findChain(leftWord, rightWord, maxTreeDepth):
errors = ''
if len(leftWord) != len(rightWord):
errors = ("Lengths of the left word, '" + leftWord
+ "', and the right word, '" + rightWord + "' do not match. ")
if not WordWithPath.checkWord(leftWord):
errors += "Left word, '" + leftWord + "', is not in the dictionary. "
if not WordWithPath.checkWord(rightWord):
errors += "Right word, '" + rightWord + "', is not in the dictionary. "
if errors != '':
raise ValueError(errors)
if (leftWord == rightWord):
return [WordWithPath(leftWord), WordWithPath(rightWord)]

leftAllNodes = [WordWithPath(leftWord)]; leftLeaves = [WordWithPath(leftWord)]
rightAllNodes = [WordWithPath(rightWord)]; rightLeaves = [WordWithPath(rightWord)]
for _ in range(maxTreeDepth):
newLeftLeaves = mergeManySortedLists([w.findNextWords() for w in leftLeaves])
leftAllNodes = mergeSortedLists(leftLeaves, leftAllNodes)
removeOverlaps(listToClean = newLeftLeaves, listReference = leftAllNodes)
leftLeaves = newLeftLeaves
overlaps = findOverlaps(leftLeaves, rightLeaves)
if len(overlaps)>0:
break

newRightLeaves = mergeManySortedLists([w.findNextWords() for w in rightLeaves])
rightAllNodes = mergeSortedLists(rightLeaves, rightAllNodes)
removeOverlaps(listToClean = newRightLeaves, listReference = rightAllNodes)
rightLeaves = newRightLeaves
overlaps = findOverlaps(leftLeaves, rightLeaves)
if len(overlaps)>0:
break

return [h1.concatenatePath(h2) for h1, h2 in overlaps]

if __name__ == '__main__':
allPaths = findChain("rough", "poach", 10)
for p in allPaths:
print p
allPaths = findChain("man", "spa", 10)
for p in allPaths:
print p
allPaths = findChain("tree", "fled", 10)
for p in allPaths:
print p
allPaths = findChain("ree", "fled", 10)
for p in allPaths:
print p
allPaths = findChain("zree", "fled", 10)
for p in allPaths:
print p

• Could you link to the challenge description for the word morph solver? – Ethan Bierlein Jul 5 '15 at 20:22
• @EthanBierlein: added the challenge description with some examples – Yulia V Jul 5 '15 at 20:29

## 2 Answers

A few style comments first, and then onto the algorithm:

• originalLetter, and similarly named items should named like original_letter rather than how you've named them.
• Functions like mergeSortedList 'should be lowercase, with words separated by underscores as necessary to improve readability', as dictated by PEP8, Python's official style guide.
• i1 should be named something more descriptive, like item_1
• i1 = 0; i2 = 0: using semicolons are not Pythonic and should be avoided, at all costs.
• if (2*i+1) 'you should have a single space in this expression': (2*i + 1)
• elif (i1 < len(list1)): Why do you wrap all of that in a bracket, but not if (2*i+1) < len(allLists):, either is fine, just stick with a complete standard throughout.
• i1 = i1+1: you can use the += modifier rather than referencing the variable: item_1 += 1
• i2 = i2+1: same as above: item_2 += 1
• if errors != '':: you can use a negative expression with not: if not errors:
• if ancestor == None:: same as above: if not ancestor:
• if (other == None): same as above: if not other:
• if len(overlaps)>0:: should have more whitespace: if len(overlaps) > 0:, but as @JoeWallis pointed out in the comments: PEP8 explicitly says this if len(overlaps) > 0: should be if overlaps:.
'For sequences, (strings, lists, tuples), use the fact that empty sequences are false'

What you're trying to solve for is called the .

In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

[Source]

And, as it seems, Python has a Levenshtein Distance package.

That may be worth looking over, to improve your algorithm.

Or even, Wikipedia's examples, which have varying examples, as well as a Python example.

if ancestor == None:


The part == None is unnecessary and adds noise to your code. Since None is a falsey value, just checking for the opposite of it will result in True if it equal to None.

Here is what I mean:

if not ancestor:


i2 = i2+1


Statements like this could be shortened to:

i2 += 1


In findChain, when you are adding errors to errors, split the errors up by newline so if the error message is viewed later, the different errors are more easily visible.

if errors != '':
raise ValueError(errors)


This can be simplified to

if errors:
raise ValueError(errors)


Which just makes more sense as your are reading it ("If [there are] errors").

Don't do this:

result.append(list1[i1]); i1 = i1+1


Semicolons are not very pythonic at all.

When you are brute-forcing words in findNextWords, you could probably speed up your algorithm by following some English rules.

One of the biggest and most known English rules is that every word must have a vowel.

Then, in findNextWords, you can setup a simple conditional that checks if a word has at least one vowel. If so, then it is a valid word.

Try to implement some other, lesser known English rules too. I'm sure you can find plenty here.

I might add more as I try to look more into the algorithm.

• Thanks! What about the algo? – Yulia V Jul 5 '15 at 20:30
• @YuliaV Yes. Sorry, I was really short on time and I didn't have time to review the algorithm. I will look at that now. – SirPython Jul 5 '15 at 21:06