15-112
Spring-17

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

CMU 15-112 Spring 2017: Fundamentals of Programming and Computer Science
Lab 4 (Due Thursday 9-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).
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.
Reminder: do not work on these problems alone -- only work on them together with your lab partners!

  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. makeLetterTypePieChart(text, winWidth=500, winHeight=500) [25 pts] [manually graded] [25 pts]
    Write the function makeLetterTypePieChart that takes one required parameter -- some text (which is just a string) -- and two optional parameters, the winWidth and winHeight. The function displays a window of the given size and fills it with a pie chart that indicates the number of vowels, consonants, and other characters in the text, with these constraints:
    1. The fill color for vowels should be pink, consonants should be cyan, and others should be lightGreen.
    2. Do not count whitespace characters at all. Hint: the isspace method can be handy here.
    3. Draw the labels in 12-point Arial bold, formatted exactly as noted in the images below -- the letter type, and then in parentheses, the number of that letter type "of" the total number of non-whitespace characters, a comma, and then that ratio as an integer percentage.
    4. Center the text in the center of the pie wedge.
    5. The pink wedge (if it is present) must start at the vertical, followed counterclockwise by cyan, then lightGreen.
    6. Do not draw a wedge if there are no characters of that type.
    7. If all the characters are of a single type, draw a whole circle, with the label centered in the circle.
    8. If there are no vowels, consonants, or other non-whitespace characters, then display "No data to display" centered in the window, in 20-point Arial bold.
    9. The pie chart should fill 90% of the smaller of the window's width or height.

    For example, this call:
       makeLetterTypePieChart("AB, c de!?!")
    produces this result:


    And this call:
       makeLetterTypePieChart("AB e")
    produces this result:


    And this call:
       makeLetterTypePieChart("A")
    produces this result:


    And this call:
       makeLetterTypePieChart(" ")
    produces this result:


    Note: to do this, you will need to use the canvas.create_arc method. This method takes 4 required parameters, the bounding box of a circle, and then two more named (keyword) parameters -- the start angle of the arc, in degrees, and the so-called extent (or angle from the start angle to the end angle), also in degrees.

    For example, in a 300x300 window, these calls:
       canvas.create_rectangle(100, 100, 250, 250) # to see the bounding box
       canvas.create_arc(100, 100, 250, 250, start=90, extent=45, fill="blue")
    produces this result: