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

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

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

Подумайте об этом, вместо того, чтобы, как в моей первой программе, теперь я получаю несколько допустимых слов, кроме случаев, когда я делаю слово =foundword, это означает, что я заменяю предыдущее слово каждый раз. Именно поэтому я пытаюсь использовать 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)было бы лучше вызвать исключение, чем печатать что-то непонятное, без следа стека и без фатальной ошибки.

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