Question

In problem set 4, problem 5, I've tested my multilevel decoder on up to ten random scrambled words and it works, but when I run the fable through it, it seems to get caught in a loop. Any thoughts on how to debug are greatly appreciated. I'll post the code in a followup post since I can't seem to paste all of it here.

Answer 1

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)
"""
### TODO.

starts_shifts=[]

for shift in range(0, 27):
## print 'Shift:', shift
s = text[:start] + apply_coder(text[start:], build_encoder(shift))
## print 'Text from start:', s[start:]

search_section = s[start:]
if ' ' in search_section:
word = search_section[:search_section.find(' ')]
else:
word = search_section

word_plus_blank = word + ' '

if ' ' not in search_section:
if is_word(wordlist, word):
## print 'Word:', word
return [(start, shift)]
elif shift == 26:
return None

elif ' ' in search_section:
if is_word(wordlist, word):
## print 'Word:',word
new_start = start + len(word_plus_blank)
## print start
if find_best_shifts_rec(wordlist, s, new_start) != None:
starts_shifts = [(start, shift)] + find_best_shifts_rec(wordlist, s, new_start)
## print starts_shifts
## print word
return starts_shifts

elif shift == 26:
return None

Answer 2

First, the hint suggests this should be a recursive function. All things considered, are you sure that you're calling this function with a list for wordlist?

Answer 3

The function calls itself here:

if find_best_shifts_rec(wordlist, s, new_start) != None:
starts_shifts = [(start, shift)] + find_best_shifts_rec(wordlist, s, new_start)

so I think I implemented the recursion in a way that is consistent with hint. And worldlist is a list. I confirmed that via type(wordlist). Here's the whole code in case it's helpful:

# 6.00 Problem Set 4
#
# Caesar Cipher Skeleton
#
import string
import random
import numbers

WORDLIST_FILENAME = "words.txt"

# -----------------------------------
# Helper code
# (you don't need to understand this helper code)
def load_words():
"""
Returns a list of valid words. Words are strings of lowercase letters.

Depending on the size of the word list, this function may
take a while to finish.
"""
print "Loading word list from file..."
# inFile: file
inFile = open(WORDLIST_FILENAME, 'r', 0)
# line: string
line = inFile.readline()
# wordlist: list of strings
wordlist = line.split()
print " ", len(wordlist), "words loaded."
return wordlist

wordlist = load_words()

def is_word(wordlist, word):
"""
Determines if word is a valid word.

wordlist: list of words in the dictionary.
word: a possible word.
returns True if word is in wordlist.

Example:
>>> isis_word(WORDLIST_FILENAME, hello)_word(wordlist, 'bat') returns
True
>>> is_word(wordlist, 'asdf') returns
False
"""
word = word.lower()
word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
return word in wordlist

def random_word(wordlist):
"""
Returns a random word.

wordlist: list of words
returns: a word from wordlist at random
"""
return random.choice(wordlist)

def random_string(wordlist, n):
"""
Returns a string containing n random words from wordlist

wordlist: list of words
returns: a string of random words separated by spaces.
"""
return " ".join([random_word(wordlist) for _ in range(n)])

def random_scrambled(wordlist, n):
"""
Generates a test string by generating an n-word random string
and encrypting it with a sequence of random shifts.

wordlist: list of words
n: number of random words to generate and scamble
returns: a scrambled string of n random words


NOTE:
This function will ONLY work once you have completed your
implementation of apply_shifts!
"""
s = random_string(wordlist, n) + " "
shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']
return apply_shifts(s, shifts)[:-1]

def get_fable_string():
"""
Returns a fable in encrypted text.
"""
f = open("fable.txt", "r")
fable = str(f.read())
f.close()
return fable


# (end of helper code)
# -----------------------------------

#
# Problem 1: Encryption
#
def build_coder(shift):
"""
Returns a dict that can apply a Caesar cipher to a letter.
The cipher is defined by the shift value. Ignores non-letter characters
like punctuation and numbers.

shift: -27 < int < 27
returns: dict

