CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 10 (Due Thursday 30-Mar, at 10pm)

• Group Formation Form: Due Tuesday 11:59pm [2.5 pts]
  Fill out one of the following forms:
  • If you already have a group, fill out this form (one per group!)
  • If you need a new group, fill out this form
  Once you submit one of these forms your group is final for the lab unless your group members are unresponsive, in which case you should email Eddie (edryer).


• Group Peer-Review Form: Due Thursday 11:59pm [2.5 pts]
  Fill out this peer review form once for each member of your group.

• This lab is Collaborative. No solo work allowed. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details.
• Starter files: No starter files this week, though as usual you should use our standard linter.
• This week you may use up to 5 submissions. Only your last submission counts.
• Everything in this lab must be recursive! No iteration allowed! In particular, you may not use 'for' or 'while' anywhere. Actually, there is one exception: you may use them for zap3 (see the comment below).
• 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).
• The autograder will check correctness, but we will have to manually grade some problems to confirm you followed the restrictions, such as using recursion meaningfully.
• Do not hardcode the test cases in your solutions.
• As usual, there are no late days for this lab.

1. recursive alternatingSum(L) [15 pts] [autograded]
   Write the function alternatingSum(L) that takes a possibly-empty list of numbers, L, and returns their alternating sum, 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 L is empty, return 0.


2. recursive powerSum(n, k) [15 pts] [autograded]
   Write the function powerSum(n, k) that takes two possibly-negative integers n and k and returns the so-called power sum:
      1**k + 2**k + ... + n**k
   If n is negative, return 0. Similarly, if k is negative, return 0.


3. recursive powersOf3ToN(n) [15 pts] [autograded]
   Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n, or None (not an empty list) if no such values exist. As an example, powersOf3ToN(10.5) returns [1, 3, 9].


4. recursive zaps! [15 pts] [autograded]
   Here you will write 3 recursive functions that each work similarly to the builtin zip function. Note that you may not use the builtin zip function in your solution. The first function, zap1(L,M), takes two lists L and M, and returns a single list of tuples from each list in order. So:

       assert(zap1([1,2],[3,4]) == [(1,3), (2,4)])
       assert(zap1([1,2,3,4,5],[6,7,8,9,10]) == [(1,6),(2,7),(3,8),(4,9),(5,10)])
   

   What happens when there are more elements in L than M, or in M than L? In either case, zap1 works like builtin zip, in that it stops as soon as there are no longer enough elements, ignoring the extras. That is:

       # zap1 is same as zip (stops when one list runs out)
       assert(zap1([1,2],[3,4,5]) == [(1,3), (2,4)])
       assert(zap1([1,2,3],[4,5]) == [(1,4), (2,5)])
   

   As for zap2, for same-length lists, zap2(L,M) works the same as zap1(L,M):

       assert(zap2([1,2],[3,4]) == [(1,3), (2,4)])
   

   But for different-length lists, zap2(L,M) uses all the values available, adding None's as necessary for missing values, as such:

       # zap2 uses None when no values are available 
       assert(zap2([1,2],[3,4,5]) == [(1,3), (2,4), (None, 5)])
       assert(zap2([1,2,3],[4,5]) == [(1,4), (2,5), (3, None)])
   

   As for zap3, for same-length lists, zap3(L,M) also works the same as zap1(L,M):

       assert(zap3([1,2],[3,4]) == [(1,3), (2,4)])
   

   But for different-length lists, zap3(L,M) only uses the available values, so the resulting tuples may have differing lengths, as such:

       # zap3 uses only the available values (so tuples may have different lengths)
       assert(zap3([1,2],[3,4,5]) == [(1,3), (2,4), (5,)])
       assert(zap3([1,2,3],[4,5]) == [(1,4), (2,5), (3,)])
   

   Finally, while zap1 and zap2 each take exactly 2 lists, zap3 has to work with any number of lists, so it takes variable-length args (*args), as such:

       # Also, just zap3 has to support a variable # of args, so:
       assert(zap3([1],[2,3],[4],[5],[6,7,8],[9]) == [(1,2,4,5,6,9),(3,7),(8,)])
   

   Hint: When you call zap3 recursively, you'll have to unpack an args list into individual arguments, which is done by calling zap3(*args). Notice that we use the * in the function call. To understand unpacking a bit more, carefully study this code:

   def f(x,y): return x+y
   L = [1,2]
   print(f(L))  # crash: TypeError: f() missing 1 required positional argument: 'y'
   print(f(*L)) # prints 3
   

   Remember: you may not use builtin zip anywhere in this hw! Also, as noted above, you may use for or while in zap3 -- in particular to iterate through all the variable-length arguments (the *args list) -- so long as you still use recursion meaningfully in some way (and this is only true for zap3 -- you still may not use for or while anywhere else in this lab).


5. Line class [40 pts] [autograded]
   Write the Line class so that it passes testLineClass, and uses the OOP constructs we learned this week as appropriate.
   def testLineClass(): print('Testing Line class...', end='') assert(str(Line(2,5)) == "y=2x+5") assert(str(Line(2,-5)) == "y=2x-5") assert(str(Line(0,5)) == "y=5") assert(str(Line(1,5)) == "y=x+5") assert(str(Line(-1,5)) == "y=-x+5") assert(str(Line(0,-5)) == "y=-5") assert(str(Line(0,0)) == "y=0") line1 = Line(2,3) assert(str(line1) == "y=2x+3") assert(line1.getSlope() == 2) assert(type(line1.getSlope()) == int) assert(line1.getIntercept() == 3) line2 = Line(6,-5) assert(str(line2) == "y=6x-5") assert(line2.getSlope() == 6) assert(line2.getIntercept() == -5) (x,y) = line1.getIntersection(line2) # (2, 7) assert(almostEqual(x, 2) and almostEqual(y, 7)) line3 = Line(2, -3) (x,y) = line3.getIntersection(line2) # (0.5, -2) assert(almostEqual(x, 0.5) and almostEqual(y, -2)) # parallel lines do not intersect assert(Line(2,3).getIntersection(Line(2,4)) == None) assert(line3.isParallelTo(line1) == True) assert(line3.isParallelTo(line2) == False) # getHorizontalLine returns a line that is horizontal # to the given line, intersecting at the given x value. line4 = line3.getHorizontalLine(4) assert(str(line4) == "y=5") assert(line4.getSlope() == 0) assert(line4.getIntercept() == 5) assert(Line(1, 2) == Line(1, 2)) assert(Line(1, 2) != Line(1, 3)) assert(not (Line(1, 2) == "don't crash here!")) s = set() assert(Line(1, 2) not in s) s.add(Line(1, 2)) assert(Line(1, 2) in s) s.remove(Line(1, 2)) assert(Line(1, 2) not in s) print('Passed.')