CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Lab 3 (Due Thursday 2-Feb, 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
  Your group will be confirmed via email before Wednesday at 8am. At that point your group is final unless your group members are unresponsive, in which case you should email Eddie (edryer).


• 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_s17_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 7 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. encodeRightLeftCipher(message, rows) [35 pts]
   Background: A right-left cipher, a kind of route cipher, is a fairly simple way to encrypt a message. It takes two values, some plaintext and a number of rows, and it first constructs a grid with that number of rows and the minimum number of columns required, writing the message in successive columns. For example, if the message is WEATTACKATDAWN, with 4 rows, the grid would be:
   
   

      W T A W
      E A T N
      A C D
      T K A
   

   We will assume the message only contains uppercase letters. We'll fill in the missing grid entries with lowercase letters starting from z and going in reverse (wrapping around if necessary), so we have:

      W T A W
      E A T N
      A C D z
      T K A y
   

   Next, we encrypt the text by reading alternating rows first to the right ("WTAW"), then to the left ("NTAE"), then back to the right ("ACDz"), and back to the left ("yAKT"), until we finish all rows. We precede these values with the number of rows itself in the string. So the encrypted value for the message WEATTACKATDAWN with 4 rows is "4WTAWNTAEACDzyAKT".
   
   With this in mind, write the function encodeRightLeftCipher(message, rows) that takes an all-uppercase message and a positive integer number of rows, and returns the encoding as just described.


3. decodeRightLeftCipher(encodedMessage) [35 pts]
   Write the function decodeRightLeftCipher, which takes an encoding from the previous problem and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeRightLeftCipher("4WTAWNTAEACDzyAKT") returns "WEATTACKATDAWN".