Lab 8: Inheritance + Linked Lists
Due at 11:59:59 pm on 10/31/2023.
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 Note
The last problem is optional. If you choose not to do this problem, the Gradescope
autograder may complain that you have not submitted the lab08_extra.py file. This
is fine, as our autograder does not grade this question.
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
Mintinstance has ayearstamp. Theupdatemethod sets theyearstamp to thecurrent_yearclass attribute of theMintclass. - The
createmethod takes a subclass ofCoinand returns an instance of that class stamped with themint's year (which may be different fromMint.current_yearif it has not been updated.) Hint: Check out thecreate_animalmethod in this demo. - A
Coin'sworthmethod returns thecentsvalue 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 thecurrent_yearclass attribute of theMintclass.
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 = 10Use OK to test your code:
python3 ok -q MintQuestion 2: Checking account
We'd like to be able to cash checks, so let's add a deposit_check
method to our CheckingAccount class. It will take a Check object
as an argument, and check to see if the payable_to attribute matches
the CheckingAccount's holder. If so, it marks the Check as
deposited, and adds the amount specified to the CheckingAccount's
total.
Write an appropriate Check class, and add the deposit_check method
to the CheckingAccount class. Make sure not to copy and paste code!
Use inheritance whenever possible.
See the doctests for examples of how this code should work.
The Account class has been provided.
class Account(object):
"""A bank account that allows deposits and withdrawals.
>>> eric_account = Account('Eric')
>>> eric_account.deposit(1000000) # depositing my paycheck for the week
1000000
>>> eric_account.transactions
[('deposit', 1000000)]
>>> eric_account.withdraw(100) # buying dinner
999900
>>> eric_account.transactions
[('deposit', 1000000), ('withdraw', 100)]
"""
interest = 0.02
def __init__(self, account_holder):
self.balance = 0
self.holder = account_holder
self.transactions = []
def deposit(self, amount):
"""Increase the account balance by amount and return the
new balance.
"""
self.transactions.append(('deposit', amount))
self.balance = self.balance + amount
return self.balance
def withdraw(self, amount):
"""Decrease the account balance by amount and return the
new balance.
"""
self.transactions.append(('withdraw', amount))
if amount > self.balance:
return 'Insufficient funds'
self.balance = self.balance - amount
return self.balance
class CheckingAccount(Account):
"""A bank account that charges for withdrawals.
>>> check = Check("Steven", 42) # 42 dollars, payable to Steven
>>> steven_account = CheckingAccount("Steven")
>>> eric_account = CheckingAccount("Eric")
>>> eric_account.deposit_check(check) # trying to steal steven's money
The police have been notified.
>>> eric_account.balance
0
>>> check.deposited
False
>>> steven_account.balance
0
>>> steven_account.deposit_check(check)
42
>>> check.deposited
True
>>> steven_account.deposit_check(check) # can't cash check twice
The police have been notified.
"""
withdraw_fee = 1
interest = 0.01
def withdraw(self, amount):
return Account.withdraw(self, amount + self.withdraw_fee)
def deposit_check(self, check):
if check.payable_to != self.holder or check.deposited:
print("The police have been notified.")
else:
self.deposit(check.amount)
check.deposited = True
return self.balance
class Check(object):
"*** YOUR CODE HERE ***"
def __init__(self, payable_to, amount):
self.payable_to = payable_to
self.amount = amount
self.deposited = FalseUse OK to test your code:
python3 ok -q CheckingAccountLinked 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 3: WWPP: Linked Lists
Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q link -uIf 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 4: 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_linkQuestion 5: Add Links
Let's implement a method in order to add together items of link1 and link2
such that the new linked list contains all of the elements of link1, then all
of the elements of link2. Do not assume that the links are the same length.
def add_links(link1, link2):
"""Adds two Links one after another, returning a new Link
>>> l1 = Link(1, Link(2))
>>> l2 = Link(3, Link(4, Link(5)))
>>> new = add_links(l1,l2)
>>> print_link(new)
<1 2 3 4 5>
>>> l3 = Link(10, Link(20))
>>> l4 = Link(30)
>>> added = add_links(l3,l4)
>>> print_link(added)
<10 20 30>
"""
"*** YOUR CODE HERE ***"
if link1 is not Link.empty:
return Link(link1.first, add_links(link1.rest, link2))
elif link2 is not Link.empty:
return Link(link2.first, add_links(link1, link2.rest))
else:
return Link.empty
# Iterative version (using reverse)
def add_links_iter(link1, link2):
result = Link.empty
while link1 is not Link.empty:
result = Link(link1.first, result)
link1 = link1.rest
while link2 is not Link.empty:
result = Link(link2.first, result)
link2 = link2.rest
return reverse(result)Use OK to test your code:
python3 ok -q add_linksOptional Question
Question 6: Rotate
Implement rotate, which takes a linked list link and a number n, and returns a linked list
containing the elements of link shifted to the right n times. Elements at the end are shifted
back to the beginning of the linked list. The value of n may be greater than the length of the
linked list, in which case the values should continue to be rotated.
def rotate(link, n):
"""Rotates the Link so that its elements are shifted to the right n times.
>>> link = Link(1, Link(2, Link(3)))
>>> link = rotate(link, 0)
>>> link
Link(1, Link(2, Link(3)))
>>> link = rotate(link, 1)
>>> link
Link(3, Link(1, Link(2)))
>>> link = rotate(link, 2)
>>> link
Link(1, Link(2, Link(3)))
>>> rotate(link, 5)
Link(2, Link(3, Link(1)))
>>> link = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6))))))
>>> rotate(link, 4)
Link(3, Link(4, Link(5, Link(6, Link(1, Link(2))))))
"""
"*** YOUR CODE HERE ***"
ptr = link
length = 0
while ptr:
ptr = ptr.rest
length += 1
n %= length
head = link
for i in range(length-1):
link = link.rest
link.rest = head
for i in range(length-n-1):
head = head.rest
temp = head.rest
head.rest = Link.empty
return tempUse OK to test your code:
python3 ok -q rotateSubmission
When you are done, submit your file to Gradescope. You only need to upload the following files:
lab08.py