Азбука и рекурсия

Question

Я почти закончил свою программу, но совершил небольшую ошибку. Моя программа должна принимать слово, и, меняя одну букву за раз, в конечном итоге должна достичь целевого слова за указанное количество шагов. Сначала я пытался найти сходство, например: если слово было найдено, а целевое слово потеряно, вот как моя программа выдаст 4 шага:

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

Какой именно вывод я хотел. Но если учесть более сложный набор слов, таких как Java и работа, вывод должен состоять из 6 шагов.

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

Так что моя ошибка в том, что я не осознавал, что вы можете добраться до целевого слова, используя буквы, которых нет в целевом слове или оригинальном слове.

Вот мой оригинальный код:

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

Вот мой текущий код:

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

Различия между ними в том, что первый проверяет каждую вариацию находки с буквами проиграть Значение: lind, fond, fisd и штраф. Затем, если он находит рабочее слово с помощью функции поиска, он вызывает замену этого нового слова.

В отличие от моей новой программы, которая проверяет каждую вариацию поиска с каждой буквой алфавита.

Я не могу заставить этот код работать. Я проверил это, просто распечатав результаты поиска:

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)

Это дает:

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

Что идеально! Обратите внимание, что каждая буква в алфавите проходит через мое слово хотя бы один раз. Теперь моя программа использует вспомогательную функцию, чтобы определить, находится ли это слово в словаре, который мне дали.

Учтите, что вместо моей первой программы я теперь получаю несколько допустимых слов, кроме случаев, когда я делаю слово = найденное слово, это означает, что я заменяю предыдущее слово каждый раз. Именно поэтому я пытаюсь использовать holderlist.append (word).

Я думаю, что моя проблема в том, что мне нужно переодевание, чтобы пробежаться по каждому слову в списке владельцев, и я не уверен, как это сделать. Хотя это только предположение.

Любая помощь будет оценена,

Приветствие.

Answer 1

Я могу быть немного озадачен тем, что вам нужно, но, позаимствовав у этот пост Я верю, у меня есть код, который должен быть полезен.

>>> 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']

Когда у вас есть список всех возможных замен, вы можете просто сделать

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

Что должно дать вам все слова, которые могут быть образованы путем замены 1 символа в слове. Поместив этот код в отдельный метод, вы можете взять слово, получить возможные последующие слова из этого текущего слова и выполнить повторение по каждому из этих слов. Например:

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)]

Этого достаточно, чтобы помочь? Я думаю, что ваш код мог бы выиграть, разделив задачи на более мелкие куски.

Answer 2

Исправил ваш код:

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

Где len(word) и len(target), было бы лучше вызвать исключение, чем печатать что-то неясное, без следа стека и без фатального исхода.

Oh и обратные косые черты (\), а не прямые косые черты (/), используются для продолжения линий.И они не работают над комментариями