Homework 3

Due Sunday 03-Feb, at 8pm

Reminder: all problems that are not explicitly marked COLLABORATIVE must be completed individually, as stated in the course syllabus.
To start:
1. Create a folder named ‘week3’
2. Download both hw3.py and cs112_s19_week3_linter.py to that folder
3. Edit hw3.py using Pyzo
4. When you are ready, submit hw3.py to autolab. For this hw, you may submit up to 15 times (which is way more than you should require), but only your last submission counts.
Do not use lists, dictionaries, or recursion this week.
Do not hardcode the test cases in your solutions.

Style [0 pts]
Starting with this assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. Writing your code with good style from the beginning is the best way to avoid losing points!

COLLABORATIVE: longestCommonSubstring(s1, s2) [10 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"
```

COLLABORATIVE: bestStudentAndAvg(gradebook) [15 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 to the nearest integer). 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.

COLLABORATIVE: encodeColumnShuffleCipher(message, key) [20 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("WEATTACKATDAWN", "1320")
Message: WEATTACKATDAWN
Key: 1320

Initial Grid:		Rearranged Grid:
W E A T			T W A E
T A C K			K T C A
A T D A			A A D T
W N - -			- W - N

Encrypted Message: TKA-WTAWACD-EATN
Message to Return: 1320TKA-WTAWACD-EATN
```
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, 4 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, 0 being in the 3rd position of the key tells us that the 3rd column will become the 0th column. 1 being in the 0th position tells us that the 0th column will become the 1st column. 2 being in the 2nd position tells us that the 2nd column will become the 2nd column. 3 being in the 1st position tells us that the 1st column will become the 3rd column.

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.

mostFrequentLetters(s) [10 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.) Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

patternedMessage(message, pattern) [20 pts]
Write the function patternedMessage(message, pattern) that takes two strings, a message and a pattern, and returns a string produced by replacing the non-whitespace characters in the pattern with the non-whitespace characters in the message (where any leading or trailing newlines in the pattern are first removed). As a first example:

call	result
patternedMessage("Go Pirates!!!", """ ************* ** ** ************* """)	GoPirates!!!GoP irates !!!GoP irates!!!GoPira

Here, the message is "Go Pirates!!!" and the pattern is a block of asterisks with a few missing in the middle. Notice how the whitespace in the pattern is preserved, but the whitespace in the message is removed. Again, note that any leading or trailing newlines in the pattern are removed.

Here is another example:

call	result
patternedMessage("Three Diamonds!",""" * * * * * * * * * * * * * * * """)	T h r eeD iam ond s!Thr eeDia monds !Th ree Dia m o n

Hint: While you may solve this how you wish, our sample solution did not use replace in any way. Instead, we started with the empty string, and built up the result character by character. How did we determine the next character? Using both the message and the pattern in some way...

And here is one last example, just for fun:

patternedMessage("Go Steelers!",
"""
                          oooo$$$$$$$$$$$$oooo
                      oo$$$$$$$$$$$$$$$$$$$$$$$$o
                   oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o         o$   $$ o$
   o $ oo        o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o       $$ $$ $$o$
oo $ $ '$      o$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$o       $$$o$$o$
'$$$$$$o$     o$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$o    $$$$$$$$
  $$$$$$$    $$$$$$$$$$$      $$$$$$$$$$$      $$$$$$$$$$$$$$$$$$$$$$$
  $$$$$$$$$$$$$$$$$$$$$$$    $$$$$$$$$$$$$    $$$$$$$$$$$$$$  '$$$
   '$$$'$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$
    $$$   o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     '$$$o
   o$$'   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$       $$$o
   $$$    $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$' '$$$$$$ooooo$$$$o
  o$$$oooo$$$$$  $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$   o$$$$$$$$$$$$$$$$$
  $$$$$$$$'$$$$   $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$     $$$$'
 ''''       $$$$    '$$$$$$$$$$$$$$$$$$$$$$$$$$$$'      o$$$
            '$$$o     '$$$$$$$$$$$$$$$$$$'$$'         $$$
              $$$o          '$$'$$$$$$'           o$$$
               $$$$o                                o$$$'
                '$$$$o      o$$$$$$o'$$$$o        o$$$$
                  '$$$$$oo     '$$$$o$$$$$o   o$$$$'
                     '$$$$$oooo  '$$$o$$$$$$$$$'
                        '$$$$$$$oo $$$$$$$$$$
                                '$$$$$$$$$$$
                                    $$$$$$$$$$$$
                                     $$$$$$$$$$'
                                      '$$$'
""")

Returns this:

                          GoSteelers!GoSteeler
                      s!GoSteelers!GoSteelers!GoS
                   teelers!GoSteelers!GoSteelers!GoS         te   el er
   s ! Go        Steelers!GoSteelers!GoSteelers!GoSteel       er s! GoSt
ee l e rs      !GoSteeler    s!GoSteelers!    GoSteelers       !GoSteel
ers!GoSte     elers!GoSt      eelers!GoSt      eelers!GoSt    eelers!G
  oSteele    rs!GoSteele      rs!GoSteele      rs!GoSteelers!GoSteeler
  s!GoSteelers!GoSteelers    !GoSteelers!G    oSteelers!GoSt  eele
   rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSteel     ers!
    GoS   teelers!GoSteelers!GoSteelers!GoSteelers!GoSteelers     !GoSt
   eele   rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSt       eele
   rs!    GoSteelers!GoSteelers!GoSteelers!GoSteelers!Go Steelers!GoSteele
  rs!GoSteelers  !GoSteelers!GoSteelers!GoSteelers!GoS   teelers!GoSteelers
  !GoSteelers!G   oSteelers!GoSteelers!GoSteelers!Go     Steel
 ers!       GoSt    eelers!GoSteelers!GoSteelers!G      oSte
            elers     !GoSteelers!GoSteelers!         GoS
              teel          ers!GoSteel           ers!
               GoSte                                elers
                !GoSte      elers!GoSteele        rs!Go
                  Steelers     !GoSteelers!   GoStee
                     lers!GoSte  elers!GoSteeler
                        s!GoSteele rs!GoSteel
                                ers!GoSteele
                                    rs!GoSteeler
                                     s!GoSteeler
                                      s!GoS

decodeColumnShuffleCipher(encodedMessage) [20 pts]
Write the function decodeColumnShuffleCipher, which takes an encoding from encodeColumnShuffleCipher and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeColumnShuffleCipher("1320TKA-WTAWACD-EATN") returns "WEATTACKATDAWN".

Reminder: Even though you wrote encodeColumnShuffleCipher() in a collaborative group, this problem is not collaborative. You must solve it solo.

decodeColumnShuffleCipherNoDashes(encodedMessage) [5 pts]
Imagine an alternative version of encodeColumnShuffleCipher that does not add dashes to the encoded message.
Consider the following example:
```
Function call: encodeColumnShuffleCipherNoDashes("WEATTACKATDAWN", "0213")
Message: WEATTACKATDAWN
Key: 0213

Initial Grid:		Rearranged Grid:
W E A T			W A E T
T A C K			T C A K
A T D A			A D T A
W N 			W   N  

Encrypted Message: WTAWACDEATNTKA
Message to Return: 0213WTAWACDEATNTKA

Function call: encodeColumnShuffleCipherNoDashes("WEATTACKATDAWN", "1320")
Message: WEATTACKATDAWN
Key: 1320

Initial Grid:		Rearranged Grid:
W E A T			T W A E
T A C K			K T C A
A T D A			A A D T
W N - -			  W   N

Encrypted Message: TKAWTAWACDEATN
Message to Return: 1320TKAWTAWACDEATN
```
Write the function decodeColumnShuffleCipherNoDashes, which takes an encoding as described above, and returns the plaintext that generated the encoding. For example, decodeColumnShuffleCipherNoDashes("1320TKAWTAWACDEATN") returns "WEATTACKATDAWN".

Note: For this problem we have not provided any testcases for you in the homework file. Your are responsible for creating your own testcases.