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.
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, andNothing
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>
Q5: Duplicate Link
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 theLink
instances that haveval
as theirfirst
. 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.