CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 4-1 (Due Tue 23-Jul, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. There is no starter file for this assignment! You should create a file, hw4-1.py, to start.
  2. Edit hw4-1.py using Pyzo
  3. When you are ready, submit hw4-1.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
• Do not use sets or dictionaries in this assignment.
• Do not use any for or while loops in this assignment. However, there are some for loops in the OOP test cases. Make sure to put these (and any other test cases) beneath an "#ignore_rest" line in your code, so the autograder will ignore them.
• Do not hardcode the test cases in your solutions.
• Remember to write your own test cases, and in general, follow the style guide!

1. Mid-Summer-Session Feedback [5 pts] [autograded]
   Fill out this feedback form to give us some feedback on how we're doing so far! At the end of the form, you'll be sent to another link to actually get credit, so that your feedback can stay anonymous. Don't forget to fill out the second form!
   Also, please fill out the TA feedback form (once per TA)! This is not for any points, but your feedback is invaluable to us, and we would love to hear it so that we can continue to improve!


2. recursive powerSum(n, k) [10 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 0, return 0. If n is negative, return 0. Similarly, if k is negative, return 0.


3. recursive powersOf3ToN(n) [25 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. Asteroid Class and Subclasses [60 pts] [autograded]
   Write the Asteroid, ShrinkingAsteroid, and SplittingAsteroid classes so that they pass testAsteroidClasses, and uses the OOP constructs we learned as appropriate.
   On hw4-2, you will use these classes in your animation!
   def getLocalMethods(clss): import types # This is a helper function for the test function below. # It returns a sorted list of the names of the methods # defined in a class. It's okay if you don't fully understand it! result = [ ] for var in clss.__dict__: val = clss.__dict__[var] if (isinstance(val, types.FunctionType)): result.append(var) return sorted(result) def testAsteroidClasses(): print("Testing Asteroids classes...", end="") # A basic Asteroid takes in cx, cy, radius, speed, and optional direction. # It's default direction (dx, dy) is (0, 1), or moving down asteroid1 = Asteroid(25, 50, 20, 5) assert(type(asteroid1) == Asteroid) assert(isinstance(asteroid1, Asteroid)) asteroid1.setDirection((-1, 0)) assert(asteroid1.getDirection() == (-1,0)) assert(str(asteroid1) == "Asteroid at (25, 50) with radius=20 and direction (-1, 0)") assert(str([asteroid1]) == "[Asteroid at (25, 50) with radius=20 and direction (-1, 0)]") # isCollisionWithWall takes in the canvasWidth and canvasHeight # Asteroids collide with walls if any part of them is touching any side # of the canvas assert(asteroid1.isCollisionWithWall(400, 400) == False) asteroid1.moveAsteroid() assert(str(asteroid1) == "Asteroid at (20, 50) with radius=20 and direction (-1, 0)") assert(asteroid1.getPositionAndRadius() == (20, 50, 20)) assert(asteroid1.isCollisionWithWall(400, 400) == True) # A normal asteroid is stunned when it is hit by a bullet, and it freezes asteroid1.reactToBulletHit() assert(asteroid1.getDirection() == (0, 0)) localMethods = ['__init__', '__repr__', 'getDirection', 'getPositionAndRadius', 'isCollisionWithWall', 'moveAsteroid', 'reactToBulletHit', 'setDirection'] methodsFound = getLocalMethods(Asteroid) for method in localMethods: assert(method in methodsFound) # A Shrinking Asteroid takes in cx, cy, radius, speed, # an optional direction (that is (0, 1) by default), # and an optional shrinkAmount set to 5 pixels by default. # ShrinkAmount is how much the radius of the asteroid decreases when it is # hit by a bullet. A Shrinking Asteroid can also bounce off the walls. asteroid2 = ShrinkingAsteroid(200, 200, 50, 20) assert(type(asteroid2) == ShrinkingAsteroid) assert(isinstance(asteroid2, ShrinkingAsteroid)) assert(isinstance(asteroid2, Asteroid)) asteroid2.reactToBulletHit() assert(asteroid2.getPositionAndRadius() == (200, 200, 45)) assert(str(asteroid2) == "ShrinkingAsteroid at (200, 200) with radius=45 and direction (0, 1)") asteroid2.setDirection((1, -1)) asteroid2.bounce() assert(asteroid2.getDirection() == (-1, 1)) asteroid3 = ShrinkingAsteroid(100, 100, 40, 10, direction=(0, -1), shrinkAmount=20) # The asteroid's radius will decrease by the shrinkAmount asteroid3.reactToBulletHit() assert(asteroid3.getPositionAndRadius() == (100, 100, 20)) assert(getLocalMethods(ShrinkingAsteroid) == ['__init__','bounce', 'reactToBulletHit']) # A Splitting Asteroid takes in cx, cy, radius, speed, and an optional # direction (set to (0, 1) by default). It splits into two smaller # Splitting Asteroids when hit by a bullet. # The each smaller Splitting Asteroid has radius that is half of # the original Splitting Asteroid's and has the original speed and direction asteroid4 = SplittingAsteroid(300, 300, 20, 15) assert(type(asteroid4) == SplittingAsteroid) assert(isinstance(asteroid4, SplittingAsteroid)) assert(isinstance(asteroid4, Asteroid)) assert(not isinstance(asteroid4, ShrinkingAsteroid)) # reactToBulletHit returns 2 new instances of the SplittingAsteroid class asteroid5, asteroid6 = asteroid4.reactToBulletHit() # The new Splitting Asteroid centers are at the top-left and bottom-right # corners of the bounding box surrounding the original asteroid # See the test cases below for an example: assert(asteroid5.getPositionAndRadius() == (280, 280, 10)) assert(asteroid6.getPositionAndRadius() == (320, 320, 10)) assert(str(asteroid6) == "SplittingAsteroid at (320, 320) with radius=10 and direction (0, 1)") assert(getLocalMethods(SplittingAsteroid) == ['__init__', 'reactToBulletHit']) print("Done!")


5. Bonus: recursive evalPrefixNotation(L) [2 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. 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 '*'.
   Hint: this problem becomes drastically easier if you implement it destructively. Our sample solution used L.pop(0) to get the first element, for example. Evaluating the operands then becomes much simpler...