Homework 7

Due Tuesday 26-Oct, at 10:00pm

To start

Create a folder named ‘hw7’
Create a new file, hw7.py, in that folder
Edit hw7.py and modify the functions as required
When you have completed and fully tested hw7, submit hw7.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

Some important notes

This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
Do not hardcode the test cases in your solutions.
We are not giving you any starter code this week. That means you need to create your file from scratch and include your own testcases. For writing testcases, follow the style of testcases uses in the previous homeworks.
Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

Limitations

Do not use try/except this week. The autograder (or a manual CA review later) will reject your submission entirely if you do.

A Note About Style Grading

Like in the previous assignment, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading starts this week, so please use good style from now on!

For Problems Marked Recursive

The recursive problems require that you use recursion meaningfully in order to receive the points.
You also may not use loops -- no for loops or while on the problems marked recursive.
You may use helper functions, so long as they are not iterative.
You may use wrapper functions -- that is, your solution function may itself be a non-recursive (but also non-iterative) wrapper around a recursive helper function.
You may only use builtin functions if they don't iterate over something. So in particular, among many other builtins you may not use this week, you may not use sum, sort, sorted, min, or max this week (you can write your own recursive versions of these if you wish, though that is not required, and we did not do that for our sample solutions).

recursive alternatingSum(lst) [10 pts]
Write the function alternatingSum(lst) that takes a possibly-empty list of numbers, lst, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If lst is empty, return 0.

recursive onlyEvenDigits(L) [20 pts]
Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. Remember to not use strings.

Hint: We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.

Equation Classes [30 pts]
Write the Polynomial and Quadratic classes so that they pass testEquationClasses and use the OOP constructs we learned this week as appropriate.

def testPolynomialBasics(): # we'll use a very simple str format... assert(str(Polynomial([1,2,3])) == "Polynomial(coeffs=[1, 2, 3])") p1 = Polynomial([2, -3, 5]) # 2x**2 -3x + 5 assert(p1.degree() == 2) # p.coeff(i) returns the coefficient for x**i assert(p1.coeff(0) == 5) assert(p1.coeff(1) == -3) assert(p1.coeff(2) == 2) # p.evalAt(x) returns the polynomial evaluated at that value of x assert(p1.evalAt(0) == 5) assert(p1.evalAt(2) == 7) def testPolynomialEq(): assert(Polynomial([1,2,3]) == Polynomial([1,2,3])) assert(Polynomial([1,2,3]) != Polynomial([1,2,3,0])) assert(Polynomial([1,2,3]) != Polynomial([1,2,0,3])) assert(Polynomial([1,2,3]) != Polynomial([1,-2,3])) assert(Polynomial([1,2,3]) != 42) assert(Polynomial([1,2,3]) != "Wahoo!") # A polynomial of degree 0 has to equal the same non-Polynomial numeric! assert(Polynomial([42]) == 42) def testPolynomialConstructor(): # If the list is empty, treat it the same as [0] assert(Polynomial([]) == Polynomial([0])) assert(Polynomial([]) != Polynomial([1])) # In fact, disregard all leading 0's in a polynomial assert(Polynomial([0,0,0,1,2]) == Polynomial([1,2])) assert(Polynomial([0,0,0,1,2]).degree() == 1) # Require that the constructor be non-destructive coeffs = [0,0,0,1,2] assert(Polynomial(coeffs) == Polynomial([1,2])) assert(coeffs == [0,0,0,1,2]) # Require that the constructor also accept tuples of coefficients coeffs = (0, 0, 0, 1, 2) assert(Polynomial(coeffs) == Polynomial([1,2])) def testPolynomialInSets(): s = set() assert(Polynomial([1,2,3]) not in s) s.add(Polynomial([1,2,3])) assert(Polynomial([1,2,3]) in s) assert(Polynomial([1,2,3]) in s) assert(Polynomial([1,2]) not in s) def testPolynomialMath(): p1 = Polynomial([2, -3, 5]) # 2x**2 -3x + 5 # p.scaled(scale) returns a new polynomial with all the # coefficients multiplied by the given scale p2 = p1.scaled(10) # 20x**2 - 30x + 50 assert(isinstance(p2, Polynomial)) assert(p2.evalAt(0) == 50) assert(p2.evalAt(2) == 70) # p.derivative() will return a new polynomial that is the derivative # of the original, using the power rule: # More info: https://www.mathsisfun.com/calculus/power-rule.html p3 = p1.derivative() # 4x - 3 assert(type(p3) == Polynomial) assert(str(p3) == "Polynomial(coeffs=[4, -3])") assert(p3.evalAt(0) == -3) assert(p3.evalAt(2) == 5) # we can add polynomials together, which will add the coefficients # of any terms with the same degree, and return a new polynomial p4 = p1.addPolynomial(p3) # (2x**2 -3x + 5) + (4x - 3) == (2x**2 + x + 2) assert(type(p4) == Polynomial) assert(str(p4) == "Polynomial(coeffs=[2, 1, 2])") assert(p1 == Polynomial([2, -3, 5])) assert(p4.evalAt(2) == 12) assert(p4.evalAt(5) == 57) # can't add a string and a polynomial! assert(p1.addPolynomial("woo") == None) # lastly, we can multiple polynomials together, which will multiply the # coefficients of two polynomials and return a new polynomial with the # correct coefficients. # More info: https://www.mathsisfun.com/algebra/polynomials-multiplying.html p1 = Polynomial([1, 3]) p2 = Polynomial([1, -3]) p3 = Polynomial([1, 0, -9]) assert(p1.multiplyPolynomial(p2) == p3) # (x + 3)(x - 3) == (x**2 - 9) assert(p1 == Polynomial([1, 3])) # (x**2 + 2)(x**4 + 3x**2) == (x**6 + 5x**4 + 6x**2) p1 = Polynomial([1,0,2]) p2 = Polynomial([1,0,3,0,0]) p3 = Polynomial([1,0,5,0,6,0,0]) assert(p1.multiplyPolynomial(p2) == p3) def testPolynomialClass(): print('Testing Polynomial class...', end='') testPolynomialBasics() testPolynomialEq() testPolynomialConstructor() testPolynomialInSets() testPolynomialMath() print('Passed!') def testQuadraticClass(): import math print("Testing Quadratic class...", end="") # Quadratic should inherit properly from Polynomial q1 = Quadratic([3,2,1]) # 3x^2 + 2x + 1 assert(type(q1) == Quadratic) assert(isinstance(q1, Quadratic) and isinstance(q1, Polynomial)) assert(q1.evalAt(10) == 321) assert(str(q1) == "Quadratic(a=3, b=2, c=1)") # We use the quadratic formula to find the function's roots. # More info: https://www.mathsisfun.com/quadratic-equation-solver.html # the discriminant is b**2 - 4ac assert(q1.discriminant() == -8) # use the discriminant to determine how many real roots (zeroes) exist assert(q1.numberOfRealRoots() == 0) assert(q1.getRealRoots() == [ ]) # Once again, with a double root q2 = Quadratic([1,-6,9]) assert(q2.discriminant() == 0) assert(q2.numberOfRealRoots() == 1) [root] = q2.getRealRoots() assert(math.isclose(root, 3)) assert(str(q2) == "Quadratic(a=1, b=-6, c=9)") # And again with two roots q3 = Quadratic([1,1,-6]) assert(q3.discriminant() == 25) assert(q3.numberOfRealRoots() == 2) [root1, root2] = q3.getRealRoots() # smaller one first assert(math.isclose(root1, -3) and math.isclose(root2, 2)) # Creating a non-quadratic "Quadratic" is an error ok = False # the exception turns this to True! try: q = Quadratic([1,2,3,4]) # this is cubic, should fail! except: ok = True assert(ok) # one more time, with a line, which is sub-quadratic, so also fails ok = False try: q = Quadratic([2,3]) except: ok = True assert(ok) # And make sure that these methods were defined in the Quadratic class # and not in the Polynomial class (we'll just check a couple of them...) assert('evalAt' in Polynomial.__dict__) assert('evalAt' not in Quadratic.__dict__) assert('discriminant' in Quadratic.__dict__) assert('discriminant' not in Polynomial.__dict__) print("Passed!") def testEquationClasses(): testPolynomialClass() testQuadraticClass()

Turtle Script [40 pts]

This problem is designed to get you more practice with using dictionaries, processing strings and get you thinking about recursion. This homework has been adapted from the presentation of Eric Roberts for nifty assignments at SIGCSE 2013.

Even though this problem has some recursion, you are not limited by the recursion rules listed at the beginning of this handout. (Feel to use loops, iterative helper functions, etc.)

Turtle Refresher

turtle is a Python module that allows for drawing of simple figures. In order to use it, you give an imaginary on-screen turtle commands regarding where to go, and it draws a line along its path.

The details of turtle library can be found at http://docs.python.org/library/turtle.html

Consider the following very simple turtle program which makes use of some basic turtle functionality to draw two squares:

import turtle
turtle.pendown()
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.penup()
turtle.forward(100)
turtle.pendown()
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(50)
turtle.penup()
turtle.forward(100)

(You should run this in Python and convince yourself you understand how it works.)

Turtle Script

In order to simplify the usage of turtle, we have designed a new language for writing turtle programs. We call it Turtle Script. A Turtle Script program is specified as a string consisting of a sequence of commands. For example, consider the following Turtle Script program:

F120 L90 F120 L90 F120 L90 F120

This program moves the turtle in a square 120 pixels on a side, ending up in the same position and orientation as when it started, like so:

Repetition

Turtle Script also includes the concept of repetition. If you enclose a sequence of commands in curly braces, you can repeat that entire sequence any number of times by preceding that block of commands with the letter X followed by the desired number of repetitions. The program to draw a square can therefore be simplified like this:

X4 {F120 L90}