Example:
>>> build_coder(3)
{' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
(The order of the key-value pairs may be different.)
"""
### TODO.

assert shift >= 0 and shift < 27, 'shift %s is not between 0 and 27' % shift
#numbers.Integral used in case of long integers
assert isinstance(shift, numbers.Integral), 'shift is not an integer'

coder = {}

lowercase_and_space = string.ascii_lowercase + ' '
uppercase_and_space = string.ascii_uppercase + ' '

# Shift letters over shift places
shifted_lowercase_and_space = lowercase_and_space[shift:] + lowercase_and_space[:shift]
shifted_uppercase_and_space = uppercase_and_space[shift:] + uppercase_and_space[:shift]

# Construct Caesar cipher dictionary
# Add uppercase letters first so ' ' will be overwritten to point to lowercase letter
for i in range(len(uppercase_and_space)):
coder[uppercase_and_space[i]] = shifted_uppercase_and_space[i]

for i in range(len(lowercase_and_space)):
coder[lowercase_and_space[i]] = shifted_lowercase_and_space[i]

return coder


def build_encoder(shift):
"""
Returns a dict that can be used to encode a plain text. For example, you
could encrypt the plain text by calling the following commands
>>>encoder = build_encoder(shift)
>>>encrypted_text = apply_coder(plain_text, encoder)

The cipher is defined by the shift value. Ignores non-letter characters
like punctuation and numbers.

shift: 0 <= int < 27
returns: dict

Example:
>>> build_encoder(3)
{' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
(The order of the key-value pairs may be different.)

HINT : Use build_coder.
"""
### TODO.

coder = build_coder(shift)

return coder

def build_decoder(shift):
"""
Returns a dict that can be used to decode an encrypted text. For example, you
could decrypt an encrypted text by calling the following commands
>>>encoder = build_encoder(shift)
>>>encrypted_text = apply_coder(plain_text, encoder)
>>>decrypted_text = apply_coder(plain_text, decoder)

The cipher is defined by the shift value. Ignores non-letter characters
like punctuation and numbers.

shift: 0 <= int < 27
returns: dict

Example:
>>> build_decoder(3)
{' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',
'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',
'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',
'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',
'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',
'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',
'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',
'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}
(The order of the key-value pairs may be different.)

HINT : Use build_coder.
"""
### TODO.

## decoder = build_coder(27-shift)

encoder = build_encoder(shift)
decoder = dict(zip(encoder.values(), encoder.keys()))


return decoder


def apply_coder(text, coder):
"""
Applies the coder to the text. Returns the encoded text.

text: string
coder: dict with mappings of characters to shifted characters
returns: text after mapping coder chars to original text

Example:
>>> apply_coder("Hello, world!", build_encoder(3))
'Khoor,czruog!'
>>> apply_coder("Khoor,czruog!", build_decoder(3))
'Hello, world!'
"""
### TODO.

caesar_text = ''

##For each letter add encoded value

for char in text:
if char in coder:
caesar_text += coder[char]
else:
caesar_text += char
## print caesar_text
## print ' '
## print coder

return caesar_text


def apply_shift(text, shift):
"""
Given a text, returns a new text Caesar shifted by the given shift
offset. The empty space counts as the 27th letter of the alphabet,
so spaces should be replaced by a lowercase letter as appropriate.
Otherwise, lower case letters should remain lower case, upper case
letters should remain upper case, and all other punctuation should
stay as it is.

text: string to apply the shift to
shift: amount to shift the text
returns: text after being shifted by specified amount.

Example:
>>> apply_shift('This is a test.', 8)
'Apq hq hiham a.'
"""
### TODO.
##
## coder = build_encoder(shift)
#### print coder
##
## encoded_text = apply_coder(text, coder)
## print encoded_text

encoded_text = apply_coder(text, build_encoder(shift))
## decoded_text = apply_coder(encoded_text, build_decoder(shift))
return encoded_text

#
# Problem 2: Codebreaking.
#
def find_best_shift(wordlist, text):
"""
Decrypts the encoded text and returns the plaintext.

text: string
returns: 0 <= int 27

Example:
>>> s = apply_coder('Hello, world!', build_encoder(8))
>>> s
'Pmttw,hdwztl!'
>>> find_best_shift(wordlist, s) returns
8
>>> apply_coder(s, build_decoder(8)) returns
'Hello, world!'
"""
### TODO

max_real_words = 0

best_shift = 0

shift = 1

while shift <27 :
decoded_text = apply_coder(text, build_decoder(shift))
word_list = string.split(decoded_text)
print shift
print word_list
real_words = 0
for word in word_list:
print word
print is_word(wordlist, word)
if is_word(wordlist, word) is True:
real_words += 1
if real_words > max_real_words:
max_real_words = real_words
best_shift = shift
shift +=1

print 'Maximum real words:', max_real_words
print 'Best shift:', best_shift
print 'Decoded message:', apply_coder(text, build_decoder(best_shift))

return best_shift
#
# Problem 3: Multi-level encryption.
#
def apply_shifts(text, shifts):
"""
Applies a sequence of shifts to an input text.

text: A string to apply the Ceasar shifts to
shifts: A list of tuples containing the location each shift should
begin and the shift offset. Each tuple is of the form (location,
shift) The shifts are layered: each one is applied from its
starting position all the way through the end of the string.
returns: text after applying the shifts to the appropriate
positions

Example:
>>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
"""
### TODO.

encoded_text = ''

encoded_text += text[0:shifts[0][0]]

print 'Start:', encoded_text

for item in range(len(shifts)):
print 'Item:', item
print 'Number of items:', len(shifts)
if item < (len(shifts)-1):
print 'Pre-encoded text:', text
text = apply_coder(text, build_encoder(shifts[item][1]))
print 'Postencoded text:', text
encoded_text += text[shifts[item][0]:shifts[item+1][0]]
print encoded_text
else:
print 'Pre-encoded text:', text
text = apply_coder(text, build_encoder(shifts[item][1]))
print 'Postencoded text:', text
encoded_text += text[shifts[item][0]:]
print encoded_text

print encoded_text

return encoded_text

#
# Problem 4: Multi-level decryption.
#


def find_best_shifts(wordlist, text):
"""
Given a scrambled string, returns a shift key that will decode the text to
words in wordlist, or None if there is no such key.

Hint: Make use of the recursive function
find_best_shifts_rec(wordlist, text, start)

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

Examples:
>>> s = random_scrambled(wordlist, 3)
>>> s
'eqorqukvqtbmultiform wyy ion'
>>> shifts = find_best_shifts(wordlist, s)
>>> shifts
[(0, 25), (11, 2), (21, 5)]
>>> apply_shifts(s, shifts)
'compositor multiform accents'
>>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
>>> s
'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
>>> shifts = find_best_shifts(wordlist, s)
>>> print apply_shifts(s, shifts)
Do Androids Dream of Electric Sheep?
"""
shifts = find_best_shifts_rec(wordlist, text, 0)
return apply_shifts(text, shifts)

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)
"""
### TODO.

starts_shifts=[]

for shift in range(0, 27):
## print 'Shift:', shift
s = text[:start] + apply_coder(text[start:], build_encoder(shift))
## print 'Text from start:', s[start:]

search_section = s[start:]
if ' ' in search_section:
word = search_section[:search_section.find(' ')]
else:
word = search_section

word_plus_blank = word + ' '

if ' ' not in search_section:
if is_word(wordlist, word):
## print 'Word:', word
return [(start, shift)]
elif shift == 26:
return None

elif ' ' in search_section:
if is_word(wordlist, word):
## print 'Word:',word
new_start = start + len(word_plus_blank)
## print start
if find_best_shifts_rec(wordlist, s, new_start) != None:
starts_shifts = [(start, shift)] + find_best_shifts_rec(wordlist, s, new_start)
## print starts_shifts
## print word
return starts_shifts

elif shift == 26:
return None




def decrypt_fable():

return find_best_shifts(wordlist, get_fable_string())

"""
Using the methods you created in this problem set,
decrypt the fable given by the function get_fable_string().
Once you decrypt the message, be sure to include as a comment
at the end of this problem set how the fable relates to your
education at MIT.

returns: string - fable in plain text
"""
### TODO.







#What is the moral of the story?
#
#
#
#
#

Answer 4

After some more debugging and adding a "print s" statement under " s = text[:start] + apply_coder(text[start:], build_encoder(shift))", I realized that the function is actually decoding the entire fable but then jumping back to the second to last word and decoding the last two words in an infinite loop I'm not sure why the base case isn't returning [start, shfit].

Answer 5

Try printing the values tested for the base case just before the testing.

Answer 6

Good idea. I tried that and the value tested is exactly what I expect: the final word with no space at the end. I'm stumped. I figured that putting the recursive call in the return statement would just return the shift/start starting with the last word and moving backward through the text but clearly I've introduced an endless loop that I can't find.

Answer 7

The recursive call is part of an if statement. Technically, yes this is recursion, but usually, the entire function is recursive.

Answer 8

I set it up that way to make sure that the function returns valid words all the way to the last word before returning any shift/start info and doesn't just accept the first valid word it finds. I read the pseudocode that MIT provided for this problem and this was the only way to implement it I thought of. If there's a better algorithm I'm happy to try to code it.