The Alphabet and Recursion

Question

I'm almost done with my program, but I've made a subtle mistake. My program is supposed to take a word, and by changing one letter at a time, is eventually supposed to reach a target word, in the specified number of steps. I had been trying at first to look for similarities, for example: if the word was find, and the target word lose, here's how my program would output in 4 steps:

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

Which is actually the output I wanted. But if you consider a tougher set of words, like Java and work, the output is supposed to be in 6 steps.

['java', 'lava', 'lave', 'wave', 'wove', 'wore', 'work']

So my mistake is that I didn't realize you could get to the target word, by using letters that don't exist in the target word or original word.

Here's my Original Code:

import string
def changeling(word,target,steps):
    alpha=string.ascii_lowercase
    x=word##word and target has been changed to keep the coding readable.
    z=target
    if steps==0 and word!= target:##if the target can't be reached, return nothing.
        return []
    if x==z:##if target has been reached.
        return [z]


    if len(word)!=len(target):##if the word and target word aren't the same length print error.
        print "error"
        return None
    i=1
    if lookup
    if lookup(z[0]+x[1:]) is True and z[0]+x[1:]!=x :##check every letter that could be from z, in variations of, and check if they're in the dictionary.
        word=z[0]+x[1:]
    while i!=len(x):
        if lookup(x[:i-1]+z[i-1]+x[i:]) and x[:i-1]+z[i-1]+x[i:]!=x:
            word=x[:i-1]+z[i-1]+x[i:]

        i+=1
    if lookup(x[:len(x)-1]+z[len(word)-1]) and x[:len(x)-1]+z[len(x)-1]!=x :##same applies here.
        word=x[:len(x)-1]+z[len(word)-1]


    y =  changeling(word,target,steps-1)
    if y :
      return [x] + y##used to concatenate the first word to the final list, and if the list goes past the amount of steps.
    else:
      return None

Here's my current code:

import string
def changeling(word,target,steps):
    alpha=string.ascii_lowercase
    x=word##word and target has been changed to keep the coding readable.
    z=target
    if steps==0 and word!= target:##if the target can't be reached, return nothing.
        return []
    if x==z:##if target has been reached.
        return [z]
    holderlist=[]


    if len(word)!=len(target):##if the word and target word aren't the same length print error.
        print "error"
        return None
    i=1
    for items in alpha:

        i=1
        while i!=len(x):
            if lookup(x[:i-1]+items+x[i:]) is True and x[:i-1]+items+x[i:]!=x:
                word =x[:i-1]+items+x[i:]
                holderlist.append(word)

            i+=1
        if lookup(x[:len(x)-1]+items) is True and x[:len(x)-1]+items!=x:
            word=x[:len(x)-1]+items
            holderlist.append(word)

    y =  changeling(word,target,steps-1)
    if y :
      return [x] + y##used to concatenate the first word to the final list, and if the/
   list goes past the amount of steps.
    else:
      return None

The differences between the two is that the first checks every variation of find with the letters from lose. Meaning: lind, fond, fisd, and fine. Then, if it finds a working word with the lookup function, it calls changeling on that newfound word.

As opposed to my new program, which checks every variation of find with every single letter in the alphabet.

I can't seem to get this code to work. I've tested it by simply printing what the results are of find:

for items in alpha:

        i=1
        while i!=len(x):
             print (x[:i-1]+items+x[i:])

             i+=1
        print (x[:len(x)-1]+items)

This gives:

aind
fand
fiad
fina
bind
fbnd
fibd
finb
cind
fcnd
ficd
finc
dind
fdnd
fidd
find
eind
fend
fied
fine
find
ffnd
fifd
finf
gind
fgnd
figd
fing
hind
fhnd
fihd
finh
iind
find
fiid
fini
jind
fjnd
fijd
finj
kind
fknd
fikd
fink
lind
flnd
fild
finl
mind
fmnd
fimd
finm
nind
fnnd
find
finn
oind
fond
fiod
fino
pind
fpnd
fipd
finp
qind
fqnd
fiqd
finq
rind
frnd
fird
finr
sind
fsnd
fisd
fins
tind
ftnd
fitd
fint
uind
fund
fiud
finu
vind
fvnd
fivd
finv
wind
fwnd
fiwd
finw
xind
fxnd
fixd
finx
yind
fynd
fiyd
finy
zind
fznd
fizd
finz

