CS88 | Lab 8: Inheritance + Linked Lists

Starter Files

Download lab08.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org.

Inheritance

Question 1: Mint

Complete the Mint and Coin classes so that the coins created by a mint have the correct year and worth.

Each Mint instance has a year stamp. The update method sets the year stamp to the current_year class attribute of the Mint class.
The create method takes a subclass of Coin and returns an instance of that class stamped with the mint's year (which may be different from Mint.current_year if it has not been updated.) Hint: Check out the create_animal method in this demo.
A Coin's worth method returns the cents value of the coin plus one extra cent for each year of age beyond 50. A coin's age can be determined by subtracting the coin's year from the current_year class attribute of the Mint class.

class Mint:
    """A mint creates coins by stamping on years.

    The update method sets the mint's stamp to Mint.current_year.

    >>> mint = Mint()
    >>> mint.year
    2020
    >>> dime = mint.create(Dime)
    >>> dime.year
    2020
    >>> Mint.current_year = 2100  # Time passes
    >>> nickel = mint.create(Nickel)
    >>> nickel.year     # The mint has not updated its stamp yet
    2020
    >>> nickel.worth()  # 5 cents + (80 - 50 years)
    35
    >>> mint.update()   # The mint's year is updated to 2100
    >>> Mint.current_year = 2175     # More time passes
    >>> mint.create(Dime).worth()    # 10 cents + (75 - 50 years)
    35
    >>> Mint().create(Dime).worth()  # A new mint has the current year
    10
    >>> dime.worth()     # 10 cents + (155 - 50 years). 155 is because this dime instance has year 2020
    115
    >>> Dime.cents = 20  # Upgrade all dimes!
    >>> dime.worth()     # 20 cents + (155 - 50 years)
    125
    >>> m = Mint()
    >>> n = m.create(Nickel)
    >>> n.worth()
    5
    >>> n.year = 2015
    >>> n.worth() # 5 cents + (160 - 50 years). 160 is from 2175 - 2015
    115
    """
    current_year = 2020

    def __init__(self):
        self.update()

    def create(self, coin):
        "*** YOUR CODE HERE ***"
        return coin(self.year)
    def update(self):
        "*** YOUR CODE HERE ***"
        self.year = Mint.current_year
class Coin:
    cents = 0 # Default value of 0. This value will be overridden in subclasses.

    def __init__(self, year):
        self.year = year

    def worth(self):
        "The worth is a coin's face value + 1 cent for each year over age 50."
        "*** YOUR CODE HERE ***"
        return self.cents + max(0, Mint.current_year - self.year - 50)
class Nickel(Coin):
    cents = 5

class Dime(Coin):
    cents = 10

Use OK to test your code:

python3 ok -q Mint

Linked Lists

A linked list is either an empty linked list (Link.empty) or a first value and the rest of the linked list.

