多级凯撒密码

Question

嘿，我正在尝试解码一个多层次的凯撒密码。简单来说，就是一串字母可能被多次移动，比如我说 apply_shifts[(2,3),(4,5)]，这意味着我先把第2个字母往后移动3位，然后再把第4个字母往后移动5位。以下是我目前的代码。

def find_best_shifts_rec(wordlist, text, start):
    """
    Given a scrambled string and a starting position from which
    to decode, returns a shift key that will decode the text to
    words in wordlist, or None if there is no such key.

    Hint: You will find this function much easier to implement
    if you use recursion.

    wordlist: list of words
    text: scambled text to try to find the words for
    start: where to start looking at shifts
    returns: list of tuples.  each tuple is (position in text, amount of shift)
    """

    for shift in range(27):
        text=apply_shifts(text, [(start,-shift)])
        #first word is text.split()[0]
        #test if first word is valid.  if not, go to next shift

        if is_word(wordlist,text.split()[0])==False:
            continue

        #enter the while loop if word is valid, otherwise never enter and go to the next shift
        i=0
        next_index=0
        shifts={}
        while is_word(wordlist,text.split()[i])==True:
            next_index+= len(text.split()[i])
            i=i+1
            #once a word isn't valid, then try again, starting from the new index.
            if is_word(wordlist,text.split()[i])==False:
                shifts[next_index]=i
                find_best_shifts_rec(wordlist, text, next_index)

    return shifts

我遇到的问题是

1) 我的代码运行不正常，我不明白为什么会出错（它没有进入我的循环），还有

2) 我不知道怎么检查我的“最终移动”（比如字符串的最后一部分）是否都是有效的单词，也不知道怎么从那里回到我的循环开始的地方。

如果能得到帮助，我会非常感激。

Answer 1

递归函数的伪代码：

coded_text = text from start-index to end of string
if length of coded_text is 0, return "valid solution (no shifts)"

for shift in possible_shifts:
    decoded_text = apply shift of (-shift) to coded_text
    first_word = split decoded_text and take first piece
    if first_word is a valid word:
        rest_of_solution = recurse on (text preceding start-index)+decoded_text, starting at start+(length of first_word)+1
        if rest_of_solution is a valid solution
            if shift is 0
                return rest_of_solution
            else
                return (start, -shift mod alphabet_size) + rest_of_solution

# no valid solution found
return "not a valid solution"

请注意，这个方法保证能得到由有效单词组成的答案——但不一定是原来的字符串。举个具体的例子：'a add hat' 可以替代 'a look at' 被解码。

Answer 2

我觉得问题在于你总是处理整个文本，但在文本的某个位置开始应用（新的）偏移。所以你的检查 is_word(wordlist,text.split()[0]) 会 总是 检查第一个单词，而这个单词当然是在你第一次偏移之后的。

你需要做的是在新的起点之后获取第一个单词，也就是检查文本中实际上还没有处理的部分。

编辑

我注意到的另一个问题是你尝试找到正确偏移的方式：

for shift in range(27):
    text=apply_shifts(text, [(start,-shift)])

所以你基本上想尝试从 0 到 26 的所有偏移，直到第一个单词被接受。这样做是可以的，但要注意，在第一次尝试偏移后，文本已经改变。因此，你并不是在按 1, 2, 3, ... 进行偏移，而是按 1, 3, 6, 10, ... 进行偏移，这显然不是你想要的，而且你在做一些相同的偏移时会漏掉一些。

所以你需要 暂时 偏移你的文本，并检查这个临时文本的状态，然后再继续处理文本。或者，另外一种方法是你始终按 1 进行偏移。

编辑²

我还注意到的另一个问题是你尝试使用递归来得到最终结果的方式。通常，递归（带有结果）是通过不断调用函数本身并传递返回值，或者 收集 结果来工作的。在你的情况下，因为你想要多个值，而不仅仅是从某个地方得到一个单一的值，所以你需要收集每个偏移的结果。

但现在，你把递归调用的返回值丢掉了，只返回最后一个值。所以要保存所有的值，确保你不会丢失它们。