Description: https://inst.eecs.berkeley.edu/~cs61a/fa20/lab/lab05/

Optional Questions

Tree - Q10: Add Trees (不会做，是老师的讲解)

Define the function add_trees, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

Hint: You may want to use the built-in zip function to iterate over multiple sequences at once.

Note: If you feel that this one's a lot harder than the previous tree problems, that's totally fine! This is a pretty difficult problem, but you can do it! Talk about it with other students, and come back to it if you need to.

不会……在Circuit的Q&A里讲了用while的做法（没有用zip），以下是其中一个solution

def add_trees(t1, t2):
    """
    >>> numbers = tree(1,
    ...                [tree(2,
    ...                      [tree(3),
    ...                       tree(4)]),
    ...                 tree(5,
    ...                      [tree(6,
    ...                            [tree(7)]),
    ...                       tree(8)])])
    >>> print_tree(add_trees(numbers, numbers))
    2
      4
        6
        8
      10
        12
          14
        16
    >>> print_tree(add_trees(tree(2), tree(3, [tree(4), tree(5)])))
    5
      4
      5
    >>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
    4
      6
      4
    >>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
    tree(2, [tree(3, [tree(4)]), tree(5)])))
    4
      6
        8
        5
      5
    """
    "*** YOUR CODE HERE ***"
    # they might have branches, but they both must have label
    res_label = label(t1) + label(t2)
    # for each corresponding branch, add them tgt
    res_branch = []
    i = 0  # index to chase which branch I am in
    while i < len(branches(t1)) and i < len(branches(t2)):
        b1, b2 = branches(t1)[i], branches(t2)[i]
        new_branch = add_trees(b1, b2)
        res_branch += [new_branch]  # remember to add []
        i += 1
    # where t1 or t2 is empty: no need to add, just need to include
    res_branch += branches(t1)[i:]
    res_branch += branches(t2)[i:]
    # return the new tree
    return tree(res_label, res_branch)

然后也介绍了用zip的solution：

• zip是程序员很喜欢用的abstraction，但是如果之前没学过，一开始会觉得confusing
• zip只会go through双方都有的branches
• zip完后剩余落单的branches可以用i = len(res_branches)来做同样的slicing

def add_trees(t1, t2):
    """*** YOUR CODE HERE ***"""
    # they might have branches, but they both must have label
    res_label = label(t1) + label(t2)
    # for each corresponding branch, add them tgt
    res_branch = []
    for b1, b2 in zip(branches(t1), branches(t2)):  # go through only the branches appearing in both t1 and t2
        new_branch = add_trees(b1, b2)
        res_branch += [new_branch]  # remember to add []
    # where t1 or t2 is empty: no need to add, just need to include
    i = len(res_branch)  # important to add
    res_branch += branches(t1)[i:]
    res_branch += branches(t2)[i:]
    # return the new tree
    return tree(res_label, res_branch)

化简版本的python：

def add_trees(t1, t2):
    """*** YOUR CODE HERE ***"""
    # get the result label
    res_label = label(t1) + label(t2)
    # get the result branches: part 1
    res_branch = [add_trees(b1, b2) for b1, b2 in zip(branches(t1, t2))]
    # get the result branches: part 2
    i = len(res_branch)
    res_branch += branches(t1)[i:] + branches(t2)[i:]  # only one will be non-empty
    # return the new tree
    return tree(res_label, res_branch)

List Comprehensions - Q9: Riffle Shuffle

The familiar riffle shuffle of a deck of cards (or in our case, of a sequence of things) results in a new configuration of cards in which the top card is followed by the middle card, then by the second card, then the card after the middle, and so forth. Assuming the deck (sequence) contains an even number of cards, write a list comprehension that produces the shuffled sequence.

Hint: To write this as a single comprehension, you may find the expression k%2, which evaluates to 0 on even numbers and 1 on odd numbers, to be useful. Consider how you can use the 0 or 1 returned by k%2 to alternatively access the beginning and the middle of the list.

