CMU 15-112 Fall 2018: Fundamentals of Programming and Computer Science
Homework 4 (Due Sunday 23-Sep, at 5pm)




  1. Style Meetings [0pts]
    Attend office hours with a TA and briefly discuss how to improve your programming style (based on your hw3 submission) in order to regain points lost on hw3 because of style errors. To make the best use of this time, come prepared by reading the feedback you received on style from hw3. The TA will discuss the most important deductions on hw3 and how to improve your tyle in general. At the TA's sole discretion, we will return lost points on hw3 due to style errors. Have this feedback and hw3 ready on your laptop when you speak to the TA. You must have this meeting by the main assignment deadline, Sunday at 5pm.

  2. List Function Table [5pts]
    There are many different list functions that exist in Python which change the contents of the list. Some of these functions are destructive (changing the list they're called on), others are nondestructive (creating a new list as a result). Next to each of the functions listed below, write whether the function is destructive or non-destructive to the list a. Include your table in a triple-string comment in hw4.py.

    """
    c = a + b
    a += b
    a.append(x)
    a.insert(0, x)
    b = a[:i] + [x] + a[i:]
    a.remove(x)
    a.pop(0)
    b = a * 3
    a.reverse()
    reversed(a)
    a.sort()
    sorted(a)
    copy.copy(a)
    """

  3. COLLABORATIVE: lookAndSay(a) [10pts]
    First, read about look-and-say numbers here. Then, write the non-destructive 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.

  4. inverseLookAndSay(a) [10pts]
    Write the non-destructive function inverseLookAndSay(a) that does the inverse of the function lookAndSay from 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]
    

  5. bestScrabbleScore(dictionary, letterScores, hand) [25pts]
    Background: In a Scrabble-like game, players each have a hand, which is a list of lowercase letters. There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letterScores, which is length 26, where letterScores[i] contains the point value for the ith character in the alphabet (so letterScores[0] contains the point value for 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. The point value for a word is 0 if it is not in the dictionary, otherwise it is the sum of the point values of each letter in the word, according to the letterScores list (pretty much as it works in actual Scrabble).

    In case you are interested, here is a list of the actual letterScores for Scrabble:
       letterScores = [
       #  a, b, c, d, e, f, g, h, i, j, k, l, m
          1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3,
       #  n, o, p, q, r, s, t, u, v, w, x, y, z
          1, 1, 3,10, 1, 1, 1, 1, 4, 4, 8, 4,10
       ]
    
    Note that your function must work for any list of letterScores as is provided by the caller.

    With this in mind, write the function bestScrabbleScore(dictionary, letterScores, hand) that takes 3 lists -- dictionary (a list of lowercase words), letterScores (a list of 26 integers), and hand (a list of lowercase characters) -- and returns a tuple of the highest-scoring word in the dictionary that can be formed by some arrangement of some subset of letters in the hand, followed by its score. In the case of a tie, the first element of the tuple should instead be a list of all such words in the order they appear in the dictionary. If no such words exist, return None.
    The dictionary in this problem is a list of words, and thus not a true Python dictionary (which we haven't taught you and you may not use in this assignment)! It is OK to loop through the dictionary, even if the dictionary we provide is large.

    Note 0: You should definitely write helper functions for this problem! In fact, try to think of at least two helper functions you could use before writing any code at all.

    Note 1: You may not use itertools for this problem! In fact, you shouldn't need to create permutations of the letters at all...

  6. COLLABORATIVE: drawStar(canvas, centerX, centerY, diameter, numPoints, color, winWidth=500, winHeight=500) [15pts] [manually-graded]
    Write the function drawStar which takes a canvas and the star's center coordinates, diameter, number of points, and color (and optional parameters winWidth and winHeight), 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:



  7. drawCirclePattern(n, winWidth=500, winHeight=500) [15 pts] [manually-graded]
    Write the function drawCirclePattern(n, winWidth=500, winHeight=500) that takes a positive int (and optional parameters winWidth and winHeight) 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.

  8. COLLABORATIVE: runSimpleTortoiseProgram(program, winWidth=500, winHeight=500) [20 pts, manually-graded]
    In addition to the Tkinter, which we all know and love, Python usually comes with another graphics package called "Turtle Graphics", which you can read about here. We will definitely not be using turtle graphics in this problem (and you may not do so in your solution!), but we will instead implement a small turtle-like (or maybe turtle-inspired) graphics language of our own. We'll call it Tortoise Graphics.

    First, we need to understand how Tortoise Graphics programs work. Your tortoise starts in the middle of the screen, heading to the right. You can direct your tortoise with the following commands:

    • color name
      Set the drawing color to the given name, which is entered without quotes, and which can be "red", "blue", "green", or any other color that Tkinter understands. It can also be "none", meaning to not draw.

    • move n
      Move n pixels straight ahead, where n is a non-negative integer, while drawing a 4-pixel-wide line in the current drawing color. If the drawing color is "none", just move straight ahead without drawing (that is, just change the tortoise's location).

    • left n
      Turn n degrees to the left, without moving, where n is a non-negative integer.

    • right n
      Turn n degrees to the right, without moving, where n is a non-negative integer.

    Commands are given one-per-line. Lines can also contain comments, denoted by the hash sign (#), and everything from there to the end-of-line is ignored. Blank lines and lines containing only whitespace and/or comments are also ignored.

    With this in mind, write the function runSimpleTortoiseProgram(program, winWidth=500, winHeight=500) that takes a program as specified above and runs it, displaying a window (which is 500x500 by default) with the resulting drawing from running that program. Your function should also display the tortoise program in that window, in a 10-point font, in gray text, running down the left-hand side of the window (10 pixels from the left edge). Don't worry if the program is longer than can fit in the window (no need to scroll or otherwise deal with this). Also, you are not responsible for any syntax errors or runtime errors in the tortoise program.

    For example, this call:
    runSimpleTortoiseProgram("""
    # This is a simple tortoise program
    color blue
    move 50
    
    left 90
    
    color red
    move 100
    
    color none # turns off drawing
    move 50
    
    right 45
    
    color green # drawing is on again
    move 50
    
    right 45
    
    color orange
    move 50
    
    right 90
    
    color purple
    move 100
    """, 300, 400)
    

    produces this result in a 300x400 window:


    And this call:
    runSimpleTortoiseProgram("""
    # Y
    color red
    right 45
    move 50
    right 45
    move 50
    right 180
    move 50
    right 45
    move 50
    color none # space
    right 45
    move 25
    
    # E
    color green
    right 90
    move 85
    left 90
    move 50
    right 180
    move 50
    right 90
    move 42
    right 90
    move 50
    right 180
    move 50
    right 90
    move 43
    right 90
    move 50  # space
    color none
    move 25
    
    # S
    color blue
    move 50
    left 180
    move 50
    left 90
    move 43
    left 90
    move 50
    right 90
    move 42
    right 90
    move 50
    """)
    

    produces this result in a 500x500 window: