CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Lab 4 (Due Thursday 22-Sep, at 10pm, no extensions or grace days)

---

• 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.
• Starter files: lab4.py and cs112_f16_wk4.py
• This week you may use up to 6 submissions. Only your last submission counts.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

---

Note: be sure to use our starter files, and in any case, be sure to place your graphics code (including the tkinter import line) below the #ignore_rest line, so the autograder ignores it. Since tkinter is not available on the autograder server, if you include tkinter above the #ignore_rest line, your code will crash and you will receive a 0 for that submission.

---

1. lookAndSay(a) [25 pts]
   First, read about look-and-say numbers here. Then, write the function lookAndSay(a) that takes a list of numbers and returns a list of numbers that results from "reading off" the initial list using the look-and-say method, using tuples for each (count, value) pair. For example:

     lookAndSay([]) == []
     lookAndSay([1,1,1]) == [(3,1)]
     lookAndSay([-1,2,7]) == [(1,-1),(1,2),(1,7)]
     lookAndSay([3,3,8,-10,-10,-10]) == [(2,3),(1,8),(3,-10)]
   



2. inverseLookAndSay(a) [25 pts]
   Write the function inverseLookAndSay(a) that does the inverse of the previous problem, so that, in general:

     inverseLookAndSay(lookAndSay(a)) == a
   

   Or, in particular:

     inverseLookAndSay([(2,3),(1,8),(3,-10)]) == [3,3,8,-10,-10,-10]
   

   
   
3. solvesCryptarithm(puzzle, solution) [25 pts]
   Background: a cryptarithm is a puzzle where we start with a simple arithmetic statement but then we replace all the digits with letters (where the same digit is replaced by the same letter each time). We will limit such puzzles to strings the form "A+B=C" (no spaces), where A, B, and C are positive integers. For example, "SEND+MORE=MONEY" is such a puzzle. The goal of the puzzle is to find an assignment of digits to the letters to make the math work out properly. For example, if we assign 0 to "O", 1 to "M", 2 to "Y", 5 to "E", 6 to "N", 7 to "D", 8 to "R", and 9 to "S" we get:

       S E N D       9 5 6 7
     + M O R E     + 1 0 8 5
     ---------     ---------
     M O N E Y     1 0 6 5 2
   

   And so we see that this assignment does in fact solve the problem! Now, we need a way to encode a possible solution. For that, we will use a single string where the index of the letter corresponds to the digit it represents. Thus, the string "OMY--ENDRS" represents the assignments listed above (the dashes are for unassigned digits).
   
   With this in mind, write the function solvesCryptarithm(puzzle, solution) that takes two strings, a puzzle (such as "SEND+MORE=MONEY") and a proposed solution (such as "OMY--ENDRS"). Your function should return True if substituting the digits from the solution back into the puzzle results in a mathematically correct addition problem, and False otherwise. You do not have to check whether a letter occurs more than once in the proposed solution, but you do have to verify that all the letters in the puzzle occur somewhere in the solution (of course). You may not use the eval() function. Also, you almost surely will want to write at least one well-chosen helper function.


4. drawCirclePattern(n) [25 pts] [manually-graded]
   Write the function drawCirclePattern(n) that takes one parameter, a positive int, and displays a graphics window, inside of which it draws the nxn version of this picture:
   
   While the image above shows two circle patterns, you only need to draw one at a time. For example, the left image above was drawn with 10 rows (and 10 columns), and the right image with 5 rows (and 5 columns). The pattern consists of "buttons" (or perhaps "bullseyes"), where each button is really several circles drawn on top of each other. Each circle in a "button" has a radius 2/3rds as large as the next-larger circle, which continues until the radius is less than 1. As for the color of each button, here are the rules to follow:
   
   Rule 1: Starting from the left-top corner, every 4th diagonal is entirely red.
   Rule 2: For the non-red buttons, starting from the top row, every 3rd row is entirely green.
   Rule 3: For the non-red and non-green buttons, starting from the second-to-leftmost column, every 2nd column is entirely yellow.
   Rule 4: Any non-red, non-green, and non-yellow button is blue.
   
   Note that these rules can be fairly easily implemented using a single if-elif-elif-else statement. Inside that statement, you might want to set a variable, say one named "color", based on each of these four conditions. Then you could draw with fill=color.
   
   Note: The drawing should mostly fill the window, and the 10x10 case should be about the same size as the 10x10 case in the image above, but the exact dimensions of the drawing are up to you.