15-112
Fall 18

Home

Syllabus

Schedule

Staff

Gallery

Piazza

Autolab

OH Queue

CMU 15-112 Fall 2018: Fundamentals of Programming and Computer Science
Homework 9 (Due Sunday 28-Oct, at 5pm)

    COLLABORATIVE PROBLEMS
  1. COLLABORATIVE Code-Writing: Vending Machine Class [15pts]
    Write the VendingMachine class so that it passes testVendingMachineClass, and uses the OOP constructs we learned this week as appropriate.

    Hint: Make sure you're representing money properly wherever it might appear in the string representation of a Vending Machine. The test cases shown here don't cover every possible case...

    def testVendingMachineClass(): print("Testing Vending Machine class...", end="") # Vending machines have three main properties: # how many bottles they contain, the price of a bottle, and # how much money has been paid. A new vending machine starts with no # money paid. vm1 = VendingMachine(100, 125) assert(str(vm1) == "Vending Machine:<100 bottles; $1.25 each; $0 paid>") assert(vm1.isEmpty() == False) assert(vm1.getBottleCount() == 100) assert(vm1.stillOwe() == 125) # When the user inserts money, the machine returns a message about their # status and any change they need as a tuple. assert(vm1.insertMoney(20) == ("Still owe $1.05", 0)) assert(str(vm1) == "Vending Machine:<100 bottles; $1.25 each; $0.20 paid>") assert(vm1.stillOwe() == 105) assert(vm1.getBottleCount() == 100) assert(vm1.insertMoney(5) == ("Still owe $1", 0)) # When the user has paid enough money, they get a bottle and # the money owed resets. assert(vm1.insertMoney(100) == ("Got a bottle!", 0)) assert(vm1.getBottleCount() == 99) assert(vm1.stillOwe() == 125) assert(str(vm1) == "Vending Machine:<99 bottles; $1.25 each; $0 paid>") # If the user pays too much money, they get their change back with the # bottle. assert(vm1.insertMoney(500) == ("Got a bottle!", 375)) assert(vm1.getBottleCount() == 98) assert(vm1.stillOwe() == 125) # Machines can become empty vm2 = VendingMachine(1, 120) assert(str(vm2) == "Vending Machine:<1 bottle; $1.20 each; $0 paid>") assert(vm2.isEmpty() == False) assert(vm2.insertMoney(120) == ("Got a bottle!", 0)) assert(vm2.getBottleCount() == 0) assert(vm2.isEmpty() == True) # Once a machine is empty, it should not accept money until it is restocked. assert(str(vm2) == "Vending Machine:<0 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Machine is empty", 25)) assert(vm2.insertMoney(120) == ("Machine is empty", 120)) assert(vm2.stillOwe() == 120) vm2.stockMachine(20) # Does not return anything assert(vm2.getBottleCount() == 20) assert(vm2.isEmpty() == False) assert(str(vm2) == "Vending Machine:<20 bottles; $1.20 each; $0 paid>") assert(vm2.insertMoney(25) == ("Still owe $0.95", 0)) assert(vm2.stillOwe() == 95) vm2.stockMachine(20) assert(vm2.getBottleCount() == 40) # We should be able to test machines for basic functionality vm3 = VendingMachine(50, 100) vm4 = VendingMachine(50, 100) vm5 = VendingMachine(20, 100) vm6 = VendingMachine(50, 200) vm7 = "Vending Machine" assert(vm3 == vm4) assert(vm3 != vm5) assert(vm3 != vm6) assert(vm3 != vm7) # should not crash! s = set() assert(vm3 not in s) s.add(vm4) assert(vm3 in s) s.remove(vm4) assert(vm3 not in s) assert(vm4.insertMoney(50) == ("Still owe $0.50", 0)) assert(vm3 != vm4) print("Done!")

  2. COLLABORATIVE Code Writing: Bird Class and Subclasses [15pts]
    Write the Bird, Penguin, and MessengerBird classes so that they pass testBirdClasses and use the OOP constructs we learned this week as appropriate.

    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 testBirdClasses(): print("Testing Bird classes...", end="") # A basic Bird has a species name, can fly, and can lay eggs bird1 = Bird("Parrot") assert(type(bird1) == Bird) assert(isinstance(bird1, Bird)) assert(bird1.fly() == "I can fly!") assert(bird1.countEggs() == 0) assert(str(bird1) == "Parrot has 0 eggs") bird1.layEgg() assert(bird1.countEggs() == 1) assert(str(bird1) == "Parrot has 1 egg") bird1.layEgg() assert(bird1.countEggs() == 2) assert(str(bird1) == "Parrot has 2 eggs") assert(getLocalMethods(Bird) == ['__init__', '__repr__', 'countEggs', 'fly', 'layEgg']) # A Penguin is a Bird that cannot fly, but can swim bird2 = Penguin("Emperor Penguin") assert(type(bird2) == Penguin) assert(isinstance(bird2, Penguin)) assert(isinstance(bird2, Bird)) assert(bird2.fly() == "No flying for me.") assert(bird2.swim() == "I can swim!") bird2.layEgg() assert(bird2.countEggs() == 1) assert(str(bird2) == "Emperor Penguin has 1 egg") assert(getLocalMethods(Penguin) == ['fly', 'swim']) # A MessengerBird is a Bird that can optionally carry a message bird3 = MessengerBird("War Pigeon", message="Top-Secret Message!") assert(type(bird3) == MessengerBird) assert(isinstance(bird3, MessengerBird)) assert(isinstance(bird3, Bird)) assert(not isinstance(bird3, Penguin)) assert(bird3.deliverMessage() == "Top-Secret Message!") assert(str(bird3) == "War Pigeon has 0 eggs") assert(bird3.fly() == "I can fly!") bird4 = MessengerBird("Homing Pigeon") assert(bird4.deliverMessage() == "") bird4.layEgg() assert(bird4.countEggs() == 1) assert(getLocalMethods(MessengerBird) == ['__init__', 'deliverMessage']) print("Done!")

  3. COLLABORATIVE Code Writing: recursive alternatingSum(lst) [10pts]
    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.

  4. COLLABORATIVE Code Writing: recursive generateCharacterString [15pts]
    Write the function generateCharacterString(s) that takes a two-character string and returns a new string that contains the all of the characters (in ascii order) between the first character and the second character. For example, generateCharacterString("ko") would return "klmno". This should also work backwards, so generateCharacterString("ME") would return "MLKJIHGFE". If the initial provided string is not two characters long, return the empty string; if the provided string contains two identical characters (for example, "22"), return that character ("2").
    5. SOLO PROBLEMS
  5. Short Answer: Design a Sports Class [10pts]
    When programming, you will not always be given the class structure, properties, and methods that you need to implement; sometimes, you need to figure out an appropriate structure yourself. In this task, you will be designing class inheritance structures, methods, and properties for a specific context.

    For the context, you may choose any team sport that is interesting to you. Common examples include soccer, baseball, football, hockey, basketball, rugby, cricket, ultimate, quidditch, and more! Assume you want to define a Player class for that sport. You must describe at least two methods and two properties that would be held by the Player class, two subclasses of Player, and whether these subclasses would need to override or inherit the methods defined for the Player class. All of this should be done in a top-level comment in your submitted file, in the following format:

    """ #5 Sports Class Answer Sport: ___ Player Class properties: ___ Player Class methods: ___ Player Class Subclass one: ___ Methods to override: ___ Methods to inherit: ___ Player Class Subclass two: ___ Methods to override: ___ Methods to inherit: ___ """

    All properties and methods should be clearly named so that someone else would immediately understand their purpose and see its relevance to the class. If needed, feel free to add comments further explaining the purpose of a method or property. Get creative, and have fun!

  6. Code Writing: Equation Classes [20pts]
    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()

  7. Code Writing: recursive powersOf3ToN(n) [15pts]
    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. As an example, powersOf3ToN(10.5) returns [1, 3, 9]. If no such powers of 3 exist, you should return the empty list.

    Hint: in the recursive case, consider using a partial result to construct a full result.