class Link:
    """
    >>> s = Link(1, Link(2, Link(3)))
    >>> s
    Link(1, Link(2, Link(3)))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_str = ', ' + repr(self.rest)
        else:
            rest_str = ''
        return 'Link({0}{1})'.format(repr(self.first), rest_str)

To check if a Link is empty, compare it against the class attribute Link.empty. For example, the below function prints out whether or not the link it is handed is empty:

def test_empty(link):
    if link is Link.empty:
        print('This linked list is empty!')
    else:
        print('This linked list is not empty!')

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (first) and a reference to another linked list (rest) which contains the rest of the values in the list.

Question 2: WWPP: Linked Lists

Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q link -u
If you get stuck, try loading lab08.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

>>> from lab08 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
1
>>> link.rest.first
______
2
>>> link.rest.rest.rest is Link.empty
______
True
>>> link.first = 9001
>>> link.first
______
9001
>>> link.rest = link.rest.rest
>>> link.rest.first
______
3
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______
1
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______
1
>>> link2.rest.first
______
2
>>> print_link(link2) # Look at print_link in lab08.py
______
<1 2 3 4>

Question 3: List to Link

Write a function list_to_link that converts a Python list to a Link.

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> link = list_to_link([1, 2, 3])
    >>> print_link(link)
    <1 2 3>
    >>> print_link(list_to_link([4]))
    <4>
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return Link.empty
    else:
        return Link(lst[0], list_to_link(lst[1:]))

Use OK to test your code:

python3 ok -q list_to_link

Question 4: Reverse

Implement reverse, which takes a linked list link and returns a linked list containing the elements of link in reverse order. The original link should be unchanged.

def reverse(link):
    """Returns a Link that is the reverse of the original.

    >>> print_link(reverse(Link(1)))
    <1>
    >>> link = Link(1, Link(2, Link(3)))
    >>> new = reverse(link)
    >>> print_link(new)
    <3 2 1>
    >>> print_link(link)
    <1 2 3>
    """
    "*** YOUR CODE HERE ***"
    #new = Link(link.first)
    #while link.rest is not Link.empty:
    #    link = link.rest
    #    new = Link(link.first, new)
    #return new

    new = Link.empty
    while link is not Link.empty:
        new = Link(link.first, new)
        link = link.rest
    return new

# Recursive solution
def reverse(link):
    def reverse_to(link, t):
        if link is Link.empty:
            return t
        else:
            return reverse_to(link.rest, Link(link.first, t))
    return reverse_to(link, Link.empty)

Use OK to test your code:

python3 ok -q reverse

Exceptions

Exceptions allow us to try a chunk of code, and then catch any errors that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

try:
    <try suite>
except Exception as e:
    <except suite>
else:
    <else suite>
finally:
    <finally suite>

Notice that we can catch the exception as e. This binds the name e to the exception object. This can be helpful when we want to give extra information on what happened. For example, we can print(e) inside the except clause.

Also, we have an optional else case. The else suite is executed if the try suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

When we write exception statements, we generally don't just use the class Exception as above. Rather, we figure out the specific type of exception that we want to handle, such as TypeError or ZeroDivisionError. To figure out which type of exception you are trying to handle, you can type purposely wrong things into the interpreter (such as 'hi' + 5 or 1 / 0) and see what kind of exception Python spits out.

Question 5: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then Python will raise a KeyError. Write the function avoid_keyerror which returns the value mapped to key in the dictionary. If key does not exist, print 'Avoid Exception' and set key to the string 'no value'.

def avoid_keyerror(dictionary, key):
    """ Returns the value associated with key in dictionary. If key 
    does not exist in the dictionary, print out 'Avoid Exception' and
    map it to the string 'no value'.

    >>> d = {1: 'one', 3: 'three', 5: 'five'}
    >>> avoid_keyerror(d, 3)
    'three'
    >>> avoid_keyerror(d, 4)
    Avoid Exception
    >>> d[4]
    'no value'
    """
    "*** YOUR CODE HERE ***"
    
    try:
        return dictionary[key]
    except KeyError as e:
        print("Avoid Exception")
        dictionary[key] = 'no value'

Use OK to test your code:

python3 ok -q avoid_keyerror

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Optional Questions

Question 6: Quidditch

It's time for the opening quidditch match of the season! We represent the various positions for players with the QuidditchPlayer class and its subclasses. Every player begins with a base_energy level, but every position requires a different proportion of energy. Fill in the energy method for the Beater, Chaser, Seeker, and Keeper classes, according to their docstrings. In addition, fill in the __init__ method for the Chaser class. In the docstrings, time minutes refers to the time variable passed into the method.

class Player:
    def __init__(self, name, base_energy):
        """
        Players have a name, and begin with base_energy.
        """
        self.name = name
        self.base_energy = base_energy

    def energy(self):
        return self.base_energy

class Beater(QuidditchPlayer):
    role = "bludgers"

    def energy(self, time):
        """
        Returns the amount of energy left after playing for time minutes. 
        After playing for time minutes, Beaters lose their base energy level 
        divided by the number of minutes. If time is 0, catch the ZeroDivisionError 
        and print "You can't divide by zero!" instead.
        >>> fred = Beater("Fred Weasley", 640)
        >>> fred.energy(40)
        624.0
        >>> fred.energy(0)
        You can't divide by zero!
        """
        "*** YOUR CODE HERE ***"
        
        try:
            return self.base_energy - (self.base_energy / time)
        except ZeroDivisionError as e:
            print("You can't divide by zero!")

Use OK to test your code:

python3 ok -q Beater.energy

class Chaser(QuidditchPlayer):
    role = "score"
    energy_expended = 20

    def __init__(self, name, base_energy, goals):
        """
        Chasers have a name, score goals, and begin with base_energy.
        """
        "*** YOUR CODE HERE ***"
        
        super().__init__(name, base_energy)
        self.goals = goals
    def energy(self, time):
        """
        Returns the amount of energy left after playing for time minutes. For every goal 
        they score, they use energy_expended units of energy. In addition, they also use 
        10% of energy_expended if the number of minutes they have played is a multiple of 9.
        >>> katie = Chaser("Katie Bell", 230, 2)
        >>> katie.energy(20)
        190
        >>> ginny = Chaser("Ginny Weasley", 400, 3)
        >>> ginny.energy(45)
        338.0
        """
        "*** YOUR CODE HERE ***"
        
        cur_energy = self.base_energy
        cur_energy -= self.energy_expended * self.goals # Note: Chaser.energy_expended works too
        if time % 9 == 0:
            cur_energy -= 0.1 * self.energy_expended 
        return cur_energy

Use OK to test your code:

python3 ok -q Chaser.energy

class Seeker(QuidditchPlayer):
    role = "snitch"
    energy_expended = 5

    def energy(self, time):
        """
        Returns the amount of energy after time minutes. Seekers expend energy_expended 
        units of their energy for every minute they have been playing.
        >>> harry = Seeker("Harry Potter", 700)
        >>> harry.energy(30)
        550
        >>> harry.energy(20)
        600
        """
        "*** YOUR CODE HERE ***"
        
        return self.base_energy - (time * Seeker.energy_expended)

Use OK to test your code:

python3 ok -q Seeker.energy

class Keeper(QuidditchPlayer):
    role = "guard"
    energy_expended = 50

    def energy(self, time):
        """
        Returns the amount of energy after time minutes. If less than 30 minutes have 
        passed, then Keepers do not lose any energy. If 30 minutes or more have passed, 
        then Keepers expend 80% of their energy_expended units for every full 15 
        minutes that pass.
        >>> oliver = Keeper("Oliver Wood", 380)
        >>> oliver.energy(45)
        260.0
        >>> oliver.energy(29)
        380
        """
        "*** YOUR CODE HERE ***"
        
        energy = self.base_energy
        if time < 30:
            return self.base_energy
        else:
            for i in range(time // 15):
                energy = energy - (0.8 * Keeper.energy_expended)
        return energy

Use OK to test your code:

python3 ok -q Keeper.energy

After you finish implementing the QuidditchPlayers, run the following command in your terminal to play the game:

python3 -i quidditch_game.py

Question 7: Shopping Tax

Complete the function tax which takes in a list that represents a shopping cart called shopping_cart and return a new list that also represents the same shopping cart but with a percent tax added to the price of each item.

A shopping cart is represented as a list of 3-element tuples like this:

[(item1, cost1, quantity1), (item2, cost2, quantity2), ..., (itemN, costN, quantityN)]

Then complete the function total_cost which takes in a list that represents a shopping cart called shopping_cart and returns the total cost of all the items in that shopping cart.

def tax(shopping_cart, percent):
    """ Returns a new list where a `percent` tax is added to each item's price in a shopping cart.
    >>> fruit_cart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
    >>> tax(fruit_cart, 10)
    [('apple', 0.55, 3), ('banana', 0.275, 4)]
    >>> cal_cart = [("oski", 1000, 1), ("go", 1.25, 2), ("bears", 3.5, 2)]
    >>> tax(cal_cart, 100)
    [('oski', 2000.0, 1), ('go', 2.5, 2), ('bears', 7.0, 2)]
    """
    "*** YOUR CODE HERE ***"
    
    tax_multiplier= 1 + (percent / 100)
    return [(name, price * tax_multiplier, quantity) for (name, price, quantity) in shopping_cart]

Use OK to test your code:

python3 ok -q tax

Question 8: Shopping Total Cost

def total_cost(shopping_cart):
    """ Returns a float that is the total cost of all items in the shopping cart.
    >>> fruit_cart = [("apple", 0.5, 3), ("banana", 0.25, 4)]
    >>> taxed_fruit = tax(fruit_cart, 10)
    >>> total_cost(taxed_fruit)
    2.75
    >>> cal_cart = [("oski", 1000, 1), ("go", 1.25, 2), ("bears", 3.5, 2)]
    >>> taxed_cart = tax(cal_cart, 100)
    >>> total_cost(taxed_cart)
    2019.0
    """
    "*** YOUR CODE HERE ***"
    
    return sum([price*quantity for (name, price, quantity) in shopping_cart])

Use OK to test your code:

python3 ok -q total_cost

Lab 8: Inheritance + Linked Lists Due at 11:59:59 pm on 4/11/2023.

Starter Files

Submission

Inheritance

Question 1: Mint

Linked Lists

Question 2: WWPP: Linked Lists

Question 3: List to Link

Question 4: Reverse

Exceptions

Question 5: No KeyErrors Allowed

Submit

Optional Questions

Question 6: Quidditch

Question 7: Shopping Tax

Question 8: Shopping Total Cost

Lab 8: Inheritance + Linked Lists
Due at 11:59:59 pm on 4/11/2023.