Homework 4: Recursive Data

Due: Thursday 10/08 @ 11:59pm
Points: 1
Download: hw04.zip

To receive credit, you must solve each problem and then complete a short checkoff interview about your solution. You may use Preceptor for the interview or come to office hours to be interviewed by a member of the course staff. Staff will be doing in-person checkoffs for up to 3 business days after the assignment deadline (including any approved extension). If a checkoff happens more than 3 business days after the regular deadline, staff may ask to confirm your extended deadline via Flextensions. You will submit a Provenance bundle that includes a record of how you used VS Code, including interactions with Preceptor. Please do not use AI tools other than Preceptor for this assignment.

Readings: This homework relies on the following readings from Composing Programs:

2.3: Compound Data

Required Questions

Data Classes

Q1: Mobiles

This problem is based on one from Structure and Interpretation of Computer Programs Section 2.2.2.

We are making a planetarium mobile. A mobile is a type of hanging sculpture. A binary mobile consists of two arms. Each arm is a rod of a certain length, from which hangs either a planet or another mobile.

We will represent a binary mobile using the types below.

A Mobile has both a left arm and a right arm.
An Arm has a positive length and must have something hanging at its end, which is a Structure.
A Planet has a positive mass, and nothing hanging from it.
A Structure is either a Mobile or a Planet.

These types have already been defined for you.

type Structure = Mobile | Planet

@dataclass
class Mobile:
    left: Arm
    right: Arm

@dataclass
class Arm:
    length: int
    end: Structure

@dataclass
class Planet:
    mass: int

Total Mass

Implement total_mass, which returns the total mass of a Structure m. The total mass of a Planet is its mass. The total mass of a Mobile is the total mass of everything hanging from its two arms (the rods themselves are weightless). Use isinstance(m, Planet) to check whether m is a Planet. The examples function constructs three Mobile instances that the doctests use.

def examples():
    t = Mobile(Arm(1, Planet(2)),
               Arm(2, Planet(1)))
    u = Mobile(Arm(5, Planet(1)),
               Arm(1, Mobile(Arm(2, Planet(3)),
                             Arm(3, Planet(2)))))
    v = Mobile(Arm(4, t), Arm(2, u))
    return t, u, v

def total_mass(m: Structure) -> int:
    """Return the total mass of m, a Planet or Mobile.

    >>> total_mass(Planet(5))
    5
    >>> t, u, v = examples()
    >>> total_mass(t)
    3
    >>> total_mass(u)
    6
    >>> total_mass(v)
    9
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return 0

python3 -m pytest -k total_mass

Balanced

Implement the balanced function, which returns whether a Structure m is balanced. A Mobile is balanced if both of the following conditions are met:

The torque applied by its left arm is equal to the torque applied by its right arm. The torque of an arm is the length of the rod multiplied by the total mass hanging from that rod. For example, if the left arm has a length of 5, and there is a Mobile hanging at the end of the left arm of total mass 10, the torque on the left side of our Mobile is 50.
Each Structure hanging at the end of its arms is itself balanced.

A Planet is always balanced, as there is nothing hanging from it.

Reminder: You may use the total_mass function above.

def balanced(m: Structure) -> bool:
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = Mobile(Arm(3, t), Arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(Mobile(Arm(1, v), Arm(1, p)))
    False
    >>> balanced(Mobile(Arm(1, p), Arm(1, v)))
    False
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return False

python3 -m pytest -k balanced

Linked Lists

Q2: Interleave

Write interleave(s, t), which takes two linked lists and returns a linked list with elements of s and t interleaved. In other words, the resulting list should have the first element of s, then the first element of t, then the second element of s, then the second element of t, and so on.

If the two lists are not the same length, then the leftover elements of the longer list should appear at the end of the returned list.

Do not use mutation, e.g. s.rest = ....

def interleave[T](s: LinkedList[T], t: LinkedList[T]) -> LinkedList[T]:
    """Interleave linked lists s and t to produce a new linked list.

    >>> evens = Link(2, Link(4, Link(6, Link(8))))
    >>> odds = Link(1, Link(3))
    >>> print(interleave(odds, evens))
    (1 2 3 4 6 8)
    >>> print(interleave(evens, odds))
    (2 1 4 3 6 8)
    >>> print(interleave(odds, odds))
    (1 1 3 3)
    >>> print(interleave((), odds))
    (1 3)
    >>> print(Link(evens, Link(odds)))  # should not change
    ((2 4 6 8) (1 3))
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return ()

python3 -m pytest -k interleave

