Kurage Notes

Appearance

Q1 ​

python
def filter(condition, lst):
    """Filters lst with condition using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    "*** YOUR CODE HERE ***"
    for x in list(lst):
        if not condition(x):
            lst.remove(x)

Notice that if we mutate lst, the for statement would produce unstable result. In this case, if we iterate over lst, the below situation happens:

  • __iter__ method is called, creating a iterator
  • The pointer of the iterator points to index 0
  • __next__ method is called, 5 is extracted and bound to x in a local frame, pointer points to index 1
  • The first element of lst got removed, and now the iterator's element of index 1 is 2
  • Leading error, etc.

So, we need to create a new temperate list by calling list(lst)

Q2 ​

python
def deep_map_mut(func, lst):
    """Deeply maps a function over a list, replacing each item
    in the original list object.
    Does NOT return the mutated list object.

    >>> l = [1, 2, [3, [4], 5], 6]
    >>> deep_map_mut(lambda x: x * x, l)
    >>> l
    [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_mut(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 x in lst:
        if type(x) == list:
            deep_map_mut(func, x)
            continue
        lst[lst.index(x)] = func(x)

IDK whether there's any other solution not using continue

Q3 ​

Include the Tree ADT

python
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)
    return label(t) + max([max_path_sum(branch) for branch in branches(t)])

Q4 ​

python
def has_path(t, word):
    """Return whether there is a path in a tree where the entries along the path
    spell out a particular word.

    >>> greetings = tree('h', [tree('i'),
    ...                        tree('e', [tree('l', [tree('l', [tree('o')])]),
    ...                                   tree('y')])])
    >>> print_tree(greetings)
    h
      i
      e
        l
          l
            o
        y
    >>> has_path(greetings, 'h')
    True
    >>> has_path(greetings, 'i')
    False
    >>> has_path(greetings, 'hi')
    True
    >>> has_path(greetings, 'hello')
    True
    >>> has_path(greetings, 'hey')
    True
    >>> has_path(greetings, 'bye')
    False
    >>> has_path(greetings, 'hint')
    False
    """
    assert len(word) > 0, 'no path for empty word.'
    "*** YOUR CODE HERE ***"
    if label(t) != word[0]:
        return False
    elif len(word) == 1 and word[0] == label(t):
        return True
    return any([has_path(branch, word[1:]) for branch in branches(t)])