Lab 9: Recursive Objects

Due at 11:59:59 pm on 11/21/2019.

Starter Files

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

  • To receive credit for this lab, you must complete Questions 1, 2, 3, 4, 5, and 6 in lab09.py and submit through OK.
  • Questions 7 and 8 are extra practice. They can be found in the lab09_extra.py file. It is recommended that you complete these problems on your own time for extra practice.

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 1: 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 lab09.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

>>> from lab09 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 lab09.py

______
<1 2 3 4>

Question 2: 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>
    """

    "*** 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 3: Insert

Implement a function insert that takes a Link, a value, and an index, and inserts the value into the Link at the given index. You can assume the linked list already has at least one element. Do not return anything — insert should mutate the linked list.

Note: If the index is out of bounds, you can raise an IndexError with:

raise IndexError
def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> print_link(link)
    <1 2 3>
    >>> insert(link, 9001, 0)
    >>> print_link(link)
    <9001 1 2 3>
    >>> insert(link, 100, 2)
    >>> print_link(link)
    <9001 1 100 2 3>
    >>> insert(link, 4, 5)
    IndexError
    """

    "*** YOUR CODE HERE ***"

    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    elif link.rest is Link.empty:
        raise IndexError
    else:
        insert(link.rest, value, index - 1)

# iterative solution
def insert(link, value, index):
    while index > 0 and link.rest is not Link.empty:
        link = link.rest
        index -= 1
    if index == 0:
        link.rest = Link(link.first, link.rest)
        link.first = value
    else:
        raise IndexError

Use OK to test your code:

python3 ok -q insert

Trees

As we saw in lecture, we can also represent trees as objects.

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def is_leaf(self):
        return not self.branches

Question 4: WWPP: Trees

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q trees -u

Hint: Remember for all WWPP questions, enter Function if you believe the answer is <function ...> and Error if it errors.

>>> from lab09 import *
>>> t = Tree(1, Tree(2))

______
Error

>>> t = Tree(1, [Tree(2)])
>>> t.entry

______
1

>>> t.branches[0]

______
Tree(2)

>>> t.branches[0].entry

______
2

>>> t.entry = t.branches[0].entry
>>> t

______
Tree(2, [Tree(2)])

>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)

______
2

>>> t.branches[0]

______
Tree(2)

>>> t.branches[1]

______
Tree(4, [Tree(8)])

Question 5: Same Shape