In English pseudocode form, this program therefore has the following effect:

Repeat the following sequence of commands 4 times
  Move forward 120 pixels.
  Turn left 90 degrees.

Repetitions can be nested to any level. You could, for example, use the program:

X4 {X4 {F120 L90} L10}

to draw two squares with a 10-degree left turn in the middle.The figure after drawing these four squares looks like this:

Functions

Turtle Script also includes functions. You can define a function by enclosing the body of the function in braces and then preceding the braces with the command M followed by a single character name for the function. The following example shows a definition of a function called S that draws a square:

MS {F120 L90 F120 L90 F120 L90 F120 L90}

The keyword M specifies that the following is a function name, followed by function body enclosed in braces. Remember that the M command only defines a function but does not execute it. After this function has been defined, you can use the function name to call this function. Here is an example of defining a function and then calling it two times:

MS { X4 { L90 F50}} S U F100 D S

This program will create two squares in a single line separated by 50 pixels.

Turtle Command Summary

Command	Description
`Fn`	Move the turtle forward by n pixels. If n is missing move by default value of 50 pixels.
`Ln`	Turn the turtle left by n degrees, where n defaults to 90
`Rn`	Turn the turtle right by n degrees, where n defaults to 90
`D`	Calls the pendown function from Turtle
`U`	Calls the penup function from Turtle
`Xn cmds`	Repeats the specified block of commands n times.
`MA cmds`	Defines a function A where A is any single character not already reserved. The function A consists of the commands specified in the block. A cannot be one of the other commands (F, L, R, D, U, X, or M).
`A`	Execute the function A. A is just a placeholder, you can use any character to define a function. A cannot be one of the other commands (F, L, R, D, U, X, or M).

Functions to Write

Here are the functions you should write while solving this problem.

Function 1: `tokenizeTurtleScript(program)`

Write a function called tokenizeTurtleScript(program) which, given a Turtle Script program, return a list of commands in that program. The function should break up the input string into individual commands and return a list containing commands as strings.

The most common kind of token in a turtle program is a command character (typically a letter, although any non-whitespace character is legal), which is typically followed by a sequence of decimal digits. For example, the command F120, which moves the turtle forward 120 pixels, is a single token in a turtle program. All command listed in the table above are individual tokens, including repetition and function definitions.

In addition, spaces are not required between tokens but are permitted for readability. These rules mean, for example, that you could rewrite the program that draws a square as:

F120L90F120L90F120L90F120

even though doing so makes the program much more difficult for people to read.

Consider the following examples:

tokenizeTurtleScript("F120L90F120L90F120L90F120") returns
['F120', 'L90', 'F120', 'L90', 'F120', 'L90', 'F120']

tokenizeTurtleScript("X4 {F120 L90} U F200 X4 {F120 L90}") returns
['X4{F120L90}', 'U', 'F200', 'X4{F120L90}']

tokenizeTurtleScript("MS { X4 { L90 F50}} S U F100 D S") returns
['MS{X4{L90F50}}', 'S', 'U', 'F100', 'D', 'S']

Note: This problem is made much easier if you plan ahead by choosing good helper functions.

Function 2: `convertTurtleScript(program, funcs)`

Write a function convertTurtleScript(program, funcs) that will convert a Turtle Script program to a Python program. It should take as arguments a Turtle Script program and a dictionary consisting of all the functions defined so far in the program. The dictionary will contain function names as keys and function code as values.

The convertTurtleScript function has the responsibility of taking the program and translating each token to the appropriate command for turtle in Python. For example, given the program tokens:

['F120', 'L90', 'F120', 'L90', 'F120', 'L90', 'F120']

The convertTurtleScript function will have to translate each token into the appropriate function call in Python. Thus, executing the F120 token needs to invoke the function call turtle.forward(120). Similarly, executing the L90 token needs to invoke a call to turtle.left(90)

Notes:

You should call tokenizeTurtleScript in order to convert the program to tokens, and then execute the tokens one at a time.
This function does not return anything. Instead, it prints the Python program.
You should make this function recursive when necessary. Recursion makes handling the repetition tokens (X) and the function tokens (M) much easier.
The funcs argument that is passed to this function is a dictionary to map function names to function code. Recall that functions are defined as part of Turtle Script. Hence, as you are executing commands you will come across function definitions. When you do, add those functions to the funcs dictionary. Later, if a function is being called, you can retrieve that function’s commands from the dictionary. For the initial call to convertTurtleScript, you should just pass an empty dictionary.

Consider the following examples.

First,

p = "F120 L90 F120 L90 F120 L90 F120"
funcs = dict()
convertTurtleScript(p, funcs)

will print out:

turtle.forward(120)
turtle.left(90)
turtle.forward(120)
turtle.left(90)
turtle.forward(120)
turtle.left(90)
turtle.forward(120)

Second,

p = "MS { X4 { L90 F50}} S U F100 D S"
funcs = dict()
convertTurtleScript(p, funcs)