Lab 7 Solutions

Solution Files

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Midsemester Survey

Q1: Mid-Semester Feedback

As part of this assignment, fill out the Mid-Semester Feedback form.

Confidentiality: Your responses to the survey are confidential, and only the instructors will be able to see this data unanonymized. More specifics on confidentiality can be found on the survey itself.

Once you finish the survey, you will be presented with a passphrase (if you miss it, it should also be at the bottom of the confirmation email you receive). Put this passphrase, as a string, on the line that says passphrase = 'REPLACE_THIS_WITH_PASSPHRASE' in the Python file for this assignment. E.g. if the passphrase is abc, then the line should be passphrase = 'abc'.

Use Ok to test your code:

python3 ok -q midsem_survey

Inheritance

Consult the drop-down if you need a refresher on Inheritance. It's okay to skip directly to the questions and refer back here should you get stuck.

To avoid redefining attributes and methods for similar classes, we can write a single base class from which more specialized classes inherit. For example, we can write a class called Pet and define Dog as a subclass of Pet:

class Pet:

    def __init__(self, name, owner):
        self.is_alive = True    # It's alive!!!
        self.name = name
        self.owner = owner

    def eat(self, thing):
        print(self.name + " ate a " + str(thing) + "!")

    def talk(self):
        print(self.name)

class Dog(Pet):

    def talk(self):
        super().talk()
        print('This Dog says woof!')

Inheritance represents a hierarchical relationship between two or more classes where one class is a more specific version of the other: a dog is a pet (We use is a to describe this sort of relationship in OOP languages, and not to refer to the Python is operator).

Since Dog inherits from Pet, the Dog class will also inherit the Pet class's methods, so we don't have to redefine __init__ or eat. We do want each Dog to talk in a Dog-specific way, so we can override the talk method.

We can use super() to refer to the superclass of self, and access any superclass methods as if we were an instance of the superclass. For example, super().talk() in the Dog class will call the talk method from the Pet class, but passing the Dog instance as the self.

Q2: WWPD: Inheritance ABCs

Important: For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q inheritance-abc -u

>>> class A:
...   x, y = 0, 0
...   def __init__(self):
...         return
>>> class B(A):
...   def __init__(self):
...         return
>>> class C(A):
...   def __init__(self):
...         return
>>> print(A.x, B.x, C.x)

______
______

>>> B.x = 2
>>> print(A.x, B.x, C.x)

______
______

>>> A.x += 1
>>> print(A.x, B.x, C.x)

______
______

>>> obj = C()
>>> obj.y = 1
>>> C.y == obj.y

______
______

>>> A.y = obj.y
>>> print(A.y, B.y, C.y, obj.y)

______
______

Class Practice

Let's say we'd like to model a bank account that can handle interactions such as depositing funds or gaining interest on current funds. In the following questions, we will be building off of the Account class. Here's our current definition of the class:

class Account:
    """An account has a balance and a holder.
    >>> a = Account('John')
    >>> a.deposit(10)
    10
    >>> a.balance
    10
    >>> a.interest
    0.02
    >>> a.time_to_retire(10.25)  # 10 -> 10.2 -> 10.404
    2
    >>> a.balance                # Calling time_to_retire method should not change the balance
    10
    >>> a.time_to_retire(11)     # 10 -> 10.2 -> ... -> 11.040808032
    5
    >>> a.time_to_retire(100)
    117
    """
    max_withdrawal = 10
    interest = 0.02

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount):
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        if amount > self.balance:
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            return "Can't withdraw that amount"
        self.balance = self.balance - amount
        return self.balance

Q3: Retirement

Add a time_to_retire method to the Account class. This method takes in an amount and returns how many years the holder would need to wait in order for the current balance to grow to at least amount, assuming that the bank adds the interest (calculated as the current balance multiplied by the interest rate) to the balance at the end of each year.

Note: Calling the time_to_retire method should not change the account balance.

    def time_to_retire(self, amount):
        """Return the number of years until balance would grow to amount."""
        assert self.balance > 0 and amount > 0 and self.interest > 0

        future = self.balance
        years = 0
        while future < amount:
            future += self.interest * future
            years += 1
        return years

Use Ok to test your code:

python3 ok -q Account

We take of our current balance, and simulate the growth from interest over many years. We stop once we hit the target value.

Note that the problem solving procedure does not differ very much from an non OOP problem. The main difference here is make sure that we do not change the account balance while in the process of calculating the future balance. Therefore, something along these lines is necessary:

future = self.balance

