Word Morph (changing one letter at a time)

Question

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

Answer 1

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 levenshtein-distance.

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.

Answer 2

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.