Write a function same_shape that returns True if two Trees have the same shape. Two trees have the same shape if they have the same number of children and each of their children have the same shape.

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape if they have the same number of branches and each of their
    children have the same shape.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = Tree(4, [Tree(7)])
    >>> same_shape(t, s)
    False
    """

    "*** YOUR CODE HERE ***"

    return len(t1.branches) == len(t2.branches) and \
        all(same_shape(st1, st2) for st1, st2 in zip(t1.branches, t2.branches))

Use OK to test your code:

python3 ok -q same_shape

Question 6: 23andTree

Write a function computeAncesTree that fills in the ethnic breakdown of everyone in your FamilyTree. FamilyTrees have a name and an ethnicity. An ethnicity is a dictionary mapping ethnicities to their percentages for that person.
A FamilyTree contains a list of parents. Parents are also FamilyTrees. A child's ethnic breakdown should be half of each of the ethnicities in each of their parents. A leaf FamilyTree is a tree with no parents. To begin, you can only assume that the ethnicity of the leafs of your FamilyTree are filled in.

class FamilyTree:
    def __init__(self, name, ethnicity, parents=[]):
        # Leaf FamilyTrees have no parents
        self.name = name
        self.ethnicity = ethnicity
        self.parents = parents
        if not self.is_leaf():
            for p in parents:
                assert isinstance(p, FamilyTree)

    def __repr__(self):
        if self.is_leaf():
            return self.name
        return '{} child of {}'.format(self.name, repr(self.parents))

    def is_leaf(self):
        return len(self.parents) == 0

def computeAncesTree(t):
    """
    Fill in the ethnicities of all parents.
    >>> gma1 = FamilyTree("Farah", {"Moroccan": 100.0})
    >>> gpa1 = FamilyTree("Lorenzo", {"Italian" : 100.0})
    >>> gpa2 = FamilyTree("Hai", {"Chinese":100.0})
    >>> gma2 = FamilyTree("Gazala", {"Indian":100.0})
    >>> papa1 = FamilyTree("Amjad", {}, [gma1, gpa1]) #  Son of Farah and Lorenzo
    >>> papa2 = FamilyTree("Arjun", {}, [gma2, gpa2]) # Son of Hai and Gazala
    >>> mama1 = FamilyTree("Anabella", {}, [gma1, gpa1]) # Daughter of Farah and Lorenzo
    >>> mama2 = FamilyTree("Biyu", {}, [gma2, gpa2]) # Daughter of Hai and Gazala
    >>> c1 = FamilyTree("Dipika", {}, [mama1, papa2]) # Daughter of Arjun and Anabella
    >>> c2 = FamilyTree("Cosimo", {}, [mama1, papa2]) # Son of Arjun and Anabella
    >>> c3 = FamilyTree("Jin", {}, [mama2, papa1]) # Son of Amjad and Biyu
    >>> c4 = FamilyTree("Malika", {}, [mama2, papa1]) # Daughter of Amjad and Biyu
    >>> eth = {a:25.0 for a in ["Moroccan", "Italian", "Chinese", "Indian"]}
    >>> computeAncesTree(c1) == eth
    True
    >>> mama1.ethnicity["Moroccan"] == 50.0 and mama1.ethnicity["Italian"] == 50.0
    True
    >>> papa2.ethnicity["Indian"] == 50.0 and papa2.ethnicity["Chinese"] == 50.0
    True
    >>> mama2.ethnicity == papa1.ethnicity == c2.ethnicity == c3.ethnicity == c4.ethnicity
    True
    >>> computeAncesTree(c2) == computeAncesTree(c3) == computeAncesTree(c4) == eth
    True
    >>> papa1.ethnicity == mama1.ethnicity
    True
    >>> papa2.ethnicity == mama2.ethnicity
    True
    >>> sidepa = FamilyTree("Kahlil Gibran", {"Lebanese":75.0, "Moroccan":25.0})
    >>> secret = FamilyTree("The Prophet", {}, [gma1, sidepa])
    >>> eth2 = {"Lebanese":37.5, "Moroccan":62.5}
    >>> computeAncesTree(secret) == eth2
    True
    """

    "*** YOUR CODE HERE ***"

    if t.is_leaf():
        return t.ethnicity
    else:
        parents_ethnicities = [computeAncesTree(p) for p in t.parents]
        new_ethnicity = {}
        for ethnicity in parents_ethnicities:
            for eth, val in ethnicity.items():
                if eth in new_ethnicity:
                    new_ethnicity[eth] += val / 2
                else:
                    new_ethnicity[eth] = val / 2
        t.ethnicity = new_ethnicity
        return t.ethnicity

Use OK to test your code:

python3 ok -q computeAncesTree

Extra Questions

The following questions are for extra practice — they can be found in the the lab09_extra.py file. It is recommended that you complete these problems on your own time.

Question 7: Link to List

Write a function link_to_list that converts a given Link to a Python list.

def link_to_list(link):
    """Takes a Link and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """

    "*** YOUR CODE HERE ***"

    # Recursive solution
    if link is Link.empty:
        return []
    return [link.first] + link_to_list(link.rest)

# Iterative solution
def link_to_list(link):
    result = []
    while link is not Link.empty:
        result.append(link.first)
        link = link.rest
    return result

Use OK to test your code:

python3 ok -q link_to_list

Question 8: Cycles

The Link class can represent lists with cycles. That is, a list may contain itself as a sublist.

>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3

Implement has_cycle that returns whether its argument, a Link instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which Link objects you've already seen.

def has_cycle(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    >>> u = Link(2, Link(2, Link(2)))
    >>> has_cycle(u)
    False
    """

    "*** YOUR CODE HERE ***"

    lists = set()
    while link is not Link.empty:
        if link in lists:
            return True
        lists.add(link)
        link = link.rest
    return False

Use OK to test your code:

python3 ok -q has_cycle

Extra for experts: Implement has_cycle with only constant space. (If you followed the hint above, you will use linear space.) The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

def has_cycle_constant(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """

    "*** YOUR CODE HERE ***"

    if link is Link.empty:
        return False
    slow, fast = link, link.rest
    while fast is not Link.empty:
        if fast.rest == Link.empty:
            return False
        elif fast == slow or fast.rest == slow:
            return True
        else:
            slow, fast = slow.rest, fast.rest.rest
    return False

Use OK to test your code:

python3 ok -q has_cycle_constant

Motivation

Since you are already familiar with Python's built-in lists, you might be wondering why we are teaching you another list representation. There are historical reasons, along with practical reasons. Later in the term, you'll be programming in Scheme, which is a programming language that uses linked lists for almost everything. But let's not worry about that for now. The real reason, is that certain operations are faster with linked lists.

Python's built-in list is like a sequence of containers with indices on them:

arraylist

Linked lists are a list of items pointing to their neighbors. Notice that there's no explicit index for each item.

linkedlist

Suppose we want to add an item at the head of the list.

  • With Python's built-in list, if you want to put an item into the container labeled with index 0, you must move all the items in the list into its neighbor containers to make room for the first item;

arraylist

  • With a linked list, you tell Python that the neighbor of the new item is the old beginning of the list.

arraylist

To test this, in your terminal, enter the following command: python3 timing.py insert 100000, which inserts 100,000 items into the beginning of both a linked list and a Python built-in list to compare the speed.

Now, say we want the item at index 3.

  • In the built-in list, you can simply grab the item from the container with 3 labeled on it;
  • In the linked list, you need to start at the first item, and go to its neighbor's neighbor's neighbor to finally reach the item at index 3.

To test this, enter the following command in your terminal: python3 timing.py index 10000. This program compares the speed of randomly accessing 10,000 items from both a linked list and a built-in Python list (each with length 10,000).

You'll learn more about orders of growth this week, which will provide mathematical rigor when comparing the runtime of the same operations with different data structures.