Lab 8: Linked Lists, Mutable Trees lab08.zip

Due by 11:59pm on Wednesday, October 19.

Linked Lists

Q1: WWPD: Linked Lists

Read over the Link class in lab08.py. Make sure you understand the doctests.

Use Ok to test your knowledge with the following “What Would Python Display?” questions:
1
python3 ok -q link -u
Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab08.py.

>>> from lab08 import *
>>> link = Link(1000)
>>> link.first
______
>>> link.rest is Link.empty
______
>>> link = Link(1000, 2000)
______
>>> link = Link(1000, Link())
______
>>> from lab08 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______
>>> link.rest.first
______
>>> link.rest.rest.rest is Link.empty
______
>>> link.first = 9001
>>> link.first
______
>>> link.rest = link.rest.rest
>>> link.rest.first
______
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty
______
>>> link.rest.rest.rest.rest.first
______
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______
>>> link2.rest.first
______
>>> from lab08 import *
>>> link = Link(5, Link(6, Link(7)))
>>> link                  # Look at the __repr__ method of Link
______
>>> print(link)          # Look at the __str__ method of Link
______

Q2: Convert Link

Write a function convert_link that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; that is none of the elements is another linked list.

Try to find both an iterative and recursive solution for this problem!

Challenge: You may NOT assume that the input list is shallow. Hint: use the type built-in.

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

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> convert_link(link)
    [1, 2, 3, 4]
    >>> convert_link(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"
    lst = []
    if link == Link.empty:
        return []
    while link != Link.empty:
        lst.append(link.first)
        link = link.rest
    return lst

Q3: Duplicate Link

Write a function duplicate_link that takes in a linked list link and a value. duplicate_link will mutate link such that if there is a linked list node that has a first equal to value, that node will be duplicated. Note that you should be mutating the original link list link; you will need to create new Links, but you should not be returning a new linked list.

Note: in order to insert a link into a linked list, you need to modify the .rest of certain links. We encourage you to draw out a doctest to visualize!

def duplicate_link(link, val):
    """Mutates `link` such that if there is a linked list
    node that has a first equal to value, that node will
    be duplicated. Note that you should be mutating the
    original link list.

    >>> x = Link(5, Link(4, Link(3)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(3))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, (Link(2, Link(3)))))
    >>> duplicate_link(z, 2) #ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    "*** YOUR CODE HERE ***"

Trees

Q4: WWPD: Trees

Read over the Tree class in lab08.py. Make sure you understand the doctests.

Use Ok to test your knowledge with the following “What Would Python Display?” questions:
1
python3 ok -q trees-wwpd -u
Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed. Recall that Tree instances will be displayed the same way they are constructed.

>>> from lab08 import *
>>> t = Tree(1, Tree(2))
______
>>> t = Tree(1, [Tree(2)])
>>> t.label
______
>>> t.branches[0]
______
>>> t.branches[0].label
______
>>> t.label = t.branches[0].label
>>> t
______
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______
>>> t.branches[0]
______
>>> t.branches[1]
______

Q5: Cumulative Mul

Write a function cumulative_mul that mutates the Tree t so that each node’s label becomes the product of its label and all labels in the subtrees rooted at the node.

Hint: Consider carefully when to do the mutation of the tree and whether that mutation should happen before or after processing the subtrees.

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of all labels in
    the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> cumulative_mul(otherTree)
    >>> otherTree
    Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return t.label
    for i in range(len(t.branches)):
        if not t.branches[i].is_leaf():
            cumulative_mul(t.branches[i])
            t.label *= t.branches[i].label
        else:
            t.label *= t.branches[i].label

Optional Questions

Q6: 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.

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)
    """
    "*** YOUR CODE HERE ***"
    t = s
    while t.rest is not Link.empty:
        t.rest = t.rest.rest
        if t.rest is not Link.empty:
            t = t.rest

Q7: Prune Small

Complete the function prune_small that takes in a Tree t and a number n and prunes t mutatively. If t or any of its branches has more than n branches, the n branches with the smallest labels should be kept and any other branches should be pruned, or removed, from the tree.

def prune_small(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest labels.

    >>> t1 = Tree(6)
    >>> prune_small(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune_small(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune_small(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    while len(t.branches)>n:
        largest = max(t.branches, key=lambda x: x.label)
        t.branches.remove(largest)
    for tree in t.branches:
        prune_small(tree, n)