[Tutor] Algorithm

[Kent Johnson]

On Tue, Aug 25, 2009 at 5:03 PM, kreglet<kreglet at gmail.com> wrote:
>
> Hello Kent,
>
> Yes I would like to see your implementation. It seems to work but I get
> error at the end.
>
> concat=''.join
>
> mainword="python"
> cmpword="pot"
>  # sort the letters in the target word; for example 'python' becomes
> 'hnopty'
> tmplst=[]
> for letters in mainword:
>        tmplst.append(letters)

This can be written as
tmplst = list(mainword)

> tmplst.sort()

The above could be greatly simplified to
tmplst = sorted(mainword)

> mainword=concat(tmplst)

You don't really need to convert back to a string, the list would work fine.

> # sort the letters in the word you want to test, for example 'pot' becomes
> 'opt'
> tmplst=[]
> for letters in cmpword:
>        tmplst.append(letters)
>
> tmplst.sort()
> cmpword=concat(tmplst)

Same as above

> inword=False
> # walk through test letters looking for them in the target list.
> print cmpword, mainword
> for letter in range(len(cmpword)): #Test
>        for let in range(len(mainword)):#Target

You want to walk the two lists together. Nested loops is not the right
structure. Here is my version:

""" Find all words that can be made with the letters of a given word """

def contains(word, letters):
    ''' Test whether all letters of word are in letters.
        Letters must be a sorted list.'''
    letterIndex = 0;
    for letter in sorted(word):
        if letterIndex >= len(letters):
            # Ran out of letters
            return False

        while letter > letters[letterIndex] and letterIndex < len(letters) -1:
            # Skip letters that are too small
            letterIndex += 1

        if letter == letters[letterIndex]:
            # A match, keep checking
            letterIndex += 1
            continue

        # No match for current letter
        return False

    return True


def findWordsIn(targetWord, minLen=3):
    letters = sorted(targetWord)

    for word in open('/usr/share/dict/words'):
        word = word.strip()

        if len(word) < minLen:
            continue

        if contains(word, letters):
            print word

findWordsIn('python', 3)

Prints:
hop
hot
hoy
hyp
hypo
not
noy
nth
opt
pho
phon
phony
phot
phyton
poh
pon
pont
pony
pot
poy
python
tho
thon
thy
ton
tony
top
toph
toy
typo
yon
yont
yot

Kent