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.

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.

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:

1. is_hungry - should be set to False
2. 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:

1. The cat's fullness value should be set to whatever Cat.default_fullness is.
2. 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.'

Document the Occasion

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