Question

ps4 multilevel description finally solved.. but how to implement recursion....

Answer 1

# 6.00 Problem Set 4
#
# Caesar Cipher Skeleton
#
import string
import random
from collections import deque

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')
# line: string
line = inFile.readline()
# wordlist: list of strings
wordlist = line.split()
print (" ", len(wordlist), "words loaded.")
inFile.close()
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:
>>> is_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 scramble
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_encoders(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_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.
"""
encoder = {}

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

shifted_lowercase_and_space = lowercase_and_space[shift:] + lowercase_and_space[:shift]
shifted_uppercase_and_space = uppercase_and_space[shift:] + uppercase_and_space[:shift]

for i in range(len(uppercase_and_space)):
encoder[uppercase_and_space[i]] = shifted_uppercase_and_space[i]

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

return encoder


def apply_encoder(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_encoder('This is a test.', 8)
'Apq hq hiham a.'
"""
ciphertext = ''
encoder = build_encoder(shift)

for letter in text:
if letter in encoder:
ciphertext += encoder[letter]
else:
ciphertext += letter

return ciphertext


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.
"""
encoder = build_encoder(shift)
decoder = dict(zip(encoder.values(), encoder.keys()))

return decoder


def apply_decoder(text, shift):

plaintext = ""
decoder = build_decoder(shift)

for letter in text:
if letter in decoder:
plaintext += decoder[letter]
else:
plaintext += letter

return plaintext


#
# 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!'
"""

cipher = []
plaintext = ""

for i in range(27):
plaintext += apply_decoder(text, i)
words_in_plaintext = plaintext.split()
count = 0
for word in words_in_plaintext:
if is_word(wordlist, word):
count += 1
cipher.append(count)

shift = cipher.index(max(cipher))

return shift


#
# Problem 3: Multi-level encryption.
#
def apply_encoders(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_encoders("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
"""

cipher_text = ''

places = [x[0] for x in shifts]
places.append(len(text))
encoders = [x[1] for x in shifts]

total_encoders = [0]
for i in range(len(encoders)):
total_encoders.append((total_encoders[i]+encoders[i])%27)
del total_encoders[0]

for i in range(len(total_encoders)):
cipher_text += apply_encoder(text, total_encoders[i])[places[i]:places[i+1]]

return cipher_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_encoders(s, shifts)
'compositor multiform accents'
>>> s = apply_encoders("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
>>> s
'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
>>> shifts = find_best_shifts(wordlist, s)
>>> print (apply_encoders(s, shifts))
Do Androids Dream of Electric Sheep?
"""

decryption = []
decoders = []
places = [0]
total_shifts = []
counter = 0
i_range = list(range(27))

# while text[places[len(places)-1]:] != '':
# keys, deciphered = find_possible_shift(text[places[len(places)-1]:])
# i_range = len(keys)
#
# for i in i_range:
# shifts.append(keys[i])
# decryption.append(deciphered[i])

while len(text[places[-1]:]) > 0:

for i in i_range:
place = 0
plaintext = apply_decoder(text[places[-1]:], i)
words_in_plaintext = plaintext.split() # decrypted words separate by ' '

for word in words_in_plaintext:
if is_word(wordlist, word):
counter = 0
i_range = list(range(27))
decryption.append(word) # get decrypted words
place += len(word) + 1 # get length of decrypted words+' '
else:
counter += 1
if counter > 26:
i_range.remove(decoders[-1])
del decoders[-1]
del places[-1]
del decryption[-1]
counter = 0
break
else:
break

if place != 0:
places.append(places[-1]+place) # get positions for write diff shifts
decoders.append(i) # the shifts

del places[-1]
j = [0]
positions = j + decoders

for i in range(1, len(positions)):
x = (positions[i] - positions[i-1])
if x >= 0:
total_shifts.append(x)
else:
total_shifts.append(27+x)

best_decoders = list(zip(places, total_shifts))
print("decryption:", ' '.join(decryption))
print("best_decoders:", best_decoders)

return best_decoders


def decrypt_fable():

return find_best_shifts(wordlist, get_fable_string())



# -----------------------------------------------------------
# print()
# s = 'This is a test.'
# s_cipher = apply_encoder(s, 8)
# print(s_cipher)
# print(apply_decoder(s_cipher, 8))
# # 'Apq hq hiham a.'
#
# print()
# b = 'Hello, world!'
# b_cipher = apply_encoder(b, 3)
# print(b_cipher)
# print(apply_decoder(b_cipher, 3))
# #'Khoor,czruog!'
#
# print()
# f = 'What are you doing? I think I like ice-cream.'
# f_cipher = apply_encoder(f, 7)
# print(f_cipher)
# t = 'Coh ghylgevagkvpun?gPg opurgPgsprlgpjl-jylht.'
# cipher = find_best_shift(wordlist, t)
# print(cipher)
# print(apply_decoder(t, cipher))
#
# # print()
# c = "Do Androids Dream of Electric Sheep?"
# # print('length c = ', len(c))
# print(c)
# c_cipher = apply_encoders(c, [(0,6), (3, 18), (12, 16)])
# # 'JufSevif vjrTguqbpdvpUausigyspHxuue?'
# print(c_cipher)
# #
# print(find_best_shifts(wordlist, c_cipher))
#

# s = random_scrambled(wordlist, 80)
# print("s:", s)
# print('length of s:', len(s))
# shifts = find_best_shifts(wordlist, s)

# decrypt_fable()