Recursion and adding to lists

I am having problems with the program, the program takes one word and changes one letter at a time, converts that word to the target word. Though, keep in mind that the converted word must be a legal word according to the dictionary of words I was given.

I am having a hard time figuring out how to make this recursive. The program has a limit on the number of steps it must complete.

The output should be a list. So what if the parameters for the spoof function? substitute ("find", "lose"), the output should be: ['Find', 'beautiful', 'string', 'lonely', 'lose'].

with my current code:

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

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

            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"

                    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"

                    elif i==0:
                        if items[0]==target[0] and items[1:]==word[1:]:
                            if items==target:
                                print "Target Achieved"

                    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"

                        return None


return holderlist


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

I get the answer I wanted, but I'm not sure how to: a) clean it up without having any lists in lists. and b) love appears because when the find is called it gives the beautiful and beloved, the beautiful is what ends with the target word, and love fails, but I'm not sure how to get rid of it once I add this to list of holders.

Any help would be appreciated.



source to share

3 answers

I'm not entirely sure if using extend

instead append

will solve all of your problems, because it looks like it might not account for changes that don't resolve the word and require a return.

If it turns out that I'm right and the rest of the answers don't work, here is a recursive function that will convert your current result to 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']




If you're trying to add a list to a list, you probably want to extend

, not append




Here's an alternative implementation. It doesn't use recursion, but permutations instead. It has been rewritten to convey a wordlist rather than relying on a global wordlist to make it more portable. This implementation relies solely on generators, which also provides less memory than expanding lists (as in expanding / appending)

import itertools

somelists = [['find','fine','line','lone','lose'],

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)


w[-2], w[0]

can be changed / replaced according to whatever words you have chosen



All Articles