Homework 4

Due Sunday 10-Feb, at 8pm

• Reminder: all problems that are not explicitly marked COLLABORATIVE must be completed individually, as stated in the course syllabus.
• To start:
  1. Create a folder named ‘week4’
  2. Download both hw4.py and cs112_s19_week4_linter.py to that folder
  3. Edit hw4.py using Pyzo
  4. When you are ready, submit hw4.py to autolab. For this hw, you may submit up to 15 times (which is way more than you should require), but only your last submission counts.
• Do not use dictionaries, sets, or recursion this week.
• Do not hardcode the test cases in your solutions.

0. Mentor Meeting [5 pts]
   Every student in the class has been assigned a TA mentor. You are required to meet with your mentor for a quick, in-person checkin before the submission deadline of this assignment. The goal of the mentor is to see how you are doing and provide advice and tips for the class. Your mentor will get in touch with you by email in order to coordinate the meetings. From this point forward, you will meet with your mentor every week.


1. COLLABORATIVE: lookAndSay(a) [10 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. COLLABORATIVE: 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. COLLABORATIVE: drawStar(canvas, centerX, centerY, diameter, numPoints, color) [20 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...


4. COLLABORATIVE: drawQatarFlag(winWidth=760, winHeight=300): [15 pts, manually graded]
   Write the function drawQatarFlag which draws the Qatar flag in the provided dimensions. You can assume that the height:width ratio will be close to 11:28, as is the case with the actual Qatar flag.
   
   You can find much useful information about the flag's dimensions and colors on Wikipedia, but we do not expect you to match the actual Qatar 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 zig-zags
   • The colors should be correct (Note: The flag is not red...)
   
   For examples of what a reasonable flag might look like, here is an instructor-created flag:
   
   
   
   


5. bestScrabbleScore(dictionary, letterScores, hand) [20 pts]
   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.
   
   Note: 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.
   
   Another note: there is no fixed dictionary here. Each time we call the function, we may provide a different dictionary! It may contain 100 words or perhaps 100,000 words.


6. 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: