CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Lab 3 (Due Thursday 14-Sep, at 10pm)

---

This lab has 2 required forms -- one to make groups and one to peer-review each others' groupwork (in terms of being great groupmates, not in terms of getting right answers).

• Group Formation Form: Due Tuesday 11:59pm [2.5 pts]
  Fill out one of the following forms:
  • If you already have a group, fill out this form (one per group!)
  • If you need a new group, fill out this form


• Group Peer-Review Form: Due Thursday 11:59pm [2.5 pts]
  Fill out this peer review form once for each member of your group.

---

• This lab is Collaborative. No solo work allowed!. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details. Be sure to list your collaboration partners (name and andrew id) in a comment on the first line of this file!
• Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone.
• Be a good lab partner! Help everyone in your lab group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the lab group is following and understanding. The goal is to learn, not just to finish.
• To start:
  1. Create a folder named 'week3'
  2. Download both lab3.py and cs112_f17_week3_linter.py to that folder
  3. Edit lab3.py using pyzo
  4. When you are ready, submit lab3.py to autolab. For this lab, you may submit up to 8 times, but only your last submission counts.
• Do not use lists or recursion this week.
• Do not hardcode the test cases in your solutions.

---

Reminder: do not work on these problems alone -- only work on them together with your lab partners!

1. longestCommonSubstring(s1, s2) [25 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"
   



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 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.


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("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: WTAWACD-EATNTKA-
   Message to Return: 0213WTAWACD-EATNTKA-
   

   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, the 0th column becomes first, then the 2nd column, then the 1st, and then the 3rd. 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.