Which is perfect! Notice that each letter in the alphabet goes through my word at least once. Now, what my program does is use a helper function to determine if that word is in a dictionary that I've been given.

Consider this, instead of like my first program, I now receive multiple words that are legal, except when I do word=foundword it means I'm replacing the previous word each time. Which is why I'm trying holderlist.append(word).

I think my problem is that I need changeling to run through each word in holderlist, and I'm not sure how to do that. Although that's only speculation.

Any help would be appreciated,

Cheers.

Answer 1

I might be slightly confused about what you need, but by borrowing from this post I belive I have some code that should be helpful.

>>> alphabet = 'abcdefghijklmnopqrstuvwxyz'
>>> word = 'java'
>>> splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
>>> splits
[('', 'java'), ('j', 'ava'), ('ja', 'va'), ('jav', 'a'), ('java', '')]
>>> replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
>>> replaces
['aava', 'bava', 'cava', 'dava', 'eava', 'fava', 'gava', 'hava', 'iava', 'java', 'kava', 'lava', 'mava', 'nava', 'oava', 'pava', 'qava', 'rava', 'sava', 'tava', 'uava', 'vava', 'wav
a', 'xava', 'yava', 'zava', 'java', 'jbva', 'jcva', 'jdva', 'jeva', 'jfva', 'jgva', 'jhva', 'jiva', 'jjva', 'jkva', 'jlva', 'jmva', 'jnva', 'jova', 'jpva', 'jqva', 'jrva', 'jsva', '
jtva', 'juva', 'jvva', 'jwva', 'jxva', 'jyva', 'jzva', 'jaaa', 'jaba', 'jaca', 'jada', 'jaea', 'jafa', 'jaga', 'jaha', 'jaia', 'jaja', 'jaka', 'jala', 'jama', 'jana', 'jaoa', 'japa'
, 'jaqa', 'jara', 'jasa', 'jata', 'jaua', 'java', 'jawa', 'jaxa', 'jaya', 'jaza', 'java', 'javb', 'javc', 'javd', 'jave', 'javf', 'javg', 'javh', 'javi', 'javj', 'javk', 'javl', 'ja
vm', 'javn', 'javo', 'javp', 'javq', 'javr', 'javs', 'javt', 'javu', 'javv', 'javw', 'javx', 'javy', 'javz']

Once you have a list of all possible replaces, you can simply do

valid_words = [valid for valid in replaces if lookup(valid)]

Which should give you all words that can be formed by replacing 1 character in word. By placing this code in a separate method, you could take a word, obtain possible next words from that current word, and recurse over each of those words. For example:

alphabet = 'abcdefghijklmnopqrstuvwxyz'
def next_word(word):
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
    return [valid for valid in replaces if lookup(valid)]

Is this enough help? I think your code could really benefit by separating tasks into smaller chunks.

Answer 2

Fixed your code:

import string 
def changeling(word, target, steps): 
    alpha=string.ascii_lowercase 
    x = word  #word and target has been changed to keep the coding readable. 
    z = target 
    if steps == 0 and word != target:  #if the target can't be reached, return nothing. 
        return [] 
    if x == z:  #if target has been reached. 
        return [z] 
    holderlist = [] 


    if len(word) != len(target):  #if the word and target word aren't the same length print error. 
        raise BaseException("Starting word and target word not the same length: %d and %d" % (len(word), 
    i = 1 
    for items in alpha: 
        i=1
        while i != len(x): 
            if lookup(x[:i-1] + items + x[i:]) is True and x[:i-1] + items + x[i:] != x: 
                word = x[:i-1] + items + x[i:] 
                holderlist.append(word) 
            i += 1 
        if lookup(x[:len(x)-1] + items) is True and x[:len(x)-1] + items != x: 
            word = x[:len(x)-1] + items 
            holderlist.append(word) 

    y =  [changeling(pos_word, target, steps-1) for pos_word in holderlist] 
    if y: 
      return [x] + y  #used to concatenate the first word to the final list, and if the list goes past the amount of steps. 
    else: 
      return None

Where len(word) and len(target), it'd be better to raise an exception than print something obscure, w/o a stack trace and non-fatal.

Oh and backslashes(\), not forward slashes(/), are used to continue lines. And they don't work on comments