Video walkthrough:

YouTube link

Q4: FreeChecking

Implement the FreeChecking class, which is like the Account class except that it charges a withdraw fee withdraw_fee after withdrawing free_withdrawals number of times. If a withdrawal is unsuccessful, it still counts towards the number of free withdrawals remaining, but no fee for the withdrawal will be charged.

class FreeChecking(Account):
    """A bank account that charges for withdrawals, but the first two are free!
    >>> ch = FreeChecking('Jack')
    >>> ch.balance = 20
    >>> ch.withdraw(100)  # First one's free. Still counts as a free withdrawal even though it was unsuccessful
    'Insufficient funds'
    >>> ch.withdraw(3)    # Second withdrawal is also free
    17
    >>> ch.balance
    17
    >>> ch.withdraw(3)    # Ok, two free withdrawals is enough, as free_withdrawals is only 2
    13
    >>> ch.withdraw(3)
    9
    >>> ch2 = FreeChecking('John')
    >>> ch2.balance = 10
    >>> ch2.withdraw(3) # No fee
    7
    >>> ch.withdraw(3)  # ch still charges a fee
    5
    >>> ch.withdraw(5)  # Not enough to cover fee + withdraw
    'Insufficient funds'
    """
    withdraw_fee = 1
    free_withdrawals = 2


    def __init__(self, account_holder):
        super().__init__(account_holder)
        self.withdrawals = 0

    def withdraw(self, amount):
        self.withdrawals += 1
        fee = 0
        if self.withdrawals > self.free_withdrawals:
            fee = self.withdraw_fee
        return super().withdraw(amount + fee)

    # Alternative solution where you don't need to include init.
    # Check out the video solution for more.
    def withdraw(self, amount):
        self.free_withdrawals -= 1
        if self.free_withdrawals >= 0:
            return super().withdraw(amount)
        return super().withdraw(amount + self.withdraw_fee)

Use Ok to test your code:

python3 ok -q FreeChecking

We can take advantage of inheritance to make sure we add just what we need to withdraw.

  • For starters, a withdrawal with a fee is the same as the original withdraw amount plus the amount from the fee. We can therefore represent a FreeChecking withdraw as a "regular" Account withdraw in this way.
  • On top of the note from before, we need to do a little bit of extra bookkeeping to make sure the first few withdrawals do not add the extra fee. We can either create a new instance attribute or modify an existing one.

Video walkthrough:

YouTube link

Object-Oriented Programming

Here's a refresher on Object-Oriented Programming. It's okay to skip directly to the questions and refer back here if you get stuck.

Object-oriented programming (OOP) uses objects and classes to organize programs. Here's an example of a class:

class Car:
    max_tires = 4

    def __init__(self, color):
        self.tires = Car.max_tires
        self.color = color

    def drive(self):
        if self.tires < Car.max_tires:
            return self.color + ' car cannot drive!'
        return self.color + ' car goes vroom!'

    def pop_tire(self):
        if self.tires > 0:
            self.tires -= 1

Class: The type of an object. The Car class (shown above) describes the characteristics of all Car objects.

Object: A single instance of a class. In Python, a new object is created by calling a class.

>>> ferrari = Car('red')

Here, ferrari is a name bound to a Car object.

Class attribute: A variable that belongs to a class and is accessed via dot notation. The Car class has a max_tires attribute.

>>> Car.max_tires
4

Instance attribute: A variable that belongs to a particular object. Each Car object has a tires attribute and a color attribute. Like class attributes, instance attributes are accessed via dot notation.

>>> ferrari.color
'red'
>>> ferrari.tires
4
>>> ferrari.color = 'green'
>>> ferrari.color
'green'

Method: A function that belongs to an object and is called via dot notation. By convention, the first parameter of a method is self.

When one of an object's methods is called, the object is implicitly provided as the argument for self. For example, the drive method of the ferrari object is called with empty parentheses because self is implicitly bound to the ferrari object.

>>> ferrari = Car('red')
>>> ferrari.drive()
'red car goes vroom!'

We can also call the original Car.drive function. The original function does not belong to any particular Car object, so we must provide an explicit argument for self.

>>> ferrari = Car('red')
>>> Car.drive(ferrari)
'red car goes vroom!'

__init__: A special function that is called automatically when a new instance of a class is created.

Notice how the drive method takes in self as an argument, but it looks like we didn't pass one in! This is because the dot notation implicitly passes in ferrari as self for us. So in this example, self is bound to the object called ferrari in the global frame.

