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