CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science
Homework 4 (Due Mon 9-Jul, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Download hw4.py to your 'week1' folder
  2. Edit hw4.py using Pyzo
  3. When you are ready, submit hw4.py to Autolab. For this hw, you may submit up to 20 times (which is way more than you should require), but only your last submission counts.
• Do not use lists, or recursion in this assignment.
• Do not hardcode the test cases in your solutions.

1. longestCommonSubstring(s1, s2) [30 pts]
   Write the function, longestCommonSubstring(s1, s2), that takes two possibly-empty strings and returns the longest string that occurs in both strings (and returns the empty string if either string is empty). For example:

        longestCommonSubstring("abcdef", "abqrcdest") returns "cde"
        longestCommonSubstring("abcdef", "ghi") returns "" (the empty string)
   

   If there are two or more longest common substrings, return the lexicographically smaller one (ie, just use "<" to compare the strings). So, for example:

       longestCommonSubstring("abcABC", "zzabZZAB") returns "AB" and not "ab"
   

   
   Hint: Start by solving a simpler problem: how would you find and return the longest-matching substring starting from the beginning of each of the strings? Under this restriction:

        longestCommonSubstring*("abcdef", "abqrcdest") returns "ab"
   

   Now imagine you have a helper function that implements that simpler version of longestCommonSubstring. With that helper function, you can solve longestCommonSubstring by generating all possible combinations of the starting places of s1 and s2, and calling the helper function with each. This can help you identify which sequence of matching characters is the longest.



2. bestStudentAndAvg(gradebook) [30 pts]
   Background: for this problem, a "gradebook" is a multiline string where each row contains a student's name (one word, all lowercase) followed by one or more comma-separated integer grades. A gradebook always contains at least one student, and each row always contains at least one grade. Gradebooks can also contain blank lines and lines starting with the "#" character, which should be ignored.
   
   With this in mind, write the function bestStudentAndAvg(gradebook), that takes a gradebook and finds the student with the best average (ignoring the case where there is a tie) and returns a string of that student's name followed by a colon (":") followed by his/her average (rounded using the provided roundHalfUp). For example, here is a test case:

   gradebook = """
   # ignore  blank lines and lines starting  with  #'s
   wilma,91,93
   fred,80,85,90,95,100
   betty,88
   """
   assert(bestStudentAndAvg(gradebook) ==  "wilma:92"))
   

   Note: you most likely will want to use both s.split(",") and s.splitlines() in your solution.



3. encodeColumnShuffleCipher(message, key) [40 pts]
   Background: In this problem you will implement a simple encryption cipher we've called a column shuffle cipher. It takes two values, a plaintext and a key, and it constructs a grid of the letters of the message, rearranges the columns of the grid, and then reads the characters back column by column.
   
   Consider the following example:
   

   Function call: encodeColumnShuffleCipher("ILOVECMUSOMUCH", "021")
   Message: ILOVECMUSOMUCH
   Key: 021
   
   Initial Grid:   Rearranged Grid:
     I L O             I O L          
     V E C             V C E
     M U S             M S U
     O M U             O U M
     C H -             C - H
   
   
   Encrypted Message: IVMOCOCSU-LEUMH
   Message to Return: 021IVMOCOCSU-LEUMH
   

   The first step is to take the message and arrange it into a grid that has as many columns as the key has characters. (In this case, 3 columns.) Any empty spaces at the end are filled with - characters. We then rearrange the grid by changing the column order to match the order specified by the key. In this case, the 0th column becomes first, then the 2nd column, then the 1st. Finally, we read out the encrypted message by reading down the columns from left to right. The returned value from the function is just the encrypted message prepended with the key.
   
   With this in mind, write the function encodeColumnShuffleCipher(message, key) that takes an all-uppercase message and a valid key, and returns the encoding as just described.
   
   Hint: In your program you won't actually build a grid. Instead, you will use the concept of the grid to help you calculate the index of individual characters in your message.

Bonus Problems!

None of the problems below this statement are required.


4. decodeColumnShuffleCipher(encodedMessage) [1 pt]
   Write the function decodeColumnShuffleCipher(encodedMessage), which takes an encoding from encodeColumnShuffleCipher and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeColumnShuffleCipher("0213WTAWACD-EATNTKA-") returns "WEATTACKATDAWN".


5. mostFrequentLetters(s) [3 pts]
   Write the function mostFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the letters of s in most frequently used order. (In the event of a tie between two letters, follow alphabetic order.) So:

      mostFrequentLetters("We Attack at Dawn")
   

   returns "atwcdekn". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. (And you should not use lists, sets, or maps in your solution. Do not use sorted() or .sort() either.) Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").