Homework 5: List Mutation

Due: Thursday 10/15 @ 11:59pm
Points: 1
Download: hw05.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.4: Mutable Data

Getting Started Videos:

If you feel stuck, try watching some walkthrough videos.

Required Questions

Q1: Deep Map

Definition: A nested list of numbers is a list that contains numbers and lists. It may contain only numbers, only lists, or a mixture of both. The lists must also be nested lists of numbers. For example: [1, [2, [3]], 4], [1, 2, 3], and [[1, 2], [], [3, 4]] are all nested lists of numbers.

Write a function deep_map that takes two arguments: a one-argument function f and a nested list of numbers s. It modifies s in place by replacing each number in s with the result of calling f on that number.

Important: deep_map returns None and should not create any new lists.

Hint: type(a) == list and isinstance(a, list) will evaluate to True if a is a list.

def deep_map(f, s: list) -> None:
    """Replace all non-list elements x with f(x) in the nested list s.

    >>> six = [1, 2, [3, [4], 5], 6]
    >>> deep_map(lambda x: x * x, six)
    >>> six
    [1, 4, [9, [16], 25], 36]
    >>> # Check that you're not making new lists
    >>> s = [3, [1, [4, [1]]]]
    >>> s1 = s[1]
    >>> s2 = s1[1]
    >>> s3 = s2[1]
    >>> deep_map(lambda x: x + 1, s)
    >>> s
    [4, [2, [5, [2]]]]
    >>> s1 is s[1]
    True
    >>> s2 is s1[1]
    True
    >>> s3 is s2[1]
    True
    """
    "*** YOUR CODE HERE ***"

python3 -m pytest -k deep_map

Q2: All Odd Sums

Implement all_odd_sums, which takes a linked list of integers s. It returns a list of all the different odd sums that can be formed by adding together some of the items in s. The returned list should have no repeats and be sorted in ascending order.

The built-in sorted function takes a list and returns a list of the same items sorted in ascending order.

from __future__ import annotations
from lib.link import Link, LinkedList

def all_odd_sums(s: LinkedList[int]) -> list[int]:
    """Return all odd sums of some of the items in s, in ascending order.

    >>> all_odd_sums(Link(1, Link(5, Link(3))))  # sums are 0, 1, 3, 4, 5, 6, 8, 9
    [1, 3, 5, 9]
    >>> all_odd_sums(Link(3, Link(5, Link(4))))  # sums are 0, 3, 4, 5, 7, 8, 9, 12
    [3, 5, 7, 9]
    >>> all_odd_sums(Link(2, Link(1, Link(3))))  # 3 appears only once
    [1, 3, 5]
    >>> all_odd_sums(Link(2, Link(4)))
    []
    """
    sums = []
    def f(s: LinkedList[int], total: int) -> None:
        """Append to sums each unique odd total + (a sum of some items in s)."""
        "*** YOUR CODE HERE ***"
    f(s, 0)
    return sorted(sums)

python3 -m pytest -k all_odd_sums

Q3: Adder

Implement adder, which takes two lists x and y that contain the digits of positive numbers. It mutates x to contain the digits of the sum of the numbers represented by x and y, then returns x. It does not change y.

Hint

First insert 0s at the front of x until it is at least as long as y. Then, add digits from right to left, carrying a 1 as needed.

def adder(x: list[int], y: list[int]) -> list[int]:
    """Add y into x, where x and y are lists of digits representing positive numbers.

    >>> a = [3, 4, 5]
    >>> adder(a, [5, 5])           #  345 +    55 =   400
    [4, 0, 0]
    >>> adder(a, [8, 3, 4])        #  400 +   834 =  1234
    [1, 2, 3, 4]
    >>> adder(a, [3, 3, 3, 3, 3])  # 1234 + 33333 = 34567
    [3, 4, 5, 6, 7]
    >>> a
    [3, 4, 5, 6, 7]
    >>> b = [9, 9, 9, 4, 5]
    >>> adder(b, [5, 5])           # 99945 +    55 = 100000
    [1, 0, 0, 0, 0, 0]
    >>> adder([5, 5], b)           #    55 + 100000 = 100055
    [1, 0, 0, 0, 5, 5]
    >>> b                          # y is not changed
    [1, 0, 0, 0, 0, 0]
    """
    assert max(x + y) <= 9 and min(x + y) >= 0, 'x and y should contain only digits'
    "*** YOUR CODE HERE ***"
    return x

python3 -m pytest -k adder

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.