Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Dec 1st, 2012  |  syntax: Python  |  size: 12.24 KB  |  hits: 83  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. # 6.00 Problem Set 4
  2. #
  3. # Caesar Cipher Skeleton
  4. #
  5. import string
  6. import random
  7.  
  8. WORDLIST_FILENAME = "words.txt"
  9.  
  10. # -----------------------------------
  11. # Helper code
  12. # (you don't need to understand this helper code)
  13. def load_words():
  14.     """
  15.    Returns a list of valid words. Words are strings of lowercase letters.
  16.    
  17.    Depending on the size of the word list, this function may
  18.    take a while to finish.
  19.    """
  20.     print "Loading word list from file..."
  21.     # inFile: file
  22.     inFile = open(WORDLIST_FILENAME, 'r', 0)
  23.     # line: string
  24.     line = inFile.readline()
  25.     # wordlist: list of strings
  26.     wordlist = line.split()
  27.     print "  ", len(wordlist), "words loaded."
  28.     return wordlist
  29.  
  30. wordlist = load_words()
  31.  
  32. def is_word(wordlist, word):
  33.     """
  34.    Determines if word is a valid word.
  35.  
  36.    wordlist: list of words in the dictionary.
  37.    word: a possible word.
  38.    returns True if word is in wordlist.
  39.  
  40.    Example:
  41.    >>> is_word(wordlist, 'bat') returns
  42.    True
  43.    >>> is_word(wordlist, 'asdf') returns
  44.    False
  45.    """
  46.     word = word.lower()
  47.     word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
  48.     return word in wordlist
  49.  
  50. def random_word(wordlist):
  51.     """
  52.    Returns a random word.
  53.  
  54.    wordlist: list of words  
  55.    returns: a word from wordlist at random
  56.    """
  57.     return random.choice(wordlist)
  58.  
  59. def random_string(wordlist, n):
  60.     """
  61.    Returns a string containing n random words from wordlist
  62.  
  63.    wordlist: list of words
  64.    returns: a string of random words separated by spaces.
  65.    """
  66.     return " ".join([random_word(wordlist) for _ in range(n)])
  67.  
  68. def random_scrambled(wordlist, n):
  69.     """
  70.    Generates a test string by generating an n-word random string
  71.    and encrypting it with a sequence of random shifts.
  72.  
  73.    wordlist: list of words
  74.    n: number of random words to generate and scamble
  75.    returns: a scrambled string of n random words
  76.  
  77.  
  78.    NOTE:
  79.    This function will ONLY work once you have completed your
  80.    implementation of apply_shifts!
  81.    """
  82.     s = random_string(wordlist, n) + " "
  83.     shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']
  84.     return apply_shifts(s, shifts)[:-1]
  85.  
  86. def get_fable_string():
  87.     """
  88.    Returns a fable in encrypted text.
  89.    """
  90.     f = open("fable.txt", "r")
  91.     fable = str(f.read())
  92.     f.close()
  93.     return fable
  94.  
  95.  
  96.  
  97. # (end of helper code)
  98. # -----------------------------------
  99.  
  100. #
  101. # Problem 1: Encryption
  102. #
  103. def build_coder(shift):
  104.     """
  105.    Returns a dict that can apply a Caesar cipher to a letter.
  106.    The cipher is defined by the shift value. Ignores non-letter characters
  107.    like punctuation and numbers.
  108.  
  109.    shift: -27 < int < 27
  110.    returns: dict
  111.  
  112.    Example:
  113.    >>> build_coder(3)
  114.    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
  115.    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
  116.    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
  117.    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
  118.    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
  119.    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
  120.    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
  121.    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
  122.    (The order of the key-value pairs may be different.)
  123.    """
  124.     ### TODO.
  125.     assert shift >= 0 and shift < 27, 'shift %s is not between 0 and 27' % shift
  126. #     #numbers.Integral used in case of long integers
  127.     assert isinstance(shift, int), 'shift is not an integer'
  128.    
  129.     coder = {}
  130.  
  131.     lowercase_and_space = string.ascii_lowercase + ' '
  132.     uppercase_and_space = string.ascii_uppercase + ' '
  133.  
  134.     # Shift letters over shift places
  135.     shifted_lowercase_and_space = lowercase_and_space[shift:] + lowercase_and_space[:shift]
  136.     shifted_uppercase_and_space = uppercase_and_space[shift:] + uppercase_and_space[:shift]
  137.  
  138. # Construct Caesar cipher dictionary
  139.     # Add uppercase letters first so ' ' will be overwritten to point to lowercase letter
  140.     for i in range(len(uppercase_and_space)):
  141.         coder[uppercase_and_space[i]] = shifted_uppercase_and_space[i]
  142.  
  143.     for i in range(len(lowercase_and_space)):
  144.         coder[lowercase_and_space[i]] = shifted_lowercase_and_space[i]
  145.  
  146.     return coder
  147.  
  148. print build_coder(3)
  149.  
  150.        
  151.  
  152. def build_encoder(shift):
  153.     """
  154.    Returns a dict that can be used to encode a plain text. For example, you
  155.    could encrypt the plain text by calling the following commands
  156.    >>>encoder = build_encoder(shift)
  157.    >>>encrypted_text = apply_coder(plain_text, encoder)
  158.    
  159.    The cipher is defined by the shift value. Ignores non-letter characters
  160.    like punctuation and numbers.
  161.  
  162.    shift: 0 <= int < 27
  163.    returns: dict
  164.  
  165.    Example:
  166.    >>> build_encoder(3)
  167.    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
  168.    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
  169.    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
  170.    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
  171.    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
  172.    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
  173.    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
  174.    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
  175.    (The order of the key-value pairs may be different.)
  176.  
  177.    HINT : Use build_coder.
  178.    """
  179.     ### TODO.
  180.  
  181. def build_decoder(shift):
  182.     """
  183.    Returns a dict that can be used to decode an encrypted text. For example, you
  184.    could decrypt an encrypted text by calling the following commands
  185.    >>>encoder = build_encoder(shift)
  186.    >>>encrypted_text = apply_coder(plain_text, encoder)
  187.    >>>decrypted_text = apply_coder(plain_text, decoder)
  188.    
  189.    The cipher is defined by the shift value. Ignores non-letter characters
  190.    like punctuation and numbers.
  191.  
  192.    shift: 0 <= int < 27
  193.    returns: dict
  194.  
  195.    Example:
  196.    >>> build_decoder(3)
  197.    {' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',
  198.    'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',
  199.    'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',
  200.    'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',
  201.    'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',
  202.    'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',
  203.    'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',
  204.    'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}
  205.    (The order of the key-value pairs may be different.)
  206.  
  207.    HINT : Use build_coder.
  208.    """
  209.     ### TODO.
  210.    
  211.  
  212.    
  213.    
  214.  
  215.  
  216. def apply_coder(text, coder):
  217.     """
  218.    Applies the coder to the text. Returns the encoded text.
  219.  
  220.    text: string
  221.    coder: dict with mappings of characters to shifted characters
  222.    returns: text after mapping coder chars to original text
  223.  
  224.    Example:
  225.    >>> apply_coder("Hello, world!", build_encoder(3))
  226.    'Khoor,czruog!'
  227.    >>> apply_coder("Khoor,czruog!", build_decoder(3))
  228.    'Hello, world!'
  229.    """
  230.     encoded_word = ''
  231.    
  232.     for i in range (0, len(text)):
  233.         if text[i] not in coder:
  234.                 encoded_word = encoded_word + text[i]
  235.         else:
  236.                 encoded_word = encoded_word + coder[text[i]]
  237.        
  238.     return encoded_word
  239.    
  240. print apply_coder('Hello, world!', build_coder(3))
  241.    
  242.        
  243.     ### TODO.
  244.  
  245.  
  246. def apply_shift(text, shift):
  247.     """
  248.    Given a text, returns a new text Caesar shifted by the given shift
  249.    offset. The empty space counts as the 27th letter of the alphabet,
  250.    so spaces should be replaced by a lowercase letter as appropriate.
  251.    Otherwise, lower case letters should remain lower case, upper case
  252.    letters should remain upper case, and all other punctuation should
  253.    stay as it is.
  254.    
  255.    text: string to apply the shift to
  256.    shift: amount to shift the text
  257.    returns: text after being shifted by specified amount.
  258.  
  259.    Example:
  260.    >>> apply_shift('This is a test.', 8)
  261.    'Apq hq hiham a.'
  262.    """
  263.     ### TODO.
  264.    
  265.     return apply_coder(text, build_coder(shift))
  266.    
  267. print apply_shift('This is a test.', 8)
  268.    
  269.  
  270.    
  271. #
  272. # Problem 2: Codebreaking.
  273. #
  274.  
  275. def find_best_shift(wordlist, text):
  276.     """
  277.    Decrypts the encoded text and returns the plaintext.
  278.  
  279.    text: string
  280.    returns: 0 <= int 27
  281.  
  282.    Example:
  283.    >>> s = apply_coder('Hello, world!', build_encoder(8))
  284.    >>> s
  285.    'Pmttw,hdwztl!'
  286.    >>> find_best_shift(wordlist, s) returns
  287.    8
  288.    >>> apply_coder(s, build_decoder(8)) returns
  289.    'Hello, world!'
  290.    """
  291.     ### TODO
  292.    
  293.     max_num_valid_words = 0
  294.     best_shift = 0
  295.    
  296.     for shift in range(27):
  297.         shifted_words = apply_shift(text, shift)
  298.         potential_words = shifted_words.split()
  299.         num_valid_words = 0
  300.         for word in potential_words:
  301.                 if is_word(wordlist, word):
  302.                         num_valid_words += 1
  303.         if num_valid_words > max_num_valid_words:
  304.                 max_num_valid_words = num_valid_words
  305.                 best_shift = shift
  306.                
  307.     return best_shift
  308.    
  309. print find_best_shift(wordlist, "Pmttw,hdwztl!")
  310.                            
  311. #
  312. # Problem 3: Multi-level encryption.
  313. #
  314.  
  315. def apply_shifts(text, shifts):
  316.     """
  317.    Applies a sequence of shifts to an input text.
  318.  
  319.    text: A string to apply the Ceasar shifts to
  320.    shifts: A list of tuples containing the location each shift should
  321.    begin and the shift offset. Each tuple is of the form (location,
  322.    shift) The shifts are layered: each one is applied from its
  323.    starting position all the way through the end of the string.  
  324.    returns: text after applying the shifts to the appropriate
  325.    positions
  326.  
  327.    Example:
  328.    >>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  329.    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
  330.    """
  331.     ### TODO.
  332.    
  333.     encoded_word = ""
  334.     a = dict(shifts)
  335.     for key in a:
  336.         if key == 0:
  337.                 initial_shift = apply_shift(text, a[key])
  338.                 encoded_word = encoded_word + initial_shift
  339.                 print encoded_word
  340.         else:
  341.                 new_shift = apply_shift(encoded_word[key:], a[key])
  342.                 print new_shift
  343.                 encoded_word = encoded_word[0:key] + new_shift
  344.                 print encoded_word
  345.     return encoded_word
  346.  
  347. # print apply_shifts("JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?", [(0, 21), (3, 9), (12, 11), (18, 0), (21, 0), (30, 0)])   
  348.        
  349.  
  350.  
  351.    
  352.  
  353. #
  354. # Problem 4: Multi-level decryption.
  355. #
  356.  
  357. def find_best_shifts_rec(wordlist, text, start):
  358.     """
  359.    Given a scrambled string and a starting position from which
  360.    to decode, returns a shift key that will decode the text to
  361.    words in wordlist, or None if there is no such key.
  362.  
  363.    Hint: You will find this function much easier to implement
  364.    if you use recursion.
  365.  
  366.    wordlist: list of words
  367.    text: scambled text to try to find the words for
  368.    start: where to start looking at shifts
  369.    returns: list of tuples.  each tuple is (position in text, amount of shift)
  370.    """
  371.     ### TODO.
  372.    
  373.     new_string = text
  374.    
  375.     for shift in xrange(0, 27):
  376.         new_string = text[0:start] + apply_shift(text[start:len(text)], shift)
  377.         for i in xrange(start, len(new_string)+1):
  378.             if is_word(wordlist, new_string[start:i]):
  379.                 if i == len(new_string):
  380.                     return [(start, shift)]
  381.                 elif new_string[i] == ' ':
  382.                         recShifts = find_best_shifts_rec(wordlist, new_string, i+1)
  383.                         if recShifts != None:
  384.                                 return [(start, shift)] + recShifts
  385.                                
  386. print find_best_shifts_rec(wordlist, "JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?", 0)
  387.  
  388. def decrypt_fable():
  389.     """
  390.    Using the methods you created in this problem set,
  391.    decrypt the fable given by the function get_fable_string().
  392.    Once you decrypt the message, be sure to include as a comment
  393.    at the end of this problem set how the fable relates to your
  394.    education at MIT.
  395.  
  396.    returns: string - fable in plain text
  397.    """
  398.     fable = get_fable_string()
  399.     shifts = find_best_shifts_rec(wordlist, fable, 0)
  400.     decoded_fable = apply_shifts(fable, shifts)
  401.     return decoded_fable
  402.    
  403. print decrypt_fable()
create a new version of this paste RAW Paste Data