Lab 8 Solutions

Inheritance

Question 1: 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 = False

Use OK to test your code:

python3 ok -q CheckingAccount

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

Question 5: Slice

Implement a function slice_link that slices a given link. slice_link should slice the link starting at start and ending one element before end, as with slicing a normal Python list.

def slice_link(link, start, end):
    """Slices a Link from start to end (as with a normal Python list).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> new
    Link(1, Link(4, Link(1)))
    >>> link2 = slice_link(Link(1), 0, 1)
    >>> link2
    Link(1)
    >>> link3 = slice_link(Link.empty, 0, 0)
    >>> link3
    ()
    """
    "*** YOUR CODE HERE ***"
    if end == 0:
        return Link.empty
    elif start == 0:
        return Link(link.first, slice_link(link.rest, 0, end-1))
    else:
        return slice_link(link.rest, start-1, end-1)

Use OK to test your code:

python3 ok -q slice_link