hw 整理

建议刚开始做的时候看一下文章：CS 61A Summary，熟悉一些知识点。

hw01

这里比较有趣的是a_plus_abs_b，这里使用的是引入函数名作为参数。

from operator import add, sub

def a_plus_abs_b(a, b):
    """Return a+abs(b), but without calling abs.

    >>> a_plus_abs_b(2, 3)
    5
    >>> a_plus_abs_b(2, -3)
    5
    >>> a_plus_abs_b(-1, 4)
    3
    >>> a_plus_abs_b(-1, -4)
    3
    """
    if b < 0:
        f = sub
    else:
        f = add
    return f(a, b)

def a_plus_abs_b_syntax_check():
    """Check that you didn't change the return statement of a_plus_abs_b.

    >>> # You aren't expected to understand the code of this test.
    >>> import inspect, re
    >>> re.findall(r'^\s*(return .*)', inspect.getsource(a_plus_abs_b), re.M)
    ['return f(a, b)']
    """
    # You don't need to edit this function. It's just here to check your work.


def two_of_three(i, j, k):
    """Return m*m + n*n, where m and n are the two smallest members of the
    positive numbers i, j, and k.

    >>> two_of_three(1, 2, 3)
    5
    >>> two_of_three(5, 3, 1)
    10
    >>> two_of_three(10, 2, 8)
    68
    >>> two_of_three(5, 5, 5)
    50
    """
    return i * i + j * j + k * k - max(i, j, k) * max(i, j, k)

def two_of_three_syntax_check():
    """Check that your two_of_three code consists of nothing but a return statement.

    >>> # You aren't expected to understand the code of this test.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(two_of_three)).body[0].body]
    ['Expr', 'Return']
    """
    # You don't need to edit this function. It's just here to check your work.


def largest_factor(n):
    """Return the largest factor of n that is smaller than n.

    >>> largest_factor(15) # factors are 1, 3, 5
    5
    >>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
    40
    >>> largest_factor(13) # factor is 1 since 13 is prime
    1
    """
    factor = n - 1
    while n % factor != 0:
        factor = factor - 1
    return factor


def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    >>> b = hailstone(1)
    1
    >>> b
    1
    """
    cnt = 1
    while n != 1:
        cnt += 1
        print(n)
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    print(1)
    return cnt

hw02

挺有趣的，对高级函数有了更深的理解。

from operator import add, mul

square = lambda x: x * x

identity = lambda x: x

triple = lambda x: 3 * x

increment = lambda x: x + 1


HW_SOURCE_FILE=__file__


def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term:  a function that takes one argument to produce the term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    ans = 1
    for i in range(1, n + 1):
        ans *= term(i)
    return ans



def accumulate(fuse, start, n, term):
    """Return the result of fusing together the first n terms in a sequence
    and start.  The terms to be fused are term(1), term(2), ..., term(n).
    The function fuse is a two-argument commutative & associative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11 (fuse is never used)
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    """
    ans = start
    for i in range(1, n + 1):
        ans = fuse(ans, term(i))
    return ans


def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.

    >>> summation_using_accumulate(5, square) # square(1) + square(2) + ... + square(4) + square(5)
    55
    >>> summation_using_accumulate(5, triple) # triple(1) + triple(2) + ... + triple(4) + triple(5)
    45
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return accumulate(add, 0, n ,term)


def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.

    >>> product_using_accumulate(4, square) # square(1) * square(2) * square(3) * square()
    576
    >>> product_using_accumulate(6, triple) # triple(1) * triple(2) * ... * triple(5) * triple(6)
    524880
    >>> # This test checks that the body of the function is just a return statement.
    >>> import inspect, ast
    >>> [type(x).__name__ for x in ast.parse(inspect.getsource(product_using_accumulate)).body[0].body]
    ['Expr', 'Return']
    """
    return accumulate(mul, 1, n, term)


def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    if n == 0:
        return identity
    else:
        return lambda x: f(make_repeater(f, n-1)(x))

# 另外一种写法：个人感觉更好理解：进行一次函数调用，接下来进行n-1次函数调用
def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    if n == 0:
        return identity
    else:
        return lambda x: make_repeater(f, n-1)(f(x))

总结

这里强调一下最后一道题目：

为什么最后是这样写：简单总结就是先处理n-1次的结果，最后再进行第n次处理。

在这段代码中，lambda x: f(make_repeater(f, n-1)(x)) 是一个匿名函数，用来递归地将函数 f 应用 n 次。

我们逐步解释这个 lambda 表达式和它的作用：

1. 基本概念：

   • lambda x: ... 定义了一个匿名函数，它接受一个参数 x。
   • f 是你传入的函数，n 是要应用 f 的次数。

2. 递归调用：

   • make_repeater(f, n-1) 表示递归调用 make_repeater 函数，生成一个新的函数，这个新的函数会将 f 应用 n-1 次。
   • (x) 则是对这个递归得到的函数进行调用，传入参数 x。

3. 核心逻辑：

   • lambda x: f(make_repeater(f, n-1)(x)) 可以理解为：
     • 先递归调用 make_repeater(f, n-1)，获取一个函数，该函数会将 f 应用 n-1 次。
     • 然后将参数 x 传入这个递归函数，得到 f 应用 n-1 次后的结果。
     • 最后，再把这个结果作为输入传递给 f，从而实现 f 的第 n 次应用。

举个例子：

假设 f = square，n = 3，x = 5：

1. 首次调用 make_repeater(square, 3)：

   • 返回的 lambda 表达式会调用 square(make_repeater(square, 2)(x))。