def riffle(deck):
    """Produces a single, perfect riffle shuffle of DECK, consisting of
    DECK[0], DECK[M], DECK[1], DECK[M+1], ... where M is position of the
    second half of the deck.  Assume that len(DECK) is even.
    >>> riffle([3, 4, 5, 6])
    [3, 5, 4, 6]
    >>> riffle(range(20))
    [0, 10, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19]
    """
    "*** YOUR CODE HERE ***"
    return [deck[(i % 2) * (len(deck) // 2) + i // 2] for i in range(len(deck))]

List Comprehensions - Q8: Coordinates

Implement a function coords that takes a function fn, a sequence seq, and a lower and upper bound on the output of the function. coords then returns a list of coordinate pairs (lists) such that:

• Each (x, y) pair is represented as [x, fn(x)]
• The x-coordinates are elements in the sequence
• The result contains only pairs whose y-coordinate is within the upper and lower bounds (inclusive)

def coords(fn, seq, lower, upper):
    """
    >>> seq = [-4, -2, 0, 1, 3]
    >>> fn = lambda x: x**2
    >>> coords(fn, seq, 1, 9)
    [[-2, 4], [1, 1], [3, 9]]
    """
    "*** YOUR CODE HERE ***"
    return [[i, fn(i)] for i in seq if lower <= fn(i) <= upper]

Required Questions

Trees - Q7: Don't violate the abstraction barrier!

Note: this question has no code-writing component (if you implemented berry_finder and sprout_leaves correctly!)

# Abstraction tests for sprout_leaves and berry_finder
def check_abstraction():
    """
    There's nothing for you to do for this function, it's just here for the extra doctest
    >>> change_abstraction(True)
    >>> 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
    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    >>> change_abstraction(False)
    """

Trees - Q6: Sprout leaves

Define a function sprout_leaves that takes in a tree, t, and a list of leaves, leaves. It produces a new tree that is identical to t, but where each old leaf node has new branches, one for each leaf in leaves.

For example, say we have the tree t = tree(1, [tree(2), tree(3, [tree(4)])]):

  1
 / \
2   3
    |
    4

If we call sprout_leaves(t, [5, 6]), the result is the following tree:

       1
     /   \
    2     3
   / \    |
  5   6   4
         / \
        5   6

思路：

Base Case：如果是叶子，那么就在叶子这里加新的叶子，注意树的抽象定义里面说了，每一片叶子本质上都是一棵新的树

Recursive Case：如果不是叶子是（一个或者多个）树枝，那么就在每一个树枝里去构建sprout_leaves(t, [5, 6])

这里我一开始错误地return了return [sprout_leaves(branch, leaves) for branch in branches(t)]

原因是我并没有理解到，这里我要做的是以当前的root为label去造tree，而不是以以branch为labe去造tree，这样才能保证是同一棵树

所以正确的return应该是return tree(current_root, [ sprout(branch, [new_leaves]) for each branch which is essentially a list/tree]

代码：

def sprout_leaves(t, leaves):
    """Sprout new leaves containing the data in leaves at each leaf in
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):  # add leaves to each leaf
        return tree(label(t), [tree(leaf) for leaf in leaves])
    else:  # find the leaves
        # wrong attempt: return [sprout_leaves(branch, leaves) for branch in branches(t)]
        return tree(label(t), [sprout_leaves(branch, leaves) for branch in branches(t)])

Trees - Q5: 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 with the value 'berry' and False otherwise.

Hint: Considering using a for loop to iterate through each of the branches recursively!

思路：

Base Case：已经是树叶了，下面没有更多branches了，直接看看树叶的label是不是tree就好

Recursive Case：下面还有树枝：那么每一个树枝（用for b in branhces实现）都可以是一棵新的树，分两步走

1. 1. check新的树的root是不是berry
   2. 如果不是，check每一个树枝（用for b in branhces实现）里有没有berry

代码：

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 label(t) == 'berry'
    elif label(t) == 'berry':
        return True
    else:
        for b in branches(t):
            if berry_finder(b):
                return True
        return False

Data Abstraction - Q4: Don't violate the abstraction barrier!

Note: this question has no code-writing component (if you implemented distance and closer_city correctly!)

def check_city_abstraction():
    """
    There's nothing for you to do for this function, it's just here for the extra doctest
    >>> change_abstraction(True)
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    >>> change_abstraction(False)
    """

Data Abstraction - Q3: Closer city

Next, implement closer_city, a function that takes a latitude, longitude, and two cities, and returns the name of the city that is relatively closer to the provided latitude and longitude.

You may only use the selectors and constructors introduced above and the distance function you just defined for this question.

def closer_city(lat, lon, city_a, city_b):
    """
    Returns the name of either city_a or city_b, whichever is closest to
    coordinate (lat, lon). If the two cities are the same distance away
    from the coordinate, consider city_b to be the closer city.

    >>> berkeley = make_city('Berkeley', 37.87, 112.26)
    >>> stanford = make_city('Stanford', 34.05, 118.25)
    >>> closer_city(38.33, 121.44, berkeley, stanford)
    'Stanford'
    >>> bucharest = make_city('Bucharest', 44.43, 26.10)
    >>> vienna = make_city('Vienna', 48.20, 16.37)
    >>> closer_city(41.29, 174.78, bucharest, vienna)
    'Bucharest'
    """
    "*** YOUR CODE HERE ***"
    given_location = make_city("given_location", lat, lon)
    if distance(city_a, given_location) < distance(city_b, given_location):
        return get_name(city_a)
    else:
        return get_name(city_b)

Data Abstraction - Q2: Distance

We will now implement the function distance, which computes the distance between two city objects. Recall that the distance between two coordinate pairs (x1, y1) and (x2, y2) can be found by calculating the sqrt of (x1 - x2)**2 + (y1 - y2)**2. We have already imported sqrt for your convenience. Use the latitude and longitude of a city as its coordinates; you'll need to use the selectors to access this info!

def distance(city_a, city_b):
    """
    >>> city_a = make_city('city_a', 0, 1)
    >>> city_b = make_city('city_b', 0, 2)
    >>> distance(city_a, city_b)
    1.0
    >>> city_c = make_city('city_c', 6.5, 12)
    >>> city_d = make_city('city_d', 2.5, 15)
    >>> distance(city_c, city_d)
    5.0
    """
    "*** YOUR CODE HERE ***"
    return sqrt(pow(get_lat(city_a) - get_lat(city_b), 2) + pow(get_lon(city_a) - get_lon(city_b), 2))

List Comprehensions - Q1: Couple

Implement the function couple, which takes in two lists and returns a list that contains lists with i-th elements of two sequences coupled together. You can assume the lengths of two sequences are the same. Try using a list comprehension. (Hint: You may find the built in range function helpful.)

def couple(s, t):
    """Return a list of two-element lists in which the i-th element is [s[i], t[i]].

    >>> a = [1, 2, 3]
    >>> b = [4, 5, 6]
    >>> couple(a, b)
    [[1, 4], [2, 5], [3, 6]]
    >>> c = ['c', 6]
    >>> d = ['s', '1']
    >>> couple(c, d)
    [['c', 's'], [6, '1']]
    """
    assert len(s) == len(t)
    "*** YOUR CODE HERE ***"
    return [[s[i], t[i]] for i in range(len(s))]

Topics

number_tree = tree(1,
         [tree(2),
          tree(3,
               [tree(4),
                tree(5)]),
          tree(6,
               [tree(7)])])

1
 / | \
2  3  6
  / \  \
 4   5  7

label(branches(number_tree)[1])

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)

[<expression> for <element> in <sequence> if <conditional>]

>>> [i**2 for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]