API tools faq
paste
rtorres

Non-Recursive-Solution to ps4

rtorres
May 18th, 2014
357
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 15.63 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.  
  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.     #if len(word) > 0:
  48.       #if word[0] == " ":
  49.     #return False
  50.     word = word.strip(" !@#$%^&*()-_+={}[]|\:;'<>?,./\"")
  51.     return word in wordlist
  52.  
  53. def random_word(wordlist):
  54.     """
  55.    Returns a random word.
  56.  
  57.    wordlist: list of words  
  58.    returns: a word from wordlist at random
  59.    """
  60.     return random.choice(wordlist)
  61.  
  62. def random_string(wordlist, n):
  63.     """
  64.    Returns a string containing n random words from wordlist
  65.  
  66.    wordlist: list of words
  67.    returns: a string of random words separated by spaces.
  68.    """
  69.     return " ".join([random_word(wordlist) for _ in range(n)])
  70.  
  71. def random_scrambled(wordlist, n):
  72.     """
  73.    Generates a test string by generating an n-word random string
  74.    and encrypting it with a sequence of random shifts.
  75.  
  76.    wordlist: list of words
  77.    n: number of random words to generate and scamble
  78.    returns: a scrambled string of n random words
  79.  
  80.  
  81.    NOTE:
  82.    This function will ONLY work once you have completed your
  83.    implementation of apply_shifts!
  84.    """
  85.     s = random_string(wordlist, n) + " "
  86.     shifts = [(i, random.randint(0, 26)) for i in range(len(s)) if s[i-1] == ' ']
  87.     return apply_shifts(s, shifts)[:-1]
  88.  
  89. def get_fable_string():
  90.     """
  91.    Returns a fable in encrypted text.
  92.    """
  93.     f = open("fable.txt", "r")
  94.     fable = str(f.read())
  95.     f.close()
  96.     return fable
  97.  
  98.  
  99. # (end of helper code)
  100. # -----------------------------------
  101.  
  102. #
  103. # Problem 1: Encryption
  104. #
  105. def build_coder(shift):
  106.  
  107.     """
  108.    Returns a dict that can apply a Caesar cipher to a letter.
  109.    The cipher is defined by the shift value. Ignores non-letter characters
  110.    like punctuation and numbers.
  111.  
  112.    shift: -27 < int < 27
  113.    returns: dict
  114.  
  115.    Example:
  116.    >>> build_coder(3)
  117.    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
  118.    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
  119.    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
  120.    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
  121.    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
  122.    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
  123.    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
  124.    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
  125.    (The order of the key-value pairs may be different.)
  126.    """
  127.     ### TODO.
  128.     if shift == 27:
  129.       shift = 0
  130.     try:
  131.       shift = int(shift)
  132.       if shift <-26 or shift > 26:
  133.     print "An integer between -26 <= shift <= 26 should be enter"
  134.     return
  135.     except ValueError:
  136.       print "You must enter an integer value"
  137.       return
  138.    
  139.     alphabet = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' ']
  140.     if shift < 0:
  141.       shift = len(alphabet) + shift
  142.     dictionary = {}
  143.     for i in xrange(0,len(alphabet)):
  144.       dictionary[alphabet[i]] = alphabet[(i+shift)%27]
  145.       dictionary[alphabet[i].lower()] = alphabet[(i+shift)%27].lower()
  146.     #print dictionary
  147.     return dictionary
  148.    
  149. def build_encoder(shift):
  150.     """
  151.    Returns a dict that can be used to encode a plain text. For example, you
  152.    could encrypt the plain text by calling the following commands
  153.    >>>encoder = build_encoder(shift)
  154.    >>>encrypted_text = apply_coder(plain_text, encoder)
  155.    
  156.    The cipher is defined by the shift value. Ignores non-letter characters
  157.    like punctuation and numbers.
  158.  
  159.    shift: 0 <= int < 27
  160.    returns: dict
  161.  
  162.    Example:
  163.    >>> build_encoder(3)
  164.    {' ': 'c', 'A': 'D', 'C': 'F', 'B': 'E', 'E': 'H', 'D': 'G', 'G': 'J',
  165.    'F': 'I', 'I': 'L', 'H': 'K', 'K': 'N', 'J': 'M', 'M': 'P', 'L': 'O',
  166.    'O': 'R', 'N': 'Q', 'Q': 'T', 'P': 'S', 'S': 'V', 'R': 'U', 'U': 'X',
  167.    'T': 'W', 'W': 'Z', 'V': 'Y', 'Y': 'A', 'X': ' ', 'Z': 'B', 'a': 'd',
  168.    'c': 'f', 'b': 'e', 'e': 'h', 'd': 'g', 'g': 'j', 'f': 'i', 'i': 'l',
  169.    'h': 'k', 'k': 'n', 'j': 'm', 'm': 'p', 'l': 'o', 'o': 'r', 'n': 'q',
  170.    'q': 't', 'p': 's', 's': 'v', 'r': 'u', 'u': 'x', 't': 'w', 'w': 'z',
  171.    'v': 'y', 'y': 'a', 'x': ' ', 'z': 'b'}
  172.    (The order of the key-value pairs may be different.)
  173.  
  174.    HINT : Use build_coder.
  175.    """
  176.     ### TODO.
  177.     if shift == 27:
  178.       shift = 0
  179.     try:
  180.       shift = int(shift)
  181.       if shift < 0 or shift > 26:
  182.     print "An integer between 0 <= shift <= 26 should be enter"
  183.     return
  184.     except ValueError:
  185.       print "You must enter an integer value"
  186.       return
  187.     #print  build_coder(shift)
  188.     return build_coder(shift)
  189.  
  190. def build_decoder(shift):
  191.     """
  192.    Returns a dict that can be used to decode an encrypted text. For example, you
  193.    could decrypt an encrypted text by calling the following commands
  194.    >>>encoder = build_encoder(shift)
  195.    >>>encrypted_text = apply_coder(plain_text, encoder)
  196.    >>>decrypted_text = apply_coder(plain_text, decoder)
  197.    
  198.    The cipher is defined by the shift value. Ignores non-letter characters
  199.    like punctuation and numbers.
  200.  
  201.    shift: 0 <= int < 27
  202.    returns: dict
  203.  
  204.    Example:
  205.    >>> build_decoder(3)
  206.    {' ': 'x', 'A': 'Y', 'C': ' ', 'B': 'Z', 'E': 'B', 'D': 'A', 'G': 'D',
  207.    'F': 'C', 'I': 'F', 'H': 'E', 'K': 'H', 'J': 'G', 'M': 'J', 'L': 'I',
  208.    'O': 'L', 'N': 'K', 'Q': 'N', 'P': 'M', 'S': 'P', 'R': 'O', 'U': 'R',
  209.    'T': 'Q', 'W': 'T', 'V': 'S', 'Y': 'V', 'X': 'U', 'Z': 'W', 'a': 'y',
  210.    'c': ' ', 'b': 'z', 'e': 'b', 'd': 'a', 'g': 'd', 'f': 'c', 'i': 'f',
  211.    'h': 'e', 'k': 'h', 'j': 'g', 'm': 'j', 'l': 'i', 'o': 'l', 'n': 'k',
  212.    'q': 'n', 'p': 'm', 's': 'p', 'r': 'o', 'u': 'r', 't': 'q', 'w': 't',
  213.    'v': 's', 'y': 'v', 'x': 'u', 'z': 'w'}
  214.    (The order of the key-value pairs may be different.)
  215.  
  216.    HINT : Use build_coder.
  217.    """
  218.     ### TODO.
  219.     if shift == 27:
  220.       shift = 0
  221.     try:
  222.       shift = int(shift)
  223.       if shift < 0 or shift > 26:
  224.     print "An integer between 0 <= shift <= 26 should be enter"
  225.     return
  226.     except ValueError:
  227.       print "You must enter an integer value"
  228.       return
  229.     #print  build_coder(shift)
  230.     shift = -shift
  231.     return build_coder(shift)
  232.  
  233.  
  234. def apply_coder(text, coder):
  235.     """
  236.    Applies the coder to the text. Returns the encoded text.
  237.  
  238.    text: string
  239.    coder: dict with mappings of characters to shifted characters
  240.    returns: text after mapping coder chars to original text
  241.  
  242.    Example:
  243.    >>> apply_coder("Hello, world!", build_encoder(3))
  244.    'Khoor,czruog!'
  245.    >>> apply_coder("Khoor,czruog!", build_decoder(3))
  246.    'Hello, world!'
  247.    """
  248.     ### TODO.
  249.     coded_text = []
  250.     for c in text:
  251.       if c in coder.keys():
  252.     coded_text.append(coder[c])
  253.       else:
  254.     coded_text.append(c)
  255.     return "".join(coded_text)
  256.  
  257.  
  258. def apply_shift(text, shift):
  259.     """
  260.    Given a text, returns a new text Caesar shifted by the given shift
  261.    offset. The empty space counts as the 27th letter of the alphabet,
  262.    so spaces should be replaced by a lowercase letter as appropriate.
  263.    Otherwise, lower case letters should remain lower case, upper case
  264.    letters should remain upper case, and all other punctuation should
  265.    stay as it is.
  266.    
  267.    text: string to apply the shift to
  268.    shift: amount to shift the text
  269.    returns: text after being shifted by specified amount.
  270.  
  271.    Example:
  272.    >>> apply_shift('This is a test.', 8)
  273.    'Apq hq hiham a.'
  274.    """
  275.     ### TODO.
  276.     return apply_coder(text, build_encoder(shift))
  277.    
  278. #
  279. # Problem 2: Codebreaking.
  280. #
  281. def find_best_shift(wordlist, text):
  282.     """
  283.    Decrypts the encoded text and returns the plaintext.
  284.  
  285.    text: string
  286.    returns: 0 <= int 27
  287.  
  288.    Example:
  289.    >>> s = apply_coder('Hello, world!', build_encoder(8))
  290.    >>> s
  291.    'Pmttw,hdwztl!'
  292.    >>> find_best_shift(wordlist, s) returns
  293.    8
  294.    >>> apply_coder(s, build_decoder(8)) returns
  295.    'Hello, world!'
  296.    """
  297.     ### TODO
  298.     decrypted_text = []
  299.     number_of_words = 0
  300.     shift_value = 0
  301.     for i in xrange(27):
  302.       s = apply_coder(text, build_decoder(i))
  303.       if not s[0] == " ":
  304.     transitory_array1 = s.split(" ")
  305.     if is_word(wordlist, transitory_array1[0]):
  306.       transitory_array2 = []
  307.       for j in range(0, len(transitory_array1)):
  308.         if is_word(wordlist, transitory_array1[j]):
  309.           transitory_array2.append(transitory_array1[j] + " ")       
  310.       if len(transitory_array2) > len(decrypted_text):
  311.         decrypted_text = transitory_array2
  312.         shift_value = i
  313.    
  314.     return shift_value
  315. #
  316. # Problem 3: Multi-level encryption.
  317. #
  318. def apply_shifts(text, shifts):
  319.     """
  320.    Applies a sequence of shifts to an input text.
  321.  
  322.    text: A string to apply the Ceasar shifts to
  323.    shifts: A list of tuples containing the location each shift should
  324.    begin and the shift offset. Each tuple is of the form (location,
  325.    shift) The shifts are layered: each one is applied from its
  326.    starting position all the way through the end of the string.  
  327.    returns: text after applying the shifts to the appropriate
  328.    positions
  329.  
  330.    Example:
  331.    >>> apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  332.    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
  333.    """
  334.     ### TODO.
  335.    
  336.     result = text[:]
  337.     for i in xrange(len(shifts)):
  338.       position = shifts[i][0]
  339.       text1 = result[position:]
  340.       text1 = apply_shift(text1,shifts[i][1])
  341.       if position > 0:
  342.     result = result[0:position] + text1
  343.       else:
  344.     result = text1[:]
  345.      
  346.     return result  
  347. #
  348. # Problem 4: Multi-level decryption.
  349. #
  350.  
  351.  
  352. def find_best_shifts(wordlist, text):
  353.     """
  354.    Given a scrambled string, returns a shift key that will decode the text to
  355.    words in wordlist, or None if there is no such key.
  356.  
  357.    Hint: Make use of the recursive function
  358.    find_best_shifts_rec(wordlist, text, start)
  359.  
  360.    wordlist: list of words
  361.    text: scambled text to try to find the words for
  362.    returns: list of tuples.  each tuple is (position in text, amount of shift)
  363.    
  364.    Examples:
  365.    >>> s = random_scrambled(wordlist, 3)
  366.    >>> s
  367.    'eqorqukvqtbmultiform wyy ion'
  368.    >>> shifts = find_best_shifts(wordlist, s)
  369.    >>> shifts
  370.    [(0, 25), (11, 2), (21, 5)]
  371.    >>> apply_shifts(s, shifts)
  372.    'compositor multiform accents'
  373.    >>> s = apply_shifts("Do Androids Dream of Electric Sheep?", [(0,6), (3, 18), (12, 16)])
  374.    >>> s
  375.    'JufYkaolfapxQdrnzmasmRyrpfdvpmEurrb?'
  376.    >>> shifts = find_best_shifts(wordlist, s)
  377.    >>> print apply_shifts(s, shifts)
  378.    Do Androids Dream of Electric Sheep?
  379.    """    
  380.     s = text
  381.     shifts = []
  382.     position = 0
  383.     #This code is not recursive so it runs until the length of s is 0 this will signal that the last word has been decoded
  384.     while len(s) > 0:
  385.       #tupple is the array where the possible word and its shift value is store: Note that there can be more than one valid word
  386.       #that is the reason I use of an array of tupples.
  387.       tupple = []
  388.       #For the full text we run all shifts after each shift we split s1 and put its values in a matrix1.
  389.       #Note that the first value of the matrix will be a piece of text right before the first space
  390.       for i in xrange(27):
  391.     s1 = apply_coder(s,build_decoder(i))
  392.     matrix1 = s1.split()
  393.     #We evaluate if the contents of matrix1[0] is a valid word if is is we save it in tupple with its shift value
  394.     if is_word(wordlist,matrix1[0]) and not s1[0] == " ":
  395.       tupple.append((matrix1[0], i))
  396.       #since there can be more than one valid word in tupple after each shift we need to choose one and proceed with the decryption
  397.       #The rule use in this algorithm is when possible choose the word that is the longer one in almost all cases there is only one valid word
  398.       #but for those rare cases where there is more than 1 then we choose the one that is greater in length. This increases greatly the probability that
  399.       #the right word has been choosen since in most cases the other valid word will be one letter words.
  400.       max = len(tupple[0][0])
  401.       max_shift = tupple[0][1]
  402.       #decoded = tupple[0][0] #This line is needed if you want to print the string as is been decoded before you run apply_shifts as to test the validity of the algorithm
  403.  
  404.       #This is the actual part of the code that chooses the valid word with its respective shift value base on the max length of the possible choices
  405.       if len(tupple) > 1:
  406.     for i in xrange(len(tupple)-1):
  407.       if len(tupple[i+1][0]) > max:
  408.         max = len(tupple[i+1][0])
  409.         #decoded = tupple[i+1][0]   #Use if want to print the message as is been decoded
  410.         max_shift = tupple[i+1][1]
  411.      
  412.       #we apply the selected shift value to string s and split its values and put them in matrix1
  413.       s = apply_coder(s,build_decoder(max_shift))
  414.       matrix1 = s.split()
  415.       #text += decoded + " " #Use if you want to print the message as is been decoded
  416.      
  417.       #This part of the code has to do with the implementation of build_decoder that is the reason of 27-max_shift
  418.       if max_shift == 0:
  419.     max_shift = 27
  420.      
  421.       shifts.append((position, 27 - max_shift)) #this is the array of tupples that contains the position and shift value
  422.       position += len(matrix1[0]) + 1 #The initial position is 0 and then after that we increment by the length of word in matrix1[0] which is the decoded word + 1 for the space
  423.       s = s[len(matrix1[0])+1:] #We shorten s by the decoded word so we are left only with code that still needs to be decoded
  424.       #print text    #Use if you want to see the message printed as is been decoded
  425.     return shifts
  426.  
  427.  
  428. def find_best_shifts_rec(wordlist, text, start):
  429.     """
  430.    Given a scrambled string and a starting position from which
  431.    to decode, returns a shift key that will decode the text to
  432.    words in wordlist, or None if there is no such key.
  433.  
  434.    Hint: You will find this function much easier to implement
  435.    if you use recursion.
  436.  
  437.    wordlist: list of words
  438.    text: scambled text to try to find the words for
  439.    start: where to start looking at shifts
  440.    returns: list of tuples.  each tuple is (position in text, amount of shift)
  441.    """
  442.     ### TODO.
  443.  
  444.  
  445. def decrypt_fable():
  446.      """
  447.    Using the methods you created in this problem set,
  448.    decrypt the fable given by the function get_fable_string().
  449.    Once you decrypt the message, be sure to include as a comment
  450.    at the end of this problem set how the fable relates to your
  451.    education at MIT.
  452.  
  453.    returns: string - fable in plain text
  454.    """
  455.     ### TODO.
  456.      s = get_fable_string()
  457.      bar = find_best_shifts(wordlist,s)
  458.      return  apply_shifts(s,bar)
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465. #What is the moral of the story?
  466. #
  467. #
  468. #
  469. #
  470. #
  471. print decrypt_fable()
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!