To evaluate the expression Car('red'), Python creates a new Car object. Then, Python calls the __init__ function of the Car class with self bound to the new object and color bound to 'red'.

Q5: Bank Account

Extend the BankAccount class to include a transactions attribute. This attribute should be a list that keeps track of each transaction made on the account. Whenever the deposit or withdraw method is called, a new Transaction instance should be created and added to the list, regardless of whether that action is successful.

The Transaction class should have the following attributes:

  • before: The account balance before the transaction.
  • after: The account balance after the transaction.
  • id: The transaction ID, which is the number of previous transactions (deposits or withdrawals) made on that account. This id should be unique within the scope of each account, but not necessarily unique across all accounts.

In addition, the Transaction class should have the following methods:

  • changed(): Returns True if the balance changed (i.e., before is different from after), otherwise returns False.
  • report(): Returns a string describing the transaction. The string should start with the transaction ID and describe the change in balance. Take a look at the doctests for the expected output.

NOTE. The BankAccount class is the same as the original Account class, meaning that it is exactly like the Account class seen under the Class Practice section excluding the changes made in Question #2 (Retirement) and #3 (FreeChecking). We just had to have a different class name for grading purposes.

class Transaction:
    def __init__(self, id, before, after):
        self.id = id
        self.before = before
        self.after = after

    def changed(self):
        """Return whether the transaction resulted in a changed balance."""

        return self.before != self.after

    def report(self):
        """Return a string describing the transaction.

        >>> Transaction(3, 20, 10).report()
        '3: decreased 20->10'
        >>> Transaction(4, 20, 50).report()
        '4: increased 20->50'
        >>> Transaction(5, 50, 50).report()
        '5: no change'
        """
        msg = 'no change'
        if self.changed():

            if self.after < self.before:
                verb = 'decreased'
            else:
                verb = 'increased'
            msg = verb + ' ' + str(self.before) + '->' + str(self.after)
        return str(self.id) + ': ' + msg

class BankAccount:
    """A bank account that tracks its transaction history.

    >>> a = BankAccount('Eric')
    >>> a.deposit(100)    # Transaction 0 for a
    100
    >>> b = BankAccount('Erica')
    >>> a.withdraw(30)    # Transaction 1 for a
    70
    >>> a.deposit(10)     # Transaction 2 for a
    80
    >>> b.deposit(50)     # Transaction 0 for b
    50
    >>> b.withdraw(10)    # Transaction 1 for b
    40
    >>> a.withdraw(100)   # Transaction 3 for a
    'Insufficient funds'
    >>> len(a.transactions)
    4
    >>> len([t for t in a.transactions if t.changed()])
    3
    >>> for t in a.transactions:
    ...     print(t.report())
    0: increased 0->100
    1: decreased 100->70
    2: increased 70->80
    3: no change
    >>> b.withdraw(100)   # Transaction 2 for b
    'Insufficient funds'
    >>> b.withdraw(30)    # Transaction 3 for b
    10
    >>> for t in b.transactions:
    ...     print(t.report())
    0: increased 0->50
    1: decreased 50->40
    2: no change
    3: decreased 40->10
    """

    # *** YOU NEED TO MAKE CHANGES IN SEVERAL PLACES IN THIS CLASS ***

    def next_id(self):
        # There are many ways to implement this counter, such as using an instance
        # attribute to track the next ID.
        return len(self.transactions)

    def __init__(self, account_holder):
        self.balance = 0
        self.holder = account_holder

        self.transactions = []

    def deposit(self, amount):
        """Increase the account balance by amount, add the deposit
        to the transaction history, and return the new balance.
        """

        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance + amount))
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount):
        """Decrease the account balance by amount, add the withdraw
        to the transaction history, and return the new balance.
        """
        if amount > self.balance:

            self.transactions.append(Transaction(self.next_id(), self.balance, self.balance))
            return 'Insufficient funds'

        self.transactions.append(Transaction(self.next_id(), self.balance, self.balance - amount))
        self.balance = self.balance - amount
        return self.balance

Use Ok to test your code:

python3 ok -q BankAccount

Q6: Email

An email system has three classes: Email, Server, and Client. A Client can compose an email, which it will send to the Server. The Server then delivers it to the inbox of another Client. To achieve this, a Server has a dictionary called clients that maps the name of the Client to the Client instance.

Assume that a client never changes the server that it uses, and it only composes emails using that server.

Fill in the definitions below to finish the implementation! The Email class has been completed for you.

Important: Before you start, make sure you read the entire code snippet to understand the relationships between the classes, and pay attention to the parameter type of the methods. Think about what varible do you have access to in each method and how can you use that to access the other classes and their methods.

Note: The sender parameter from the __init__(self, msg, sender, recipient_name) method in the Email class is a Client instance.

Note: The client parameter from the register_client(self, client) method in the Server class is a Client instance.

Note: The email parameter from the send(self, email) method in the Server class is an Email instance.

class Email:
    """An email has the following instance attributes:

        msg (str): the contents of the message
        sender (Client): the client that sent the email
        recipient_name (str): the name of the recipient (another client)
    """
    def __init__(self, msg, sender, recipient_name):
        self.msg = msg
        self.sender = sender
        self.recipient_name = recipient_name

class Server:
    """Each Server has one instance attribute called clients that is a
    dictionary from client names to client objects.
    """
    def __init__(self):
        self.clients = {}

    def send(self, email):
        """Append the email to the inbox of the client it is addressed to.
            email is an instance of the Email class.
        """

        self.clients[email.recipient_name].inbox.append(email)

    def register_client(self, client):
        """Add a client to the clients mapping (which is a 
        dictionary from client names to client instances).
            client is an instance of the Client class.
        """

        self.clients[client.name] = client

class Client:
    """A client has a server, a name (str), and an inbox (list).

    >>> s = Server()
    >>> a = Client(s, 'Alice')
    >>> b = Client(s, 'Bob')
    >>> a.compose('Hello, World!', 'Bob')
    >>> b.inbox[0].msg
    'Hello, World!'
    >>> a.compose('CS 61A Rocks!', 'Bob')
    >>> len(b.inbox)
    2
    >>> b.inbox[1].msg
    'CS 61A Rocks!'
    >>> b.inbox[1].sender.name
    'Alice'
    """
    def __init__(self, server, name):
        self.inbox = []
        self.server = server
        self.name = name

        server.register_client(self)

    def compose(self, message, recipient_name):
        """Send an email with the given message to the recipient."""

        email = Email(message, self, recipient_name)
        self.server.send(email)

Use Ok to test your code:

python3 ok -q Client

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.

Optional Questions

Q7: Make Change

Implement make_change, which takes a positive integer amount and a dictionary of coins. The coins dictionary keys are positive integer denominations and its values are positive integer coin counts. For example, {1: 4, 5: 2} represents four pennies and two nickels. The make_change function returns a list of coins that sum to amount, where the count of any denomination k in the return value is at most coins[k].

If there are multiple ways to make change for amount, prefer to use as many of the smallest coins available and place the smallest coins first in the returned list.

def make_change(amount, coins):
    """Return a list of coins that sum to amount, preferring the smallest coins
    available and placing the smallest coins first in the returned list.

    The coins argument is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> make_change(2, {2: 1})
    [2]
    >>> make_change(2, {1: 2, 2: 1})
    [1, 1]
    >>> make_change(4, {1: 2, 2: 1})
    [1, 1, 2]
    >>> make_change(4, {2: 1}) == None
    True

    >>> coins = {2: 2, 3: 2, 4: 3, 5: 1}
    >>> make_change(4, coins)
    [2, 2]
    >>> make_change(8, coins)
    [2, 2, 4]
    >>> make_change(25, coins)
    [2, 3, 3, 4, 4, 4, 5]
    >>> coins[8] = 1
    >>> make_change(25, coins)
    [2, 2, 4, 4, 5, 8]
    """
    if not coins:
        return None
    smallest = min(coins)
    rest = remove_one(coins, smallest)
    if amount < smallest:
        return None

    elif amount == smallest:
        return [smallest]
    else:
        result = make_change(amount-smallest, rest)
        if result:
            return [smallest] + result
        else:
            return make_change(amount, rest)

You should use the remove_one function in your implementation:

def remove_one(coins, coin):
    """Remove one coin from a dictionary of coins. Return a new dictionary,
    leaving the original dictionary coins unchanged.

    >>> coins = {2: 5, 3: 2, 6: 1}
    >>> remove_one(coins, 2) == {2: 4, 3: 2, 6: 1}
    True
    >>> remove_one(coins, 6) == {2: 5, 3: 2}
    True
    >>> coins == {2: 5, 3: 2, 6: 1} # Unchanged
    True
    """
    copy = dict(coins)
    count = copy.pop(coin) - 1  # The coin denomination is removed
    if count:
        copy[coin] = count      # The coin denomination is added back
    return copy

Hint: Try using the smallest coin to make change. If it turns out that there is no way to make change using the smallest coin, then try making change without the smallest coin.

Hint: The simplest solution does not involve defining any local functions, but you can define additional functions if you wish.

Definitely try to solve this without reading the walkthrough, but if you're really stuck then read the walkthrough.

The code for make_change(amount, coins) should do the following:
  1. Check if amount == smallest, in which case return a one-element list containing just smallest.
  2. Otherwise, call make_change(amount-smallest, rest), which returns either None or a list of numbers.
  3. If the call in Step 2 returned a list, then return a longer list that includes smallest at the front.
  4. If the call in Step 2 returned None, then there's no way to use the smallest coin, so just make_change(amount, rest)

Use Ok to test your code:

python3 ok -q make_change

Q8: Change Machine

Complete the change method of the ChangeMachine class. A ChangeMachine instance holds some coins, which are initially all pennies. The change method takes a positive integer coin, adds that coin to its coins, and then returns a list that sums to coin. The machine prefers to return as many of the smallest coins available, ordered from smallest to largest. The coins returned by change are removed from the machine's coins.

class ChangeMachine:
    """A change machine holds a certain number of coins, initially all pennies.
    The change method adds a single coin of some denomination X and returns a
    list of coins that sums to X. The machine prefers to return the smallest
    coins available. The total value in the machine never changes, and it can
    always make change for any coin (perhaps by returning the coin passed in).

    The coins attribute is a dictionary with keys that are positive integer
    denominations and values that are positive integer coin counts.

    >>> m = ChangeMachine(2)
    >>> m.coins == {1: 2}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.coins == {2: 1}
    True
    >>> m.change(2)
    [2]
    >>> m.coins == {2: 1}
    True
    >>> m.change(3)
    [3]
    >>> m.coins == {2: 1}
    True

    >>> m = ChangeMachine(10) # 10 pennies
    >>> m.coins == {1: 10}
    True
    >>> m.change(5) # takes a nickel & returns 5 pennies
    [1, 1, 1, 1, 1]
    >>> m.coins == {1: 5, 5: 1} # 5 pennies & a nickel remain
    True
    >>> m.change(3)
    [1, 1, 1]
    >>> m.coins == {1: 2, 3: 1, 5: 1}
    True
    >>> m.change(2)
    [1, 1]
    >>> m.change(2) # not enough 1's remaining; return a 2
    [2]
    >>> m.coins == {2: 1, 3: 1, 5: 1}
    True
    >>> m.change(8) # cannot use the 2 to make 8, so use 3 & 5
    [3, 5]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(1) # return the penny passed in (it's the smallest)
    [1]
    >>> m.change(9) # return the 9 passed in (no change possible)
    [9]
    >>> m.coins == {2: 1, 8: 1}
    True
    >>> m.change(10)
    [2, 8]
    >>> m.coins == {10: 1}
    True

    >>> m = ChangeMachine(9)
    >>> [m.change(k) for k in [2, 2, 3]]
    [[1, 1], [1, 1], [1, 1, 1]]
    >>> m.coins == {1: 2, 2: 2, 3: 1}
    True
    >>> m.change(5) # Prefers [1, 1, 3] to [1, 2, 2] (more pennies)
    [1, 1, 3]
    >>> m.change(7)
    [2, 5]
    >>> m.coins == {2: 1, 7: 1}
    True
    """
    def __init__(self, pennies):
        self.coins = {1: pennies}

    def change(self, coin):
        """Return change for coin, removing the result from self.coins."""

        self.coins[coin] = 1 + self.coins.get(coin, 0)  # Put the coin in the machine
        result = make_change(coin, self.coins)
        for c in result:
            self.coins = remove_one(self.coins, c)
        return result

Hint: Call the make_change function in order to compute the result of change, but update self.coins before returning that result.

Definitely try to solve this without reading the walkthrough, but if you're really stuck then read the walkthrough.

The code for change(self, coin) should do the following:
  1. Add the coin to the machine. This way, you can just make change and you'll always get some result, although it might just be that coin back. The simplest way is to get the count of that coin (defaulting to 0) and add 1 to it: self.coins[coin] = 1 + self.coins.get(coin, 0)
  2. Call make_change(coin, self.coins) and assign the result to a name (such as result). You'll return this at the end.
  3. Before returning, reduce the count of each coin you are returning. One way is to repeatedly call remove_one(self.coins, c) for each coin c in the result of calling make_change in Step 2.
  4. Return the result of calling make_change in Step 2.

Use Ok to test your code:

python3 ok -q ChangeMachine