Skip to main content

Lab 7 Solutions | CS 61A Spring 2024

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

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.

Q1: 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

Q2: 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.

```
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](https://youtu.be/fQzeZcI-4a0)

### Q3: FreeChecking

Implement the `FreeChecking` class, which is like the `Account` class from lecture 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](https://youtu.be/flIMJC2lY3M)

## Linked Lists

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

A linked list is a data structure for storing a sequence of values. It is more efficient than a regular built-in list for certain operations, such as inserting a value in the middle of a long list. Linked lists are not built in, and so we define a class called `Link` to represent them. A linked list is either a `Link` instance or `Link.empty` (which represents an empty linked list).

A instance of `Link` has two instance attributes, `first` and `rest`.

class Link: """A linked list.

>>> s = Link(1)
>>> s.first
1
>>> s.rest is Link.empty
True
>>> s = Link(2, Link(3, Link(4)))
>>> s.first = 5
>>> s.rest.first = 6
>>> s.rest.rest = Link.empty
>>> s # Displays the contents of repr(s)
Link(5, Link(6))
>>> s.rest = Link(7, Link(Link(8, Link(9))))
>>> s
Link(5, Link(7, Link(Link(8, Link(9)))))
>>> print(s) # Prints str(s)
<5 7 <8 9>>
"""
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_repr = ', ' + repr(self.rest)
else:
rest_repr = ''
return 'Link(' + repr(self.first) + rest_repr + ')'

def __str__(self):
string = '<'
while self.rest is not Link.empty:
string += str(self.first) + ' '
self = self.rest
return string + str(self.first) + '>'

The `rest` attribute of a `Link` instance should always be a linked list: either another `Link` instance or `Link.empty`. It SHOULD NEVER be `None`.

To check if a linked list is empty, compare it to `Link.empty`. Since there is only ever one empty list, we can use `is` to compare, but `==` would work too.

def is_empty(s): """Return whether linked list s is empty.""" return s is Link.empty:


### Q4: WWPD: Linked Lists

Read over the `Link` class. Make sure you understand the doctests.

> Use Ok to test your knowledge with the following "What Would Python Display?" questions:
>
> ```
> python3 ok -q link -u
> ```
>
> Enter `Function` if you believe the answer is `<function ...>`, `Error` if it errors, and `Nothing` if nothing is displayed.
>
> If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the `Link` class into the interpreter with `python3 -i lab08.py`.

link = Link(1000) link.first __1000 link.rest is Link.empty __True link = Link(1000, 2000) __AssertionError link = Link(1000, Link()) __TypeError


>>> 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 is Link.empty
______False
>>> 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
>>> link = Link(5, Link(6, Link(7)))
>>> link # Look at the __repr__ method of Link
______Link(5, Link(6, Link(7)))
>>> print(link) # Look at the __str__ method of Link
______<5 6 7>

Write a function duplicate_link that takes in a linked list s and a value val. It mutates s so that each element equal to val is followed by an additional val (a duplicate copy). It returns None.

Note: In order to insert a link into a linked list, reassign the rest attribute of the Link instances that have val as their first. Try drawing out a doctest to visualize!

def duplicate_link(s, val):
"""Mutates s so that each element equal to val is followed by another val.

>>> x = Link(5, Link(4, Link(5)))
>>> duplicate_link(x, 5)
>>> x
Link(5, Link(5, Link(4, Link(5, Link(5)))))
>>> y = Link(2, Link(4, Link(6, Link(8))))
>>> duplicate_link(y, 10)
>>> y
Link(2, Link(4, Link(6, Link(8))))
>>> z = Link(1, Link(2, (Link(2, Link(3)))))
>>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
>>> z
Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
"""
if s is Link.empty:
return
elif s.first == val:
remaining = s.rest
s.rest = Link(val, remaining)
duplicate_link(remaining, val)
else:
duplicate_link(s.rest, val)

Use Ok to test your code:

python3 ok -q duplicate_link

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

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 complete this attendance form. Submit this form each week, whether you attend lab or missed it for a good reason. The attendance form is not required for mega section students.