CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Homework 4 (Due Saturday 24-Sep, at 8pm)

• This hw is SOLO. See the syllabus for details.
• Starter files: hw4.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.

• Be sure to place your graphics code, including the import tkinter line, below the #ignore_rest line, as it already is in the starter file. Otherwise, the autograder will crash on the import line and you will score 0 on that submission.
• For runSimpleTortoiseProgram, and any other function that creates a window with graphics in it, you should adapt our runDrawing program in the course notes -- create a window ("root"), create a canvas for that window, pack the canvas (fit the window around it), do your drawing in a helper function, call the window's mainloop, and then you're done.

0. Friday optional OH [0 pts]
   Friday recitation is optional this week. We will staff the rooms all day and the TA's will host OH, to help you with your homework or any other concerns you may have. It's a great time to finish your homework, brush up on previous week's work, start talking about your term projects, etc. Attendance is optional, and you can stop by for any or all recitations, which run from 9:30am to 5:30pm all day!


1. bestScrabbleScore(dictionary, letterScores, hand) [50 pts] [autograded]
   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: 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,00 words.


2. runSimpleTortoiseProgram(program, winWidth=500, winHeight=500) [50 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 (say 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:
   


3. Bonus/Optional: staticMotionAfterEffect(winWidth, winHeight) [1 pt] [manually-graded]
   Using only Tkinter primitives (rectangles, ovals, polygons, arcs, etc), and no images, write a function named drawSpiral(winWidth, winHeight) that takes two ints and creates a window of the given dimensions, and then draws this picture (to fill the window as completely as possible):
   
   Have fun!


4. Bonus/Optional: drawSpiral(winWidth, winHeight) [1 pt] [manually-graded]
   Write a function named drawSpiral(winWidth, winHeight) that takes two ints and creates a window of the given dimensions, and then draws this picture (to fill the window as completely as possible):
   
   Here, you will draw both sides of the picture (the larger and smaller spirals), along with the title text (drawSpiral) and the boxes around the spirals.
   
   As for the image, each side will be a spiral (or really a series of spiral arms). The spiral arms must be created by drawing a series of circles (the only thing drawn to create the spirals in this exercise are small circles). There should be 28 arms, each arm composed of 32 circles. Each arm spirals, or bends, such that the outermost circle in the arm is drawn pi/4 radians (45 degrees) beyond the innermost circle in that same arm. Hint: You will have to use basic trigonometry here! Also, try to make the color gradients work as indicated (think rgbString).


5. Bonus/Optional: runSimpleProgram(program, args) [3 pts]
   First, carefully watch this video that describes this problem:
   
   Then, write the function runSimpleProgram(program, args) that works as described in the video, taking a legal program (do not worry about syntax or runtime errors, as we will not test for those cases) and runs it with the given args, and returns the result.
   
   Here are the legal expressions in this language:
   
   
   • [Non-negative Integer]
     Any non-negative integer, such as 0 or 123, is a legal expression.
   
   
   • A[N]
     The letter A followed by a non-negative integer, such as A0 or A123, is a legal expression, and refers to the given argument. A0 is the value at index 0 of the supplied args list. It is an error to set arg values, and it is an error to get arg values that are not supplied. And you may ignore these errors, as we will not test for them!
   
   
   • L[N]
     The letter L followed by a non-negative integer, such as L0 or L123, is a legal expression, and refers to the given local variable. It is ok to get an unassigned local variable, in which case its value should be 0.
   
   
   • [operator] [operand1] [operand2]
     This language allows so-called prefix expressions, where the operator precedes the operands. The operator can be either + or -, and the operands must each be one of the legal expression types listed above (non-negative integer, A[N] or L[N]).
   
   And here are the legal statements in this language (noting that statements occur one per line, and leading and trailing whitespace is ignored):
   
   
   • ! comment
     Lines that start with an exclamation (!), after the ignored whitespace, are comments and are ignored.
   
   
   • L[N] [expr]
     Lines that start with L[N] are assignment statements, and are followed by the expression (as described above) to be stored into the given local variable. For example: L5 - L2 42 This line assigns (L2 - 42) into L5.
   
   
   • [label]:
     Lines that contain only a lowercase word followed by a colon are labels, which are ignored except for when they are targets of jump statements.
   
   
   • JMP [label]
     This is a jump statement, and control is transferred to the line number where the given label is located. It is an error for such a label to not exist, and you may ignore that error.
   
   
   • JMP+ [expr] [label]
     This is a conditional jump, and control is transferred to the line number where the given label is located only if the given expression is positive. Otherwise, the statement is ignored.
   
   
   • JMP0 [expr] [label]
     This is another kind of conditional jump, and control is transferred only if the given expression is 0.
   
   
   • RTN [expr]
     This is a return statement, and the given expression is returned.
   
   Hints:
   1. Do not try to translate the program into Python! Even if you could do so, it is not allowed here. Instead, you are going to write a so-called interpreter. Just keep track of the local variables, and move line-by-line through the program, simulating the execution of the line as appropriate.
   2. You will find it useful to keep track of the current line number.
   3. How long do you run the program? Until you hit a RTN statement! You may assume that will always eventually happen.
   4. We used strip, split, and splitlines in our sample solution, though you of course may solve this how you wish.
   
   Finally, here is a sample test function for you. You surely will want to add some addition test cases. In fact, a hint would be to build your function incrementally, starting with the simplest test cases you can think up, which use the fewest expression and statement syntax rules. Then add more test cases as you implement more of the language.
   def testRunSimpleProgram(): print("Testing runSimpleProgram()...", end="") largest = """! largest: Returns max(A0, A1) L0 - A0 A1 JMP+ L0 a0 RTN A1 a0: RTN A0""" assert(runSimpleProgram(largest, [5, 6]) == 6) assert(runSimpleProgram(largest, [6, 5]) == 6) sumToN = """! SumToN: Returns 1 + ... + A0 ! L0 is a counter, L1 is the result L0 0 L1 0 loop: L2 - L0 A0 JMP0 L2 done L0 + L0 1 L1 + L1 L0 JMP loop done: RTN L1""" assert(runSimpleProgram(sumToN, [5]) == 1+2+3+4+5) assert(runSimpleProgram(sumToN, [10]) == 10*11//2) print("Passed!")


6. Bonus/Optional: linearRegressionVisualization [1 pt] [manually-graded]
   Do the linearRegression visualization from bonus #6 from here. Be sure to call your function linearRegressionVisualization (so the TA's can find it when grading).