CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 4 (Due Thursday 21-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). Please note that peer reviews are used to keep groups running smoothly, and does not directly affect groupmate's grades.

• 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
  Once you submit one of these forms your group is final for the lab 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 'week4'
  2. Download both lab4.py and cs112_f17_week4_linter.py to that folder
  3. Edit lab4.py using Pyzo
  4. When you are ready, submit lab4.py to Autolab. For this lab, you may submit up to 6 times, but 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 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.

---

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

1. lookAndSay(a) [15 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)]
   

   Hint: you'll want to keep track of the current number and how many times it has been seen.


2. inverseLookAndSay(a) [10 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) [20 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. drawStar(canvas, centerX, centerY, diameter, numPoints, color) [25 pts, manually graded]
   Write the function drawStar which takes a canvas and the star's center coordinates, diameter, number of points, and color, and produces a star based on that specification. To draw a star, we need to identify where to place each of the inner and outer points, then draw them all together as a polygon.
   
   The outer points of the star should be evenly placed on a circle based on the specified diameter, with the first point at a 90 degree angle. The inner points should then be placed on a circle 3/8 the size of the first circle, halfway between the pairs of outer points. (We use this ratio to make a nice-looking five-pointed star. Actually, the best inner circle would be about 38.2% the size of the outer circle; a little trigonometry and problem-solving will tell you why! But 3/8 is close enough.) An example of how these circles work is shown below.
   
   
   
   
   For example, this call:
      drawStar(canvas, 250, 250, 500, 5, "gold")
   produces this result:
   
   And this call:
      drawStar(canvas, 300, 400, 100, 4, "blue")
   produces this result:
   
   And if we add a few more points:
      drawStar(canvas, 300, 200, 300, 9, "red")
   we get this result:
   
   
   Note: to test your code, you'll need to call drawStarHelper(centerX, centerY, diameter, numPoints, color), which sets up the canvas, then calls drawStar. We set up the function this way so that you can use drawStar in the final problem...


5. drawUnitedStatesFlag(winWidth=950, winHeight=500) [25 pts, manually graded]
   Write the function drawUnitedStatesFlag which draws the US flag in the provided dimensions. You can assume that the height:width ratio will be 10:19, as is the case with the actual US flag.
   
   You can find much useful information about the flag's dimensions on Wikipedia, but we do not expect you to match the actual US flag design perfectly; you should instead seek to create a reasonable approximation of the flag. However, your flag must meet the following requirements:
   
   
   • The flag should cover the entire provided width and height
   • The flag should have the correct number of stripes, alternating red and white in the correct order
   • The blue field in the upper left corner should cover exactly seven stripes and have a reasonably correct width
   • The flag should have the correct number of stars in the correct configuration, with the star size and spacing reasonably close to the actual flag
   
   For examples of what reasonable flags might look like, here are some instructor-created flags: