Caesar Cipher Recursion

Question

I am attempting to finish a problem involving decoding a string of text encoded with multiple levels of a Caesar cipher. It seems to work for the first shift by returning Do but it will not recurse. I have print statements throughout showing the snippets I am using and putting into the functions and they seem to be correct.

def build_decoder(shift):
    cipher = build_coder(shift)
    decoder = {}
    for k, v in cipher.items():
        decoder[v] = k
    return decoder

def is_word(wordlist, word):
    word = word.lower()
    word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
    return word in wordlist

def apply_coder(text, coder):
    encrypted = []
    for character in text:
        if character in coder.keys():
            encrypted.append(coder[character])
        else:
            encrypted.append(character)
    return ''.join(encrypted)

def apply_shift(text, shift):
    coder = build_coder(shift)
    return apply_coder(text, coder)

def apply_shifts(text, shifts):
    for index, shift in shifts:
        text = (text[:index]) + (apply_coder(text[index:], build_coder(shift)))
    return text

def find_best_shifts_rec(wordlist, text, start=0):
            """
            text: scrambled 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)
            """
            key = []
            for shift in range(28):
                message = text[:start] + apply_shift(text[start:], -shift) #Concatenate text from beginning to start with an apply_shift from start to end of text.
                space = message[start:].find(" ") #Find next space from start to " " character.
                if is_word(wordlist, message[start:space]): #If text from start to space is a word.
                    print message[start:space]
                    key.append((start, shift)) #Add position and shift as tuple in list key.
                    print key
                    print len(message[:start]), message[:start]
                    print len(message[start:space]), message[start:space]
                    print len(message), message
                    print message[:space]
                    print message[space+1:]
                    print message[space+1]
                    if not(is_word(wordlist, message[start:])):
                        return message[:space] + find_best_shifts_rec(wordlist, message, space+1) #Return text from beginning to space(decrypted) and recursively call find_best_shifts_rec on rest of text.
                    else:
                        return message[start:]
            print "No shift match found, closest match:"
            print key
            return ''

s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
print find_best_shifts_rec(wordlist, s)

Output:

Do
[(0, 6)]
0 
2 Do
36 Do Sevif vjrKylhtgvmgLslj ypjgZollw?
Do
Sevif vjrKylhtgvmgLslj ypjgZollw?
S
No shift match found, closest match:
[]
Do

What do you mean "multiple levels of Caesar cipher"? You are aware that for repeated encryption with Caesar that you can simply revert multiple levels to one level by adding the keys together, right? Heck, you could even invert the encryption, returning you the plaintext. — Maarten Bodewes
Well it doesn't apply the encryption to the entire string. If you look at apply_shifts it takes a tuple of the index to start the encryption at and the shift. The bottom line is encoding it using the given list of tuples. My problem function find_best_shifts_rec is supposed to recursively generate that same tuple basically. — Jordan

frank S frank S · Accepted Answer · 2016-05-17T02:54:31

I assume this is for the MIT 6.00 Course? I wrote a working find_best_shifts and find_best_shifts_rec. This is my first experience coding so I'm sure my code can be improved, but it does work, so you might be able to use it as a baseline to improve upon.

def find_best_shifts(wordlist, text): global shifts shifts = [] return find_best_shifts_rec(wordlist, text, 0)

def find_best_shifts_rec(wordlist, text, start):

for shift in range(28):
        decoded = apply_shift(text[start:], shift)
        words = decoded.split()
        decoded = text[:start] + decoded
        string_split = decoded.split()
        size = len(string_split)
        correct_words = 0
        if is_word(wordlist, words[0]):
            if shift != 0:
                shifts.append((start,shift))
                new_start = start + len(words[0]) + 1
                if new_start >= len(text)-1:
                       return shifts
                else:
                    return find_best_shifts_rec(wordlist, decoded, start=new_start)
        for j in string_split:
            if is_word(wordlist, j):
                correct_words += 1
                if correct_words == size:
                    return shifts

Caesar Cipher Recursion

2 Answers