Discussion 8: Inheritance, Linked Lists

disc08.pdf

Linked Lists

A linked list is a Link object or Link.empty.

You can mutate a Link object s in two ways:

Change the first element with s.first = ...
Change the rest of the elements with s.rest = ...

You can make a new Link object by calling Link:

Link(4) makes a linked list of length 1 containing 4.
Link(4, s) makes a linked list that starts with 4 followed by the elements of linked list s.

class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    <3 4 5>
    """
    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:
            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) + '>'

Q1: Sum Two Ways

Implement both sum_rec and sum_iter. Each one takes a linked list of numbers s and a non-negative integer k and returns the sum of the first k elements of s. If there are fewer than k elements in s, all of them are summed. If k is 0 or s is empty, the sum is 0.

Use recursion to implement sum_rec. Don't use recursion to implement sum_iter; use a while loop instead.

Your Answer

Solution

def sum_rec(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_rec(a, 2)
    7
    >>> sum_rec(a, 5)
    15
    >>> sum_rec(Link.empty, 1)
    0
    """
    # Use a recursive call to sum_rec; don't call sum_iter
    if k == 0 or s is Link.empty:
        return 0
    return s.first + sum_rec(s.rest, k - 1)

def sum_iter(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_iter(a, 2)
    7
    >>> sum_iter(a, 5)
    15
    >>> sum_iter(Link.empty, 1)
    0
    """
    # Don't call sum_rec or sum_iter
    total = 0
    while k > 0 and s is not Link.empty:
        total, s, k = total + s.first, s.rest, k - 1
    return total

Add s.first to the sum of the first k-1 elements in s.rest. Your base case condition should include s is Link.empty so that you're checking whether s is empty before ever evaluating s.first or s.rest.

Introduce a new name, such as total, then repeatedly (in a while loop) add s.first to total, set s = s.rest to advance through the linked list, and reduce k by one.

Discussion time: When adding up numbers, the intermediate sums depend on the order. (1 + 3) + 5 and 1 + (3 + 5) both equal 9, but the first one makes 4 along the way while the second makes 8 along the way. For the same linked list s and length k, will sum_rec and sum_iter both make the same intermediate sums along the way?

Q2: Every Other

Implement every_other, which takes a linked list s. It mutates s such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True

If s contains fewer than two elements, s remains unchanged.

Do not return anything! every_other should mutate the original list.

Your Answer

Solution

def every_other(s):
    """Mutates a linked list so that all the odd-indiced elements are removed
    (using 0-based indexing).

    >>> s = Link(1, Link(2, Link(3, Link(4))))
    >>> every_other(s)
    >>> s
    Link(1, Link(3))
    >>> odd_length = Link(5, Link(3, Link(1)))
    >>> every_other(odd_length)
    >>> odd_length
    Link(5, Link(1))
    >>> singleton = Link(4)
    >>> every_other(singleton)
    >>> singleton
    Link(4)
    """
    if s is Link.empty or s.rest is Link.empty:
        return
    else:
        s.rest = s.rest.rest
        every_other(s.rest)

Inheritance

Q3: Cat

Below is the implementation of a Pet class. Each pet has two instance attributes (name and owner), as well as one instance method (talk).

class Pet:

    def __init__(self, name, owner):
        self.name = name
        self.owner = owner

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

Implement the Cat class, which inherits from the Pet class seen above. To complete the implementation, override or implement the following methods:

___init___

Set the Cat's name and owner attributes, and also add 2 new attributes:

is_hungry - should be set to False
fullness - should be set to whatever the fullness parameter is

Hint: You can call the __init__ method of Pet (the superclass of Cat) to set a cat's name and owner using super().

talk

Print out a cat's greeting, which is "<name of cat> says meow!".

get_hungry

Decrements a cat's fullness level by 1. When fullness reaches zero, is_hungry becomes True. If this is called after fullness has already reached zero, print the message "<name of cat> is hungry."

eat

This method is called when the cat eats some food.

If the cat is hungry, after calling this method both of the following should be true:

The cat's fullness value should be set to whatever Cat.default_fullness is.
The cat's is_hungry value should be False.

Also print out the food the cat ate. For example, if a cat named Thomas ate fish, print out 'Thomas ate a fish!'

Otherwise, if the cat wasn't hungry, print '<name of cat> is not hungry.'

Your Answer

Solution

class Cat(Pet):
    default_fullness = 5

    def __init__(self, name, owner, fullness=default_fullness):
        """
        >>> cat = Cat('Thomas', 'Tammy')
        >>> cat.name
        'Thomas'
        >>> cat.owner
        'Tammy'
        >>> cat.fullness # use default fullness value
        5
        >>> cat.is_hungry
        False
        >>> cat2 = Cat('Meow Meow', 'Yoobin', 3)
        >>> cat2.fullness # use fullness value that was passed in
        3
        """
        super().__init__(name, owner)
        self.fullness = fullness
        self.is_hungry = False

    def talk(self):
        """
        >>> Cat('Thomas', 'Tammy').talk()
        Thomas says meow!
        >>> Cat('Meow Meow', 'ThuyAnh').talk()
        Meow Meow says meow!
        """
        print(self.name + ' says meow!')

    def get_hungry(self):
        """
        >>> cat = Cat('Thomas', 'Tammy', 2)
        >>> cat.is_hungry
        False
        >>> cat.fullness
        2
        >>> cat.get_hungry()
        >>> cat.is_hungry
        False
        >>> cat.fullness
        1
        >>> cat.get_hungry()
        >>> cat.is_hungry
        True
        >>> cat.fullness
        0
        >>> cat.get_hungry()
        Thomas is hungry.
        >>> cat.is_hungry
        True
        >>> cat.fullness
        0
        """
        if self.fullness > 0:
            self.fullness -= 1
            if self.fullness == 0:
                self.is_hungry = True
        else:
            print(f"{self.name} is hungry.")

    def eat(self, food):
        """
        >>> cat = Cat('Crookshanks', 'Hermione', 1)
        >>> cat.eat('tuna')
        Crookshanks is not hungry.
        >>> cat.is_hungry
        False
        >>> cat.fullness
        1
        >>> cat.get_hungry()
        >>> cat.eat('tuna')
        Crookshanks ate a tuna!
        >>> cat.is_hungry
        False
        >>> cat.fullness
        5
        >>> Cat.default_fullness = 3
        >>> for i in range(5):
        ...     cat.get_hungry()
        >>> cat.eat('tuna')
        Crookshanks ate a tuna!
        >>> cat.is_hungry
        False
        >>> cat.fullness
        3
        """
        if self.is_hungry:
            self.fullness = Cat.default_fullness
            self.is_hungry = False
            print(f"{self.name} ate a {food}!")
        else:
            print(f'{self.name} is not hungry.')

Document the Occasion

Please all fill out the attendance form (one submission per person per week).