2. make_repeater(square, 2)：

   • 返回 lambda x: square(make_repeater(square, 1)(x))。

3. make_repeater(square, 1)：

   • 返回 lambda x: square(make_repeater(square, 0)(x))。

4. make_repeater(square, 0)：

   • 直接返回 identity 函数，即返回输入的值。

这样，最终调用 lambda x: square(square(square(5)))，即计算 square(square(square(5)))，最终结果为 390625。

总结一下，这个 lambda 表达式通过递归的方式，逐步将函数 f 应用多次，直到 n 次为止。

hw03

开始难起来了，但是收获还是不错的。

HW_SOURCE_FILE = __file__


def num_eights(n):
    """Returns the number of times 8 appears as a digit of n.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> num_eights(8782089)
    3
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(HW_SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
    True
    """
    def is_eight(x):
        if x == 8:
            return 1
        else:
            return 0
    if n == 0:
        return 0
    return is_eight(n % 10) + num_eights(n // 10)


def digit_distance(n):
    """Determines the digit distance of n.

    >>> digit_distance(3)
    0
    >>> digit_distance(777) # 0 + 0
    0
    >>> digit_distance(314) # 2 + 3
    5
    >>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
    32
    >>> digit_distance(3464660003)  # 1 + 2 + 2 + 2 + ... + 3
    16
    >>> from construct_check import check
    >>> # ban all loops
    >>> check(HW_SOURCE_FILE, 'digit_distance',
    ...       ['For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"
    def abs(x):
        if x < 0:
            return -x
        return x
    if n < 10:
        return 0
    return abs(n % 10 - n // 10  % 10) + digit_distance(n // 10)


def interleaved_sum(n, odd_func, even_func):
    """Compute the sum odd_func(1) + even_func(2) + odd_func(3) + ..., up
    to n.

    >>> identity = lambda x: x
    >>> square = lambda x: x * x
    >>> triple = lambda x: x * 3
    >>> interleaved_sum(5, identity, square) # 1   + 2*2 + 3   + 4*4 + 5
    29
    >>> interleaved_sum(5, square, identity) # 1*1 + 2   + 3*3 + 4   + 5*5
    41
    >>> interleaved_sum(4, triple, square)   # 1*3 + 2*2 + 3*3 + 4*4
    32
    >>> interleaved_sum(4, square, triple)   # 1*1 + 2*3 + 3*3 + 4*3
    28
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
    True
    >>> check(HW_SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
    True
    """
    "*** YOUR CODE HERE ***"
    i = 1
    j = 2
    def oddsum(i):
        if i > n:
            return 0
        return odd_func(i) + oddsum(i + 2)

    def evensum(j):
        if j > n:
            return 0
        return even_func(j) + evensum(j + 2)

    return oddsum(1) + evensum(2)

def next_smaller_dollar(bill):
    """Returns the next smaller bill in order."""
    if bill == 100:
        return 50
    if bill == 50:
        return 20
    if bill == 20:
        return 10
    elif bill == 10:
        return 5
    elif bill == 5:
        return 1

def count_dollars(total):
    """Return the number of ways to make change.

    >>> count_dollars(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
    6
    >>> count_dollars(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
    4
    >>> count_dollars(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
    10
    >>> count_dollars(45)  # How many ways to make change for 45 dollars?
    44
    >>> count_dollars(100) # How many ways to make change for 100 dollars?
    344
    >>> count_dollars(200) # How many ways to make change for 200 dollars?
    3274
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_dollars', ['While', 'For'])
    True
    """
    def count_small(total, largest_coins):
        if total == 0:
            return 1
        elif total < 0:
            return 0
        elif largest_coins == None:
            return 0
        without_coins = count_small(total, next_smaller_dollar(largest_coins))
        with_coins = count_small(total - largest_coins, largest_coins)
        return without_coins + with_coins

    return count_small(total, 100)

def next_larger_dollar(bill):
    """Returns the next larger bill in order."""
    if bill == 1:
        return 5
    elif bill == 5:
        return 10
    elif bill == 10:
        return 20
    elif bill == 20:
        return 50
    elif bill == 50:
        return 100

def count_dollars_upward(total):
    """Return the number of ways to make change using bills.

    >>> count_dollars_upward(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
    6
    >>> count_dollars_upward(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
    4
    >>> count_dollars_upward(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
    10
    >>> count_dollars_upward(45)  # How many ways to make change for 45 dollars?
    44
    >>> count_dollars_upward(100) # How many ways to make change for 100 dollars?
    344
    >>> count_dollars_upward(200) # How many ways to make change for 200 dollars?
    3274
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'count_dollars_upward', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

    def count_large(total, smallest_coins):
        if total == 0:
            return 1
        elif total < 0:
            return 0
        elif smallest_coins == None:
            return 0
        without_coins = count_large(total, next_larger_dollar(smallest_coins))
        with_coins = count_large(total - smallest_coins, smallest_coins)
        return without_coins + with_coins

    return count_large(total, 1)

def print_move(origin, destination):
    """Print instructions to move a disk."""
    print("Move the top disk from rod", origin, "to rod", destination)

def move_stack(n, start, end):
    """Print the moves required to move n disks on the start pole to the end
    pole without violating the rules of Towers of Hanoi.

    n -- number of disks
    start -- a pole position, either 1, 2, or 3
    end -- a pole position, either 1, 2, or 3

    There are exactly three poles, and start and end must be different. Assume
    that the start pole has at least n disks of increasing size, and the end
    pole is either empty or has a top disk larger than the top n start disks.

    >>> move_stack(1, 1, 3)
    Move the top disk from rod 1 to rod 3
    >>> move_stack(2, 1, 3)
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 3
    >>> move_stack(3, 1, 3)
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 1 to rod 2
    Move the top disk from rod 3 to rod 2
    Move the top disk from rod 1 to rod 3
    Move the top disk from rod 2 to rod 1
    Move the top disk from rod 2 to rod 3
    Move the top disk from rod 1 to rod 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
    if n == 1:
        print_move(start, end)
    else:
        other = 6 - start - end # 1 + 2 + 3 = 6 找剩下的那一根柱子
        move_stack(n - 1, start, other)
        print_move(start, end)
        move_stack(n - 1, other, end)



from operator import sub, mul

def make_anonymous_factorial():
    """Return the value of an expression that computes factorial.

    >>> make_anonymous_factorial()(5)
    120
    >>> from construct_check import check
    >>> # ban any assignments or recursion
    >>> check(HW_SOURCE_FILE, 'make_anonymous_factorial',
    ...     ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'FunctionDef', 'Recursion'])
    True
    """
    return (lambda f: f(f))(lambda f: lambda x: 1 if x == 0 else mul(x, f(f)(x - 1)))

总结

• count_dollars和count_dollars_upwards需要参考一下implementation of count_partitions ，分为两种情况讨论：

  1. 可以n减去m，继续拆分。
  2. 不能，则n不变，m减小，尝试继续拆分。
  3. 这里主要考虑的是所给的货币类型，所以需要使用next_smaller_dollar和next_larger_dollar函数。

• 汉诺塔问题分析：

  我们需要的是将上面的盘子移动其他柱子，然后最大盘（相对于位于其上面的盘子来说）移动到理想的柱子，最后再将其他盘移动到最大的柱子上面。

  按照这种思路进行编码即可。

• make_anonymous_factorial：这道是关于lambda表达式和递归函数的使用，建议看看下面的注解：

  这两个 lambda 表达式一起实现了一个匿名递归函数，用于计算阶乘。让我们逐步解析它们。

  完整的代码：

  (lambda f: lambda k: f(f, k)) (lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1))))

  这个表达式实际上有两个主要的 lambda 函数，它们是如何互相配合的呢？

  第一部分：外部 lambda f: lambda k: f(f, k)

  lambda f: lambda k: f(f, k)

  • 这个表达式定义了一个函数，它接收一个参数 f，并返回一个新的函数。
  • 这个新的函数是 lambda k: f(f, k)，它接收一个参数 k，然后调用 f(f, k)。
  • 作用：这个 lambda 表达式实际上是将传入的函数 f 传递给自身，以实现递归调用。它通过 f(f, k) 这种形式，使 f 能够递归调用自身。

  作用机制：

  • 当我们将一个匿名函数（稍后解释）传递给这个 lambda f: ... 时，它会生成一个新的函数，这个新函数接收一个参数 k，并在内部递归调用 f(f, k)。
  • f 是下一层的递归函数，而 f(f, k) 表示调用 f 并传递自身 f，从而实现递归调用。

  第二部分：内部 lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))

  lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))

  • 这是用于计算阶乘的核心递归函数。
  • 它有两个参数：
    • f：用于递归调用的函数（即自身）。
    • k：当前要计算的阶乘数字。

  递归逻辑：

  • k if k == 1 else mul(k, f(f, sub(k, 1))) 是阶乘计算的递归过程：
    • 如果 k == 1，直接返回 k，即递归基线：1! = 1。
    • 否则，调用 mul(k, f(f, sub(k, 1)))，递归计算 k-1 的阶乘：
      • sub(k, 1) 计算 k - 1。
      • f(f, sub(k, 1)) 递归调用自身来计算 k-1 的阶乘。
      • 然后用 mul(k, ...) 乘以当前的 k 值，实现 k * (k-1)!。

  组合效果：

  现在让我们看看这两个 lambda 是如何配合的。

  1. 外层 lambda 接受内部的递归函数，并通过 f(f, k) 方式将自身传递给自己，实现递归调用。
  2. 内层 lambda 执行阶乘的递归逻辑，并通过递归调用 f(f, k) 来计算阶乘。

  整体计算过程：

  假设我们调用 make_anonymous_factorial()(5)，整个过程如下：

  1. 外部 lambda 立即调用，并传递了内部 lambda。

  2. 调用 (lambda f: lambda k: f(f, k))(...)，将内部 lambda 传递进去：

     • 这返回了一个新的函数 lambda k: f(f, k)，这个函数接收 k，并开始计算阶乘。

  3. 当我们调用 make_anonymous_factorial()(5) 时，k = 5，于是递归开始：

     • 首先调用 mul(5, f(f, 4))。
     • 再递归调用 f(f, 4)，进入下一个阶段的计算，依次递归直到 k == 1。

  4. 最终，整个递归结果为 5 * 4 * 3 * 2 * 1 = 120。

  总结：

  • 外层 lambda f: lambda k: f(f, k)：这是一个生成递归函数的机制，通过 f(f, k) 实现递归调用。
  • 内层 lambda f, k: k if k == 1 else mul(k, f(f, sub(k, 1)))：这是阶乘的递归逻辑，用来计算阶乘。

  这个设计通过匿名递归的方式，使用函数自身来执行递归操作，实现了阶乘计算。

hw04

def shuffle(s):
    """Return a shuffled list that interleaves the two halves of s.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    >>> shuffle(letters)
    ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
    >>> shuffle(shuffle(letters))
    ['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
    >>> letters  # Original list should not be modified
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    """
    assert len(s) % 2 == 0, 'len(seq) must be even'
    "*** YOUR CODE HERE ***"
    a, b = [], []
    for i in range(0, len(s) // 2):
        a.append(s[i])
    for i in range(len(s) // 2, len(s)):
        b.append(s[i])
    list = []
    for i in range(len(a)):
        list.append(a[i])
        list.append(b[i])
    return list


def deep_map(f, s):
    """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 ***"
    for i in range(len(s)):
        if type(s[i]) == list:
            deep_map(f, s[i])
        else:
            s[i] = f(s[i])


HW_SOURCE_FILE=__file__


def planet(mass):
    """Construct a planet of some mass."""
    assert mass > 0
    "*** YOUR CODE HERE ***"
    return ['planet', mass]

def mass(p):
    """Select the mass of a planet."""
    assert is_planet(p), 'must call mass on a planet'
    "*** YOUR CODE HERE ***"
    return p[1]

def is_planet(p):
    """Whether p is a planet."""
    return type(p) == list and len(p) == 2 and p[0] == 'planet'

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):
    """Return the total mass of m, a planet or mobile.

    >>> t, u, v = examples()
    >>> total_mass(t)
    3
    >>> total_mass(u)
    6
    >>> total_mass(v)
    9
    """
    if is_planet(m):
        return mass(m)
    else:
        assert is_mobile(m), "must get total mass of a mobile or a planet"
        return total_mass(end(left(m))) + total_mass(end(right(m)))

def balanced(m):
    """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
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'balanced', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"
    if is_planet(m):
        return True
    else:
        left_end, right_end = end(left(m)), end(right(m))
        torque_left = length(left(m)) * total_mass(left_end)
        torque_right = length(right(m)) * total_mass(right_end)
        return torque_left == torque_right and balanced(left_end) and balanced(right_end)


def berry_finder(t):
    """Returns True if t contains a node with the value '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 ***"
    if is_leaf(t):
        return 'berry' in str(label(t))
    else:
        for son in branches(t):
            if berry_finder(son):
                return True
        return False

HW_SOURCE_FILE=__file__


def max_path_sum(t):
    """Return the maximum root-to-leaf path sum of a tree.
    >>> t = tree(1, [tree(5, [tree(1), tree(3)]), tree(10)])
    >>> max_path_sum(t) # 1, 10
    11
    >>> t2 = tree(5, [tree(4, [tree(1), tree(3)]), tree(2, [tree(10), tree(3)])])
    >>> max_path_sum(t2) # 5, 2, 10
    17
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return label(t)
    else:
        max_sum = 0
        for son in branches(t):
            max_sum = max(max_sum, max_path_sum(son))
        max_sum += label(t)
        return max_sum







def mobile(left, right):
    """Construct a mobile from a left arm and a right arm."""
    assert is_arm(left), "left must be an arm"
    assert is_arm(right), "right must be an arm"
    return ['mobile', left, right]

def is_mobile(m):
    """Return whether m is a mobile."""
    return type(m) == list and len(m) == 3 and m[0] == 'mobile'

def left(m):
    """Select the left arm of a mobile."""
    assert is_mobile(m), "must call left on a mobile"
    return m[1]

def right(m):
    """Select the right arm of a mobile."""
    assert is_mobile(m), "must call right on a mobile"
    return m[2]

def arm(length, mobile_or_planet):
    """Construct an arm: a length of rod with a mobile or planet at the end."""
    assert is_mobile(mobile_or_planet) or is_planet(mobile_or_planet)
    return ['arm', length, mobile_or_planet]

def is_arm(s):
    """Return whether s is an arm."""
    return type(s) == list and len(s) == 3 and s[0] == 'arm'

# 描述力臂长度
def length(s):
    """Select the length of an arm."""
    assert is_arm(s), "must call length on an arm"
    return s[1]

# 描述力臂末端物体
def end(s):
    """Select the mobile or planet hanging at the end of an arm."""
    assert is_arm(s), "must call end on an arm"
    return s[2]



# Tree Data Abstraction

def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    """Return the label value of a tree."""
    return tree[0]

def branches(tree):
    """Return the list of branches of the given tree."""
    return tree[1:]

def is_tree(tree):
    """Returns True if the given tree is a tree, and False otherwise."""
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    """Returns True if the given tree's list of branches is empty, and False
    otherwise.
    """
    return not branches(tree)

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

def copy_tree(t):
    """Returns a copy of t. Only for testing purposes.

    >>> t = tree(5)
    >>> copy = copy_tree(t)
    >>> t = tree(6)
    >>> print_tree(copy)
    5
    """
    return tree(label(t), [copy_tree(b) for b in branches(t)])

总结

主要要balanced和max_sum比较困难一些，因为需要看懂一些函数的定义。

• max_sum比较简单，如果接触过树形dp的话不难，我们只需要进行计算子树的最大值即可，再加上根节点的值。

• berry_finder注意一下可能berry不是作为叶子节点，而是其中一部分。这里使用'berry' in str(label(t))，可以将label(t)转化为字符串，然后进行判断是否合法即可。

• 其中一些函数的定义如下：

  主要是定义了移动星系统（mobile）和树结构（tree）的构造与操作，分别处理移动星与树的各种属性和操作。

  移动星系统（Mobile System）

  1. mobile(left, right)：

     • 构造一个由左臂和右臂组成的移动星。左臂和右臂分别通过 arm 构造。
     • 函数会检查左臂和右臂是否为合法的臂结构。

  2. is_mobile(m)：

     • 检查输入的 m 是否为一个移动星，移动星用列表表示，包含 3 个元素，第一个元素是字符串 'mobile'，第二和第三个元素分别是左臂和右臂。

  3. left(m)：

     • 返回移动星 m 的左臂，前提是输入的 m 必须是合法的移动星。

  4. right(m)：

     • 返回移动星 m 的右臂，输入的 m 也必须是合法的移动星。

  5. arm(length, mobile_or_planet)：

     • 构造一个臂（力臂），包含臂的长度和末端的移动星或行星。力臂是一个列表，包含 'arm' 标签、长度和末端物体（行星或移动星）。

  6. is_arm(s)：

     • 检查输入的 s 是否是一个臂结构。臂是一个列表，包含 3 个元素，第一个元素为 'arm'，第二个元素为臂的长度，第三个元素为挂在臂末端的物体。

  7. length(s)：

     • 返回臂 s 的长度，要求输入的 s 是一个合法的臂。

  8. end(s)：

     • 返回臂 s 末端挂着的移动星或行星，要求输入的 s 是一个合法的臂。

  树结构（Tree Data Abstraction）

  1. tree(label, branches=[])：

     • 构造一个树，label 是树的根节点的值，branches 是树的子树。每个子树必须是一个合法的树结构。

  2. label(tree)：

     • 返回树的根节点的标签（值）。

  3. branches(tree)：

     • 返回树的子树列表。

  4. is_tree(tree)：

     • 检查输入是否是一个合法的树结构。树是一个列表，至少有一个元素，且所有的子树都必须是合法的树。

  5. is_leaf(tree)：

     • 判断树是否为叶子节点。叶子节点的特征是没有子树（即 branches(tree) 为空）。

  6. print_tree(t, indent=0)：

     • 打印树的结构，按照树的深度进行缩进，每个节点缩进的空格数量等于该节点的深度乘以 2。

     • 例如：print_tree(tree(1, [tree(2), tree(3, [tree(4), tree(5)])])) 会打印如下结构：

       1
         2
         3
           4
           5

  7. copy_tree(t)：

     • 返回树 t 的一个拷贝。对 t 及其所有子树进行递归拷贝。

• balanced就比较好理解了：

  • 对于一个行星：只需要返回True即可。因为它没有围绕它旋转的星球，没有力臂。
  • 对于一个mobile，我们需要判断它的左右两端和悬挂物是否平衡，所以需要计算力矩。看看两者是否平衡。
  • 此外还需要注意它的左右mobile是否平衡。

hw05

def hailstone(n):
    """
    Yields the elements of the hailstone sequence starting at n.
    At the end of the sequence, yield 1 infinitely.

    >>> hail_gen = hailstone(10)
    >>> [next(hail_gen) for _ in range(10)]
    [10, 5, 16, 8, 4, 2, 1, 1, 1, 1]
    >>> next(hail_gen)
    1
    """
    "*** YOUR CODE HERE ***"
    yield n
    if n == 1:
        yield from hailstone(n)
    elif n % 2 == 0:
        yield from hailstone(n // 2)
    else:
        yield from hailstone(3 * n + 1)


def merge(a, b):
    """
    Return a generator that has all of the elements of generators a and b,
    in increasing order, without duplicates.

    >>> def sequence(start, step):
    ...     while True:
    ...         yield start
    ...         start += step
    >>> a = sequence(2, 3) # 2, 5, 8, 11, 14, ...
    >>> b = sequence(3, 2) # 3, 5, 7, 9, 11, 13, 15, ...
    >>> result = merge(a, b) # 2, 3, 5, 7, 8, 9, 11, 13, 14, 15
    >>> [next(result) for _ in range(10)]
    [2, 3, 5, 7, 8, 9, 11, 13, 14, 15]
    """
    a_val, b_val = next(a), next(b)
    while True:
        if a_val == b_val:
            "*** YOUR CODE HERE ***"
            yield a_val
            a_val = next(a)
            b_val = next(b)
        elif a_val < b_val:
            "*** YOUR CODE HERE ***"
            yield a_val
            a_val = next(a)
        else:
            "*** YOUR CODE HERE ***"
            yield b_val
            b_val = next(b)

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        yield []
    elif n > 0:
        for j in range(1, 3):
            for way in stair_ways(n - j):
                yield [j] + way

def yield_paths(t, value):
    """
    Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:
        yield [value]
    for b in branches(t):
        for k in yield_paths(b, value):
            yield [label(t)] + k



# Tree Data Abstraction

def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    """Return the label value of a tree."""
    return tree[0]

def branches(tree):
    """Return the list of branches of the given tree."""
    return tree[1:]

def is_tree(tree):
    """Returns True if the given tree is a tree, and False otherwise."""
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    """Returns True if the given tree's list of branches is empty, and False
    otherwise.
    """
    return not branches(tree)

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

def copy_tree(t):
    """Returns a copy of t. Only for testing purposes.

    >>> t = tree(5)
    >>> copy = copy_tree(t)
    >>> t = tree(6)
    >>> print_tree(copy)
    5
    """
    return tree(label(t), [copy_tree(b) for b in branches(t)])

总结

得先介绍下yield关键字的用法和yield from的语法：

在 Python 中，yield 是用于生成器函数的关键字。它允许函数在运行时暂停并返回一个值，而保留函数的状态，以便在后续调用时继续执行。这样，yield 可以让函数一次返回一个值，而不是一次性返回所有结果。与返回列表的方式相比，它能够节省内存，因为它只会按需生成值。

yield 用法示例

以下是一个简单的例子：

def count_up_to(n):
    count = 1
    while count <= n:
        yield count
        count += 1

# 使用生成器
for number in count_up_to(5):
    print(number)

在上面的例子中，每次调用 yield 时，count_up_to 会暂停，并返回当前的 count 值。下一次循环时，函数会从暂停的地方继续执行。

yield 的特性

1. 惰性求值：生成器在调用时不会立即计算所有值，而是按需生成值，这有助于节省内存。
2. 保留状态：函数调用暂停时会保存局部变量的状态，下次调用时可以继续计算。
3. 生成无限序列：利用生成器，可以生成无限序列，比如无限斐波那契数列或无穷循环等。

生成器与返回列表的比较

如果需要返回大量数据，可以用 yield 替代列表返回，从而避免内存消耗问题。例如：

def big_range(n):
    for i in range(n):
        yield i

相比于 return [i for i in range(n)]，它不会一次性占用大量内存。

总结

yield 是 Python 中实现生成器的重要工具，能在内存和性能上带来很大的优化。

---

yield from 是 Python 3 中引入的一个语法，主要用于简化生成器的嵌套调用。当一个生成器要调用另一个子生成器并直接生成其值时，可以使用 yield from，这样可以减少代码量并提高可读性。yield from 会将子生成器中的值逐个返回给外部调用方。

示例：对比 yield 和 yield from

假设我们有两个生成器，一个生成数值序列，另一个生成字符序列。我们希望在一个父生成器中使用这两个生成器的值。

使用 yield

def numbers():
    yield 1
    yield 2

def letters():
    yield 'a'
    yield 'b'

def combined():
    for n in numbers():
        yield n
    for l in letters():
        yield l

# 输出: 1 2 a b
for item in combined():
    print(item)

这里，combined 生成器必须使用两个 for 循环来分别遍历 numbers 和 letters 生成的值。

使用 yield from

使用 yield from 可以简化嵌套生成器的代码：

def numbers():
    yield 1
    yield 2

def letters():
    yield 'a'
    yield 'b'

def combined():
    yield from numbers()
    yield from letters()

# 输出: 1 2 a b
for item in combined():
    print(item)

yield from 语句会直接将 numbers 和 letters 中的值生成给调用方，因此 combined 函数的代码更加简洁。

yield from 的其他功能

除了简化生成器嵌套，yield from 还可以：

1. 转发返回值：如果子生成器有返回值（例如在 Python 3.3+ 中，生成器可以使用 return 返回值），yield from 会捕获这个返回值。
2. 异常传播：yield from 可以将生成器的异常传播到子生成器，并在适当的时候捕获异常。
3. 双向通信：yield from 可以支持生成器之间的双向数据传输，使得子生成器可以接收并返回数据。

总结

yield from 是一种将生成器的值和控制权委派给子生成器的简洁方式，能够使嵌套生成器代码更加简明，提高代码可读性。

其实可以简单理解为yield是一种特殊的return，但是有一些区别：

可以把 yield 理解为一种特殊的 return。但它们有几个重要的区别：

1. 暂停与恢复：yield 会暂停函数的执行，将一个值返回给调用者，但保留函数的执行状态（包括局部变量的值和当前执行位置）。下一次调用生成器时，函数会从上次暂停的位置继续执行。而 return 则是直接终止函数的执行，不保留任何状态，下次调用时会从头开始。

2. 生成器特性：使用 yield 的函数是一个生成器函数，而不是普通的函数。生成器函数会返回一个生成器对象，生成器对象可以被迭代多次（每次获取一个值），直到生成器终止。而普通函数只会返回一个单一的值。

3. 多次返回：yield 可以在函数中使用多次，每次产生一个值，生成器函数可以在整个生命周期中不断地生成新值。return 只能返回一次，返回后函数就彻底结束了。

示例对比

yield 的生成器函数：

def count_up_to(n):
    count = 1
    while count <= n:
        yield count
        count += 1

# 输出: 1, 2, 3
for number in count_up_to(3):
    print(number)

在这个例子中，每次调用 yield 都会暂停函数并返回当前的 count，直到循环结束。

return 的普通函数：

def count_up_to(n):
    count = 1
    while count <= n:
        return count  # 只会返回1，然后函数结束
        count += 1

print(count_up_to(3))  # 输出: 1

这里，return 会立即返回 1 并终止函数，不会有机会返回其他的值。

总结

虽然 yield 类似于 return，都可以将一个值返回给调用方，但 yield 是生成器函数独有的，提供了暂停与恢复的特性，使得生成器能够按需生成多个值。这也是 yield 与 return 的核心区别。

那前两道题就很好理解了，就不解释了，解释后面两题：

• 观察第一个样例可以发现：
  • 如果n==0，那么yield []。
  • 否则对多种情况进行分析：可能是yield 1，也可能是yield 2，并且需要对子情况进行递归处理，注意需要将两者拼接起来。

def stair_ways(n):
    """
    Yield all the ways to climb a set of n stairs taking
    1 or 2 steps at a time.

    >>> list(stair_ways(0))
    [[]]
    >>> s_w = stair_ways(4)
    >>> sorted([next(s_w) for _ in range(5)])
    [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]
    >>> list(s_w) # Ensure you're not yielding extra
    []
    """
    "*** YOUR CODE HERE ***"
    if n == 0:
        yield []
    elif n > 0:
        for j in range(1, 3):
            for way in stair_ways(n - j):
                yield [j] + way

• 这道题需要注意是打印所有的路径：
  • 当遇到目标时，打印目标。
  • 对分支进行递归处理，最后还是留意得将他们拼接起来（注意是列表）。

def yield_paths(t, value):
    """
    Yields all possible paths from the root of t to a node with the label
    value as a list.

    >>> t1 = tree(1, [tree(2, [tree(3), tree(4, [tree(6)]), tree(5)]), tree(5)])
    >>> print_tree(t1)
    1
      2
        3
        4
          6
        5
      5
    >>> next(yield_paths(t1, 6))
    [1, 2, 4, 6]
    >>> path_to_5 = yield_paths(t1, 5)
    >>> sorted(list(path_to_5))
    [[1, 2, 5], [1, 5]]

    >>> t2 = tree(0, [tree(2, [t1])])
    >>> print_tree(t2)
    0
      2
        1
          2
            3
            4
              6
            5
          5
    >>> path_to_2 = yield_paths(t2, 2)
    >>> sorted(list(path_to_2))
    [[0, 2], [0, 2, 1, 2]]
    """
    if label(t) == value:
        yield [value]
    for b in branches(t):
        for k in yield_paths(b, value):
            yield [label(t)] + k

hw06

passphrase = 'REPLACE_THIS_WITH_PASSPHRASE'

def midsem_survey(p):
    """
    You do not need to understand this code.
    >>> midsem_survey(passphrase)
    '2bf925d47c03503d3ebe5a6fc12d479b8d12f14c0494b43deba963a0'
    """
    import hashlib
    return hashlib.sha224(p.encode('utf-8')).hexdigest()


class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Nothing left to vend. Please restock.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'Please add $10 more funds.'
    >>> v.add_funds(7)
    'Current balance: $7'
    >>> v.vend()
    'Please add $3 more funds.'
    >>> v.add_funds(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.add_funds(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'

    >>> w = VendingMachine('soda', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.add_funds(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    """
    def __init__(self, product, price):
        """Set the product and its price, as well as other instance attributes."""
        "*** YOUR CODE HERE ***"
        self.product = product
        self.price = price
        self.stock = 0
        self.balance = 0

    def restock(self, n):
        """Add n to the stock and return a message about the updated stock level.

        E.g., Current candy stock: 3
        """
        "*** YOUR CODE HERE ***"
        self.stock += n
        return f'Current {self.product} stock: {self.stock}'

    def add_funds(self, n):
        """If the machine is out of stock, return a message informing the user to restock
        (and return their n dollars).

        E.g., Nothing left to vend. Please restock. Here is your $4.

        Otherwise, add n to the balance and return a message about the updated balance.

        E.g., Current balance: $4
        """
        "*** YOUR CODE HERE ***"
        if self.stock == 0:
            return f'Nothing left to vend. Please restock. Here is your ${n}.'
        self.balance += n
        return f'Current balance: ${self.balance}'


    def vend(self):
        """Dispense the product if there is sufficient stock and funds and
        return a message. Update the stock and balance accordingly.

        E.g., Here is your candy and $2 change.

        If not, return a message suggesting how to correct the problem.

        E.g., Nothing left to vend. Please restock.
              Please add $3 more funds.
        """
        "*** YOUR CODE HERE ***"
        if self.stock == 0:
            return f'Nothing left to vend. Please restock.'
        delta = self.balance - self.price
        if delta < 0:
            return f'Please add ${-delta} more funds.'
        message = f'Here is your {self.product}'
        if delta != 0:
            message += f' and ${delta} change'
        self.balance = 0
        self.stock -= 1
        message += '.'
        return message


def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> store_digits(2450)
    Link(2, Link(4, Link(5, Link(0))))
    >>> store_digits(20105)
    Link(2, Link(0, Link(1, Link(0, Link(5)))))
    >>> # a check for restricted functions
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    """
    "*** YOUR CODE HERE ***"
    result = Link.empty
    while n > 0:
        result = Link(n % 10, result)
        n //= 10
    return result

def deep_map_mut(func, s):
    """Mutates a deep link s by replacing each item found with the
    result of calling func on the item. Does NOT create new Links (so
    no use of Link's constructor).

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> print(link1)
    <3 <4> 5 6>
    >>> # Disallow the use of making new Links before calling deep_map_mut
    >>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
    >>> try:
    ...     deep_map_mut(lambda x: x * x, link1)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    <9 <16> 25 36>
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return
    if isinstance(s.first, Link):
        deep_map_mut(func, s.first)
    else:
        s.first = func(s.first)
    deep_map_mut(func, s.rest)


def two_list(vals, counts):
    """
    Returns a linked list according to the two lists that were passed in. Assume
    vals and counts are the same size. Elements in vals represent the value, and the
    corresponding element in counts represents the number of this value desired in the
    final linked list. Assume all elements in counts are greater than 0. Assume both
    lists have at least one element.
    >>> a = [1, 3]
    >>> b = [1, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(3))
    >>> a = [1, 3, 2]
    >>> b = [2, 2, 1]
    >>> c = two_list(a, b)
    >>> c
    Link(1, Link(1, Link(3, Link(3, Link(2)))))
    """
    "*** YOUR CODE HERE ***"
    result = Link.empty
    index = len(vals) - 1
    while index >= 0:
        count = 0
        while count < counts[index]:
            result = Link(vals[index], result)
            count += 1
        index -= 1
    return result

class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.first = 5
    >>> s.rest.first = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    <5 7 <8 9>>
    """
    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_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) + '>'

总结

• 第一题得补充一下题意。

  首先可以学到的是f-strings，此外需要留意各个属性的作用：

  • product：产品名称
  • stock：数量
  • price：单价
  • balance：余额，可以理解为顾客当前购买中已经投了多少钱（售货机在目前这一次买卖中已经收到了多少钱），每次买卖完后需要清 0。

  理清头绪后，代码实现就很容易了，这里不解释。

In this question you'll create a vending machine that sells a single product and provides change when needed. 在本题中，您将创建一台自动售货机，用于销售单一产品并在需要时提供零钱。

Implement the VendingMachine class, which models a vending machine for one specific product. The methods of a VendingMachine object return strings to describe the machine’s status and operations. Ensure that your output matches exactly with the strings provided in the doctests, including punctuation and spacing. 实现VendingMachine类，该类为一种特定产品建模自动售货机。 VendingMachine对象的方法返回描述机器状态和操作的字符串。确保您的输出与文档测试中提供的字符串完全匹配，包括标点符号和空格。

You may find Python's formatted string literals, or f-strings useful. A quick example: 您可能会发现 Python 的格式化字符串文字或f 字符串很有用。一个简单的例子：

>>> feeling = 'love'
>>> course = '61A!'
>>> combined_string = f'I {feeling} {course}'
>>> combined_string
'I love 61A!'

class VendingMachine:
    """A vending machine that vends some product for some price.

    >>> v = VendingMachine('candy', 10)
    >>> v.vend()
    'Nothing left to vend. Please restock.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'
    >>> v.restock(2)
    'Current candy stock: 2'
    >>> v.vend()
    'Please add $10 more funds.'
    >>> v.add_funds(7)
    'Current balance: $7'
    >>> v.vend()
    'Please add $3 more funds.'
    >>> v.add_funds(5)
    'Current balance: $12'
    >>> v.vend()
    'Here is your candy and $2 change.'
    >>> v.add_funds(10)
    'Current balance: $10'
    >>> v.vend()
    'Here is your candy.'
    >>> v.add_funds(15)
    'Nothing left to vend. Please restock. Here is your $15.'

    >>> w = VendingMachine('soda', 2)
    >>> w.restock(3)
    'Current soda stock: 3'
    >>> w.restock(3)
    'Current soda stock: 6'
    >>> w.add_funds(2)
    'Current balance: $2'
    >>> w.vend()
    'Here is your soda.'
    """
    def __init__(self, product, price):
        """Set the product and its price, as well as other instance attributes."""
        "*** YOUR CODE HERE ***"
        self.product = product
        self.price = price
        self.stock = 0
        self.balance = 0

    def restock(self, n):
        """Add n to the stock and return a message about the updated stock level.

        E.g., Current candy stock: 3
        """
        "*** YOUR CODE HERE ***"
        self.stock += n
        return f'Current {self.product} stock: {self.stock}'

    def add_funds(self, n):
        """If the machine is out of stock, return a message informing the user to restock
        (and return their n dollars).

        E.g., Nothing left to vend. Please restock. Here is your $4.

        Otherwise, add n to the balance and return a message about the updated balance.

        E.g., Current balance: $4
        """
        "*** YOUR CODE HERE ***"
        if self.stock == 0:
            return f'Nothing left to vend. Please restock. Here is your ${n}.'
        self.balance += n
        return f'Current balance: ${self.balance}'


    def vend(self):
        """Dispense the product if there is sufficient stock and funds and
        return a message. Update the stock and balance accordingly.

        E.g., Here is your candy and $2 change.

        If not, return a message suggesting how to correct the problem.

        E.g., Nothing left to vend. Please restock.
              Please add $3 more funds.
        """
        "*** YOUR CODE HERE ***"
        if self.stock == 0:
            return f'Nothing left to vend. Please restock.'
        delta = self.balance - self.price
        if delta < 0:
            return f'Please add ${-delta} more funds.'
        message = f'Here is your {self.product}'
        if delta != 0:
            message += f' and ${delta} change'
        self.balance = 0
        self.stock -= 1
        message += '.'
        return message

• 适合采取头插法，最初为空，不断从右到左计算，插入新值。

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> store_digits(2450)
    Link(2, Link(4, Link(5, Link(0))))
    >>> store_digits(20105)
    Link(2, Link(0, Link(1, Link(0, Link(5)))))
    >>> # a check for restricted functions
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    """
    "*** YOUR CODE HERE ***"
    result = Link.empty
    while n > 0:
        result = Link(n % 10, result)
        n //= 10
    return result

• 需要注意下题目要求：

  Implement deep_map_mut(func, s), which applies the function func to each element in the linked list s. If an element is itself a linked list, recursively apply func to its elements as well. 实现deep_map_mut(func, s) ，它将函数func应用于链表s中的每个元素。如果一个元素本身就是一个链表，则也递归地将func应用于它的元素。

  Your implementation should mutate the original linked list. Do not create any new linked lists. The function returns None. 您的实现应该改变原始链表。不要创建任何新的链接列表。该函数返回None 。

  • 当列表为空时，直接返回。
  • 由于元素可能为链表，所以进行递归处理。
  • 当元素不是链表时，先处理元素，后递归处理后面的链表。

def deep_map_mut(func, s):
    """Mutates a deep link s by replacing each item found with the
    result of calling func on the item. Does NOT create new Links (so
    no use of Link's constructor).

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> print(link1)
    <3 <4> 5 6>
    >>> # Disallow the use of making new Links before calling deep_map_mut
    >>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
    >>> try:
    ...     deep_map_mut(lambda x: x * x, link1)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    <9 <16> 25 36>
    """
    "*** YOUR CODE HERE ***"
    if s is Link.empty:
        return
    if isinstance(s.first, Link):
        deep_map_mut(func, s.first)
    else:
        s.first = func(s.first)
    deep_map_mut(func, s.rest)