CODEWITHSUNDEEP
pythonlistloopsrecursionappend
Unknown
Unknown

Reputation: 676

Recursion and appending to lists

I'm having trouble with a program, the program takes one word, and changing one letter at a time, converts that word into the target word. Although, keep in mind that the converted word must be a legal word according to a dictionary of words that I've been given.

I'm having trouble figuring out how to make it recursive. The program has a limit to the amount of steps it must take.

The output needs to be a list. So if the parameters for the function changeling are
changeling("find","lose"), the output should be: ['find','fine','line','lone','lose'].

with my current code:

def changeling(word,target,steps):
holderlist=[]
i=0
if steps<0 and word!=target:
    return None

if steps!=-1:
    for items in wordList:
        if len(items)==len(word):
            i=0

            if items!=word:
                for length in items:

                    if i==1:
                        if items[1]==target[1] and items[0]==word[0] and items[2:]==word[2:]:
                            if items==target:
                                print "Target Achieved"
                                holder.list.append(target)
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i>0 and i<len(word)-1 and i!=1:
                        if items[i]==target[i] and items[0:i]==word[0:i] and items[i+1:]==word[i+1:]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i==0:
                        if items[0]==target[0] and items[1:]==word[1:]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))


                    elif i==len(word)-1:
                        if items[len(word)-1]==target[len(word)-1] and items[0:len(word)-1]==word[0:len(word)-1]:
                            if items==target:
                                print "Target Achieved"
                            holderlist.append(items)
                            holderlist.append(changeling(items,target,steps-1))

                    else:
                        return None

                    i+=1

return holderlist

I receive a messy output: ['fine', ['line', ['lone', ['lose', []]]], 'fond', []]

I get the answer I wanted, but I'm not sure how to a)clean it up, by not having lists within lists. and b)fond appears, because when find is called it gives fine and fond, fine is the one that ends up with the target word, and fond fails, but I'm not sure how to get rid of it once I've appended it to the holderlist.

Any help would be appreciated.

Cheers.

Upvotes: 4

Views: 6498

Answers (3)

hexparrot
hexparrot

Reputation: 3417

Here's an alternative implementation. It doesn't use recursion, but instead permutations. It's been rewritten to pass the wordlist rather than rely on the global wordlist, which should make it more portable. This implementation relies strictly on generators, too, which ensures a smaller memory footprint than expanding lists (as in the extend/append solution)

import itertools

somelists = [['find','fine','line','lone','lose'],
            ['bank','hank','hark','lark','lurk'],
            ['tank','sank','sink','sing','ding']]

def changeling(word, target, wordlist):
    def difference(word, target):
        return len([i for i in xrange(len(word)) if word[i] != target[i]])

    for length in xrange(1, len(wordlist) + 1):
        for possibilities in [j for j in itertools.permutations(wordlist, length) if j[0] is word and j[-1] is target]:
            #computes all permutations and discards those whose initial word and target word don't match parameters
            if all(difference(possibilities[i], possibilities[i+1]) == 1 for i in xrange(0, len(possibilities) - 1)):
                #checks that all words are exactly one character different from previous link
                return possibilities
                #returns first result that is valid; this can be changed to yield if you wish to have all results

for w in somelists:
    print "from '%s' to '%s' using only %s" % (w[-2], w[0], w)
    print changeling(w[-2], w[0], w)
    print

w[-2], w[0] can be modified/replaced to match any words you choose

Upvotes: 1

Andrew Clark
Andrew Clark

Reputation: 208405

I'm not completely convinced that using extend instead of append will solve all your problems, because it seems like that may not account for making a change that does not lead to solving the word and requires backtracking.

If it turns out I am correct and the other answers don't end up working, here is a recursive function that will convert your current result into what you are looking for:

def flatten_result(nested_list, target):
    if not nested_list:
        return None
    for word, children in zip(nested_list[::2], nested_list[1::2]):
        if word == target:
            return [word]
        children_result = flatten_result(children, target)
        if children_result:
            return [word] + children_result
    return None

>>> result = ['fine', ['line', ['lone', ['lose', []]]], 'fond', []]
>>> flatten_result(result, 'lose')
['fine', 'line', 'lone', 'lose']

Upvotes: 3

Mark Ransom
Mark Ransom

Reputation: 308111

If you're trying to add a list to a list, you probably want extend rather than append.

http://docs.python.org/library/stdtypes.html#mutable-sequence-types

Upvotes: 3

Related Questions