Q3: Knapsack

You're a thief choosing among treasures of different weights and worths. You have a knapsack that can carry max_weight pounds, and you want to steal the subset of the treasures with the largest total worth.

Each treasure is represented by a Treasure data class with a description, a weight, and a worth. Printing a treasure displays just its description. Here are some treasures and a total_worth function that sums the worth of the treasures in a linked list.

@dataclass
class Treasure:
    description: str
    weight: int
    worth: int

    def __str__(self):
        return self.description

trophy = Treasure('trophy', 2, 5)
gem = Treasure('gem', 4, 7)
ring = Treasure('ring', 1, 3)
crown = Treasure('crown', 6, 12)
vase = Treasure('vase', 3, 4)
orb = Treasure('orb', 5, 9)
gift = Treasure('gift', 1, 1)

def total_worth(s: LinkedList[Treasure]) -> int:
    """Return the total worth of the treasures in linked list s.

    >>> total_worth(Link(trophy, Link(ring)))
    8
    >>> total_worth(())
    0
    """
    total = 0
    while isinstance(s, Link):
        total, s = total + s.first.worth, s.rest
    return total

Implement knapsack, which takes a list of treasures and a max_weight. It returns a linked list of the treasures to steal, in the same order as they appear in treasures. Their total weight may not exceed max_weight, and their total worth should be as large as possible.

Hint: Compare the best linked list that includes the first treasure to the best one that leaves it behind.

def knapsack(treasures: list[Treasure], max_weight: int) -> LinkedList[Treasure]:
    """Return a linked list of treasures with the largest total worth that do not
    exceed max_weight, in the same order as they appear in treasures.

    >>> print(knapsack([trophy, gem, ring], 6))
    (trophy gem)
    >>> print(knapsack([trophy, gem, ring], 7))
    (trophy gem ring)
    >>> print(knapsack([trophy, gem, ring, crown, vase], 8))
    (trophy crown)
    >>> print(knapsack([crown, orb, trophy, vase], 10))
    (orb trophy vase)
    >>> print(knapsack([gem, orb, ring, gift], 6))
    (orb ring)
    >>> knapsack([crown], 3)
    ()
    >>> knapsack([], 3)
    ()
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return ()

python3 -m pytest -k knapsack

Trees

Q4: Finding Berries!

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain berries. Define the function berry_finder, which takes in a tree and returns True if the tree contains a node labeled 'berry' and False otherwise.

Hint: To iterate through each of the branches of a particular tree, you can consider using a for loop to get each branch.

def berry_finder(t: Tree) -> bool:
    """Return True if t contains the label 'berry' and False otherwise.

    >>> scrat = Tree('berry')
    >>> berry_finder(scrat)
    True
    >>> sproul = Tree('roots', [Tree('branch1', [Tree('leaf'), Tree('berry')]), Tree('branch2')])
    >>> berry_finder(sproul)
    True
    >>> numbers = Tree(1, [Tree(2), Tree(3, [Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> berry_finder(numbers)
    False
    >>> t = Tree(1, [Tree('berry', [Tree('not berry')])])
    >>> berry_finder(t)
    True
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return False

python3 -m pytest -k berry_finder

Q5: Maximum Path Sum

Write a function that takes in a tree of numbers and returns the maximum sum of the labels along any path from the root of the tree. A path from the root is a sequence of nodes that starts at the root and moves from each node to one of its branches. The path can end at any node, not just a leaf, and it may include only the root.

def max_path_sum(t: Tree[int]) -> int:
    """Return the maximum sum of labels along any path that starts at the root.

    >>> t = Tree(1, [Tree(5, [Tree(-1), Tree(-3)]), Tree(4)])
    >>> max_path_sum(t) # 1, 5
    6
    >>> u = Tree(5, [Tree(4, [Tree(1), Tree(3)]), Tree(-2, [Tree(10), Tree(-3)])])
    >>> max_path_sum(u) # 5, -2, 10
    13
    >>> v = Tree(-3, [Tree(-1), Tree(-2, [Tree(8)])])
    >>> max_path_sum(v) # -3, -2, 8
    3
    >>> w = Tree(-3, [Tree(-1), Tree(-2)])
    >>> max_path_sum(w) # -3
    -3
    """
    "*** YOUR CODE HERE ***"  # replace the code below
    return 0

python3 -m pytest -k max_path_sum

Submit

Run Provenance: Prepare Submission Bundle from the VS Code command palette to create your submission zip, and upload that zip to Gradescope. For a refresher on how to do this, refer to Lab 00.