API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 12th, 2013
246
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 13.39 KB | None | 0 0
raw download clone embed print report
  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. #WORDLIST_FILENAME = "/media/1C9C3B909C3B6404/codes/problem set/ps4/words.txt"
  10.  
  11. # -----------------------------------
  12. # Helper code
  13. # (you don't need to understand this helper code)
  14. def load_words():
  15.     """
  16.   Returns a list of valid words. Words are strings of lowercase letters.
  17.  
  18.   Depending on the size of the word list, this function may
  19.   take a while to finish.
  20.   """
  21.     print "Loading word list from file..."
  22.     # inFile: file
  23.     inFile = open(WORDLIST_FILENAME, 'r', 0)
  24.     # line: string
  25.     line = inFile.readline()
  26.     # wordlist: list of strings
  27.     wordlist = line.split()
  28.     print "  ", len(wordlist), "words loaded."
  29.     return wordlist
  30.  
  31. wordlist = load_words()
  32.  
  33. def is_word(wordlist, word):
  34.     """
  35.   Determines if word is a valid word.
  36.  
  37.   wordlist: list of words in the dictionary.
  38.   word: a possible word.
  39.   returns True if word is in wordlist.
  40.  
  41.   Example:
  42.   >>> is_word(wordlist, 'bat') returns
  43.   True
  44.   >>> is_word(wordlist, 'asdf') returns
  45.   False
  46.   """
  47.     word = word.lower()
  48.     word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
  49.     return word in wordlist
  50.  
  51. def random_word(wordlist):
  52.     """
  53.   Returns a random word.
  54.  
  55.   wordlist: list of words  
  56.   returns: a word from wordlist at random
  57.   """
  58.     return random.choice(wordlist)
  59.  
  60. def random_string(wordlist, n):
  61.     """
  62.   Returns a string containing n random words from wordlist
  63.  
  64.   wordlist: list of words
  65.   returns: a string of random words separated by spaces.
  66.   """
  67.     return " ".join([random_word(wordlist) for _ in range(n)])
  68.  
  69. def random_scrambled(wordlist, n):
  70.     """
  71.   Generates a test string by generating an n-word random string
  72.   and encrypting it with a sequence of random shifts.
  73.  
  74.   wordlist: list of words
  75.   n: number of random words to generate and scamble
  76.   returns: a scrambled string of n random words
  77.  
  78.  
  79.   NOTE:
  80.   This function will ONLY work once you have completed your
  81.   implementation of apply_shifts!
  82.   """
  83.     s = random_string(wordlist, n) + " "
  84.     shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']
  85.     return apply_shifts(s, shifts)[:-1]
  86.  
  87. def get_fable_string():
  88.     """
  89.   Returns a fable in encrypted text.
  90.   """
  91.     f = open("fable.txt", "r")
  92.     fable = str(f.read())
  93.     f.close()
  94.     return fable
  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.    
  125.     coder = {}
  126.     lowercase = (' abcdefghijklmnopqrstuvwxyz')
  127.     uppercase = (' ABCDEFGHIJKLMNOPQRSTUVWXYZ')
  128.     for i in range(len(uppercase)):
  129.         if (i+shift) < len(uppercase):
  130.             coder[uppercase[i]] = uppercase[i + shift]
  131.         else:
  132.             coder[uppercase[i]] = uppercase[i + shift - len(uppercase)]
  133.     for i in range(len(lowercase)):
  134.         if (i+shift) < len(lowercase):
  135.             coder[lowercase[i]] = lowercase[i + shift]
  136.         else:
  137.             coder[lowercase[i]] = lowercase[i + shift - len(lowercase)]
  138.  
  139.     return coder
  140.  
  141.  
  142. def build_encoder(shift):
  143.     """
  144.   Returns a dict that can be used to encode a plain text. For example, you
  145.   could encrypt the plain text by calling the following commands
  146.   >>>encoder = build_encoder(shift)
  147.   >>>encrypted_text = apply_coder(plain_text, encoder)
  148.  
  149.   The cipher is defined by the shift value. Ignores non-letter characters
  150.   like punctuation and numbers.
  151.  
  152.   shift: 0 <= int < 27
  153.   returns: dict
  154.  
  155.   Example:
  156.   >>> build_encoder(3)
  157.   {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
  158.   'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
  159.   'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
  160.   'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
  161.   'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
  162.   'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
  163.   'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
  164.   'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
  165.   (The order of the key-value pairs may be different.)
  166.  
  167.   HINT : Use build_coder.
  168.   """
  169.     return build_coder(shift)
  170.  
  171. def build_decoder(shift):
  172.     """
  173.   Returns a dict that can be used to decode an encrypted text. For example, you
  174.   could decrypt an encrypted text by calling the following commands
  175.   >>>encoder = build_encoder(shift)
  176.   >>>encrypted_text = apply_coder(plain_text, encoder)
  177.   >>>decrypted_text = apply_coder(plain_text, decoder)
  178.  
  179.   The cipher is defined by the shift value. Ignores non-letter characters
  180.   like punctuation and numbers.
  181.  
  182.   shift: 0 <= int < 27
  183.   returns: dict
  184.  
  185.   Example:
  186.   >>> build_decoder(3)
  187.   {' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',
  188.   'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',
  189.   'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',
  190.   'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',
  191.   'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',
  192.   'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',
  193.   'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',
  194.   'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}
  195.   (The order of the key-value pairs may be different.)
  196.  
  197.   HINT : Use build_coder.
  198.   """
  199.     return build_encoder(-shift)
  200.  
  201.  
  202. def apply_coder(text, coder):
  203.     """
  204.   Applies the coder to the text. Returns the encoded text.
  205.  
  206.   text: string
  207.   coder: dict with mappings of characters to shifted characters
  208.   returns: text after mapping coder chars to original text
  209.  
  210.   Example:
  211.   >>> apply_coder("Hello, world!", build_encoder(3))
  212.   'Khoor,czruog!'
  213.   >>> apply_coder("Khoor,czruog!", build_decoder(3))
  214.   'Hello, world!'
  215.   """
  216.     code = ''
  217.     for c in text:
  218.         if c in coder:
  219.             code = code + coder[c]
  220.         else:
  221.             code = code + c
  222.     return code
  223.    
  224.            
  225.  
  226.  
  227. def apply_shift(text, shift):
  228.     """
  229.   Given a text, returns a new text Caesar shifted by the given shift
  230.   offset. The empty space counts as the 27th letter of the alphabet,
  231.   so spaces should be replaced by a lowercase letter as appropriate.
  232.   Otherwise, lower case letters should remain lower case, upper case
  233.   letters should remain upper case, and all other punctuation should
  234.   stay as it is.
  235.  
  236.   text: string to apply the shift to
  237.   shift: amount to shift the text
  238.   returns: text after being shifted by specified amount.
  239.  
  240.   Example:
  241.   >>> apply_shift('This is a test.', 8)
  242.   'Apq hq hiham a.'
  243.   """
  244.     return apply_coder(text, build_encoder(shift))
  245.    
  246. #
  247. # Problem 2: Codebreaking.
  248. #
  249. def find_best_shift(wordlist, text):
  250.     """
  251.   Decrypts the encoded text and returns the plaintext.
  252.  
  253.   text: string
  254.   returns: 0 <= int 27
  255.  
  256.   Example:
  257.   >>> s = apply_coder('Hello, world!', build_encoder(8))
  258.   >>> s
  259.   'Pmttw,hdwztl!'
  260.   >>> find_best_shift(wordlist, s) returns
  261.   8
  262.   >>> apply_coder(s, build_decoder(8)) returns
  263.   'Hello, world!'
  264.   """
  265.     valid_word = 0
  266.     maxwords = 0
  267.     decoded = ''
  268.     for shift in range(0, 27):
  269.         decoded = apply_shift(text, shift)
  270.  
  271.         for c in decoded.split():
  272.            
  273.             if is_word(wordlist, c):
  274.                 valid_word += 1
  275.                 #print valid_word
  276.  
  277.             if valid_word > maxwords:
  278.                 maxwords = valid_word
  279.                 bestShift = shift
  280.                
  281.     return (27 - bestShift)          
  282.    
  283.    
  284. #
  285. # Problem 3: Multi-level encryption.
  286. #
  287. def apply_shifts(text, shifts):
  288.     """
  289.   Applies a sequence of shifts to an input text.
  290.  
  291.   text: A string to apply the Ceasar shifts to
  292.   shifts: A list of tuples containing the location each shift should
  293.   begin and the shift offset. Each tuple is of the form (location,
  294.   shift) The shifts are layered: each one is applied from its
  295.   starting position all the way through the end of the string.  
  296.   returns: text after applying the shifts to the appropriate
  297.   positions
  298.  
  299.   Example:
  300.   >>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  301.   'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
  302.   """
  303.     new_string = ''
  304.     stext = text
  305.     for c in shifts:
  306.         new_string = stext[ :c[0]] + apply_shift(stext[c[0]: ], c[1])
  307.         stext = new_string
  308.     return new_string
  309.  
  310.    
  311.  
  312. #
  313. # Problem 4: Multi-level decryption.
  314. #
  315.  
  316.  
  317. def find_best_shifts(wordlist, text):
  318.     """
  319.   Given a scrambled string, returns a shift key that will decode the text to
  320.   words in wordlist, or None if there is no such key.
  321.  
  322.   Hint: Make use of the recursive function
  323.   find_best_shifts_rec(wordlist, text, start)
  324.  
  325.   wordlist: list of words
  326.   text: scambled text to try to find the words for
  327.   returns: list of tuples.  each tuple is (position in text, amount of shift)
  328.  
  329.   Examples:
  330.   >>> s = random_scrambled(wordlist, 3)
  331.   >>> s
  332.   'eqorqukvqtbmultiform wyy ion'
  333.   >>> shifts = find_best_shifts(wordlist, s)
  334.   >>> shifts
  335.   [(0, 25), (11, 2), (21, 5)]
  336.   >>> apply_shifts(s, shifts)
  337.   'compositor multiform accents'
  338.   >>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  339.   >>> s
  340.   'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
  341.   >>> shifts = find_best_shifts(wordlist, s)
  342.   >>> print apply_shifts(s, shifts)
  343.   Do Androids Dream of Electric Sheep?
  344.   """
  345.     s = find_best_shifts_rec(wordlist, text, 0)
  346.     shifts = []
  347.     s.reverse()
  348.     for c in s:
  349.         new = (c[0], -(c[1]))
  350.         shifts.append(new)
  351.     return shifts
  352.    
  353.        
  354.  
  355.  
  356. def find_best_shifts_rec(wordlist, text, start):
  357.     """
  358.   Given a scrambled string and a starting position from which
  359.   to decode, returns a shift key that will decode the text to
  360.   words in wordlist, or None if there is no such key.
  361.  
  362.   Hint: You will find this function much easier to implement
  363.   if you use recursion.
  364.  
  365.   wordlist: list of words
  366.   text: scambled text to try to find the words for
  367.   start: where to start looking at shifts
  368.   returns: list of tuples.  each tuple is (position in text, amount of shift)
  369.   """
  370.     new_string = text
  371.    
  372.     for shift in xrange(0, 27):
  373.         new_string = text[0:start] + apply_shift(text[start:len(text)], -shift)
  374.         for i in xrange(start, len(new_string)+1):
  375.             if is_word(wordlist, new_string[start:i]):
  376.                 if i == len(new_string):
  377.                     return [(start, shift)]
  378.                 elif new_string[i] == ' ':
  379.                     #print 'space is at index: ', i
  380.                     recShifts = find_best_shifts_rec(wordlist, new_string, i+1)
  381.                     #print 'recShifts1 : ', recShifts
  382.                     if recShifts != None:
  383.                         #print 'recShifts2 : ', recShifts
  384.                         return [(start, shift)] + recShifts
  385.    
  386.  
  387. #test1 (here your start position is after the space character.)                  
  388. s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  389. print 'shifts : [(0,6), (3, 18), (12, 16)]'
  390. print 's :' ,s
  391. shifts = find_best_shifts(wordlist, s)
  392. print 'bestSHIFTS : ',shifts
  393. print apply_shifts(s, shifts)
  394.  
  395.  
  396. print '.....................'
  397. ###test2 (here your start position is random in progressive order)
  398. ##s2 = apply_shifts("Do Androids Dream of Electric Sheep?", [(2,6), (5, 18), (10, 16)])
  399. ##print 'shifts : [(2,6), (5, 18), (10, 16)]'
  400. ##print 's2 :' ,s2
  401. ##shifts = find_best_shifts(wordlist, s2)
  402. ##print 'SHIFTS : ',shifts
  403. ##
  404. ##print '......................'
  405. ###test3 (here you should try start positions random at random order)
  406. ##s3 = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,8), (3, 5), (12, 5)])
  407. ##print 'shifts :  [(0,8), (3, 5), (12, 5)]'
  408. ##print 's3 :' ,s3
  409. ##shifts = find_best_shifts(wordlist, s3)
  410. ##print 'SHIFTS : ',shifts
  411.  
  412.  
  413.    
  414.  
  415.  
  416. def decrypt_fable():
  417.      """
  418.   Using the methods you created in this problem set,
  419.   decrypt the fable given by the function get_fable_string().
  420.   Once you decrypt the message, be sure to include as a comment
  421.   at the end of this problem set how the fable relates to your
  422.   education at MIT.
  423.  
  424.   returns: string - fable in plain text
  425.   """
  426.      fable = get_fable_string()
  427.      return apply_shifts(fable, find_best_shifts(wordlist, fable))
  428.  
  429. #import time
  430. #print time.ctime()
  431.  
  432. #print time.ctime()
  433.  
  434.  
  435.    
  436. #What is the moral of the story?
  437. #
  438. #
  439. #
  440. #
  441. #
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!