CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Homework 9 (Due Sunday 30-Oct, at 8pm)

• This hw is SOLO. See the syllabus for more details.
• Everything in this hw must be recursive! No iteration allowed! In particular, you may not use 'for' or 'while' anywhere.
• You also may not use 'zip' or 'join' (which generally are not useful here, but in one or two cases could be used to avoid the recursive solution you should be finding).
• Starter files: hw9.py and cs112_f16_wk9.py
• This week you may use up to 6 submissions. Only your last submission counts.
• The autograder will check correctness, but we will have to manually grade some problems to confirm you followed the restrictions, such as only using one statement or only using map/filter/reduce/lambda appropriately (basically, for the questions requiring map/filter/reduce, you may not use iteration or recursion -- see some map/filter/reduce examples for details).
• Do not hardcode the test cases in your solutions.

1. isHappyNumber(n) [15 pts] [autograded]
   Recalling the definition of happy numbers from hw2, write the function isHappyNumber(n) which takes a possibly-negative integer and returns True if it is happy and False otherwise. Note that all numbers less than 1 are not happy.


2. binarySearchValues(L, v) [15 pts] [autograded]
   Write the function binarySearchValues(L, v) that takes a sorted list L and a value v and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not v is in L. As an example, say:

      L = ['a', 'c', 'f', 'g', 'm', 'q']
      v = 'c'
   

   Binary search always searches between some lo and hi index, which initially are 0 and (len(L)-1). So here, lo=0 and hi=5. The first index we try, then, is mid=2 (the integer average of lo and hi). The value there is 'f', so we will add (2, 'f') to our result.
   
   Since 'f' is not the value we are seeking, we continue, only now we are searching from lo=0 to hi=1 (not hi=2 because we know that index 2 was too high!).
   
   Now we try mid=0 (the integer average of lo and hi), and so we add (0, 'a') to our result.
   
   We see that 'a' is too low, so we continue, only now with lo=1 and hi=1. So we add (1, 'c') to our result. We found 'c', so we're done. And so we see:

       L = ['a', 'c', 'f', 'g', 'm', 'q']
       v = 'c'
       assert(binarySearchValues(L, v) == [(2,'f'), (0,'a'), (1,'c')])
   

   Hint: Do not slice the list L, but rather adjust the indexes into L.


3. evalPrefixNotation(L) [15 pts] [autograded]
   Background: in so-called 'prefix notation', an arithmetic expression is listed with the operator first. So instead of writing '2 + 3' we would write '+ 2 3'. Actually, for this problem, we'll represent the expression in a list, so we'd write ['+', 2, 3]. Each value can itself be another full expression, so for example we could have:

       ['+', 2, '*', 3, 4]
   

   This would be the same as (2 + (3 * 4)), or 14. Again, we could have:

       ['+', '*', 2, 3, '*', 4, 5]
   

   This would be the same as ((2 * 3) + (4 * 5)), or 26. Look at the test function in the code for a few more examples.
   
   With this in mind, write the function evalPrefixNotation(L) that takes a list L that contains a legal arithmetic expression in prefix notation, as just described, and returns the value that the expression evaluates to.
   
   Your function only needs to work for '+', '-', and '*'. If you see any other operators, raise an exception as such:

       raise Exception('Unknown operator: ' + operator)
   

   
   Hint: after removing the first element, if it is an operator, you should use evalPrefixNotation to recursively evaluate the operands for that operator.
   Take the time to really think about that hint! Also, for what it is worth, our sample solution used L.pop(0) to destructively remove the first element. We could then test if it was a string (and so an operator, like '+', or '-', etc) and do one thing, or if it is an int, and do something else.


4. intPairsAsTuples(L) [7.5 pts] [autograded]
   First, write the helper function isIntPair(L) that takes an arbitrary value L and returns True if it an 'int pair' and False otherwise, where we shall call an 'int pair' any Python value (of any type) that has a length of 2 and each of those 2 values are ints. Note that you are not guaranteed that L is a list or a tuple -- it could be any type, including types that crash if you take their length. Relatedly, note that we used try/except in our sample solution to this problem.
   
   Next, using map/filter/reduce, and using the isIntPair helper function you just wrote, write the one-statement function intPairsAsTuples(L) that takes a list L of arbitrary Python values, and returns a tuple of tuples of the int pairs in L. For example:

       L = [ 1, 2, True, "wow!", (3, 4), [5, 6], [7, 8, 9]]
   

   The int pairs in L are (3, 4) and [5, 6], so:

       intPairsAsTuples(L) returns ((3, 4), (5, 6))
   

   Remember that your solution must be only one statement of Python (not counting the lines for the helper function).


5. longestStrippedLine(lines) [7.5 pts] [autograded]
   Using reduce, map, and lambda, write the one-statement function longestStrippedLine(lines) that takes a single multi-line string and returns the longest stripped line in that string, where a stripped line excludes leading and trailing whitespace (hint: s.strip() might be handy here). So:

       lines = """
       abc def
       ghij
       kl
       mnop qrst
       uv
       """
       longestStrippedLine(lines) returns 'mnop qrst'
   

   While your solution technically must be only one statement of Python, you can insert a newline or two as needed strictly to avoid going over 80 characters width.


6. Polynomial class [40 pts] [autograded]
   Write the Polynomial class so that it passes testPolynomialClass, and uses the OOP constructs we learned this week as appropriate.
   def testPolynomialClass(): print('Testing Polynomial class...', end='') testPolynomialBasics() testPolynomialEq() testPolynomialConstructor() testPolynomialInSets() print('Passed.') 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) # 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) 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])) # Remove leading 0's 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)


7. Optional/Bonus: recursiveTetris() [5 pts] [manually graded]
   Below the #ignore_rest line, write the function recursiveTetris() that takes no arguments and when called plays Tetris, though of course without any iteration in the implementation. Have fun!