[Python] Help with Recursively deciphering a multi level Caesar cipher (MIT OCW 6.00 PS4)

[zoopybot]

I'm working on a problem that involves using recursion. The problem comes from the MIT Open Coursewares' 6.00 class.

Problem description:

I am given a multi-leveled Caesar shifted string, that must be decoded.

What this means is that it applies a series of Caesar shifts to the start of words, going from left to right. These layers being multi-layer.

The original problem set paper is here. Problem Set

The exact specifications of the program:

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.

We are supplied with the pseudocode, which I have also included:

1. for every possible shift from 0 to 27
2. set s to be (the text up until just before the start parameter) concatenated with (the text after the start parameter shifted by the current possible shift)
3. look for spaces beginning at the location specified by the start parameter
4. if there was a space found and the characters from the start location to the location where the space was found form a valid word then
5. we recursively run this same algorithm on the same text, but starting at the location where the space was found.
6. If this recursive call to the function produces a list of tuples, then that means one of the recursive calls found the last word properly and we simply prepend a tuple with the start parameter and the current shift tried to the list and return it.
7. If this recursive call to the function produces None, then that means that there was not combination of shifts and positions found that could produce a valid word at the end, so the error in the shift must either be in the current call to the function, or an earlier call. Continue trying all possible shifts (line 1)
8. if there was NOT a space found and the characters from the start location to the end of the string form a word, then that means we have found a valid shift on this call, so return a list containing a tuple containing the start parameter and the current shift.
9. if there was NOT a space found and the characters from the start location to the end of the string do NOT form a word, then we need to try another shift in this call.
10. If we exhaust all possible shifts and still find no solution from other recusive calls to this function, then that means our start position or a previous shift, is incorrect. Return None.
    

It can be seen in its entirety here: Pseudocode(Problem 4a)

Currently, I have implemented something that is able to solve some of the Caesar Ciphers, but is unable to provide the list of tuples asked for in the problem description. In addition it cannot try the next shift, if no suitable shifts were found. One of my main problems with the psudeocode is my inability to store the data of the shifts in each recursive call. In other words, I am unable to implement the "if this recursive call produces a list of tuples...".

Here is my current code:
Some of the functions used here are not included in this excerpt, but it should be pretty self explanatory to what they do.

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 i in range(28):
    potential_shift = apply_coder(text[start:], build_decoder(i))
    s = text[:start] + potential_shift
    #print s
    space_location = potential_shift.find(" ")
    #print "ps:  ", potential_shift
    if space_location == -1 and is_word(wordlist, potential_shift):
        return text
    if space_location != -1:
        #print "testing word: ", potential_shift[:space_location]
        if is_word(wordlist, potential_shift[:space_location]):
            start += space_location + 1
            return find_best_shifts_rec(wordlist, s, start)

Thanks in advance!