Lab 5: Python Lists, Trees

Q2: 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 [] if len(deck)==0 else deck[0:len(deck)//2]+deck[len(deck)-1:len(deck)//2-1:-1] if len(deck)%2==0 else deck[0:len(deck)//2]+deck[len(deck)-1:len(deck)//2-1:-1]
    #return [] if len(deck)==0 else [deck[x] for x in range(0,len(deck)//2)]+[deck[x] for x in range(len(deck)-1,len(deck)//2-1,-1)]
    return [deck[(i%2)*len(deck)//2+i//2]for i in range(len(deck))]

Q4: 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

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 ***"

Use Ok to test your code:

python3 ok -q sprout_leaves

Q5: Don't violate the abstraction barrier!

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

When writing functions that use an ADT, we should use the constructor(s) and selector(s) whenever possible instead of assuming the ADT's implementation. Relying on a data abstraction's underlying implementation is known as?violating the abstraction barrier, and we never want to do this!

It's possible that you passed the doctests for?berry_finder?and?sprout_leaves?even if you violated the abstraction barrier. To check whether or not you did so, run the following command:

Use Ok to test your code:

python3 ok -q check_abstraction

The?check_abstraction?function exists only for the doctest, which swaps out the implementations of the?tree?abstraction with something else, runs the tests from the previous two parts, then restores the original abstraction.

The nature of the abstraction barrier guarantees that changing the implementation of an ADT shouldn't affect the functionality of any programs that use that ADT, as long as the constructors and selectors were used properly.

If you passed the Ok tests for the previous questions but not this one, the fix is simple! Just replace any code that violates the abstraction barrier, i.e. creating a tree with a new list object or indexing into a tree, with the appropriate constructor or selector.

Make sure that your functions pass the tests with both the first and the second implementations of the Tree ADT and that you understand why they should work for both before moving on.

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 ***"

代码一分析：

    # 不能过抽象
    # def find_leaves(t):
    #     for branch in branches(t):
    #         sprout_leaves(branch,leaves)
    #     return t
    # def add_leaves(t):
    #     if is_leaf(t):
    #         t += [tree(x) for x in leaves]
    #         return t
    # find_leaves(t)
    # add_leaves(t)
    # return t

?代码一（Q5报错）（希望有大佬能指点一下）：

Traceback (most recent call last):
  File "D:\pycharm\python document\CS61A class homework\lab05\lab05.py", line 97, in sprout_leaves
    find_leaves(t)
  File "D:\pycharm\python document\CS61A class homework\lab05\lab05.py", line 91, in find_leaves
    sprout_leaves(branch,leaves)
  File "D:\pycharm\python document\CS61A class homework\lab05\lab05.py", line 98, in sprout_leaves
    add_leaves(t)
  File "D:\pycharm\python document\CS61A class homework\lab05\lab05.py", line 95, in add_leaves
    t += [tree(x) for x in leaves]
TypeError: unsupported operand type(s) for +=: 'dict' and 'list'

# Error: expected

# but got
#     Traceback (most recent call last):
#       ...
#     TypeError: unsupported operand type(s) for +=: 'dict' and 'list'

---------------------------------------------------------------------
Test summary
    0 test cases passed before encountering first failed test case

Backup... 50.0% complete

?代码二分析：

1.首先判断是否为末端叶

是：加上新叶

否（即存在其他的枝条）：

遍历其枝条

2.重复之前的工作

    #完美代码
    if is_leaf(t):
      return tree(label(t), [tree(x) for x in leaves])
    return tree(label(t), [sprout_leaves(b, leaves) for b in branches(t)])

Q6: 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.

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 ***"

分析：

1.?????b1,b2为两个添加树的branch

????????取b为空列表

2.遍历branch元素

i ? ?属于（0-? ? ? ? ?（对于两个branch元素个数 ????????取???????? 最大值））

(1）如果i<len1 and <len2:

（说明两树共有（共有branch的branch也可能有差异），所以继续深层遍历）

b.apppend(add_tree(b1[i],b2[i))????????

( 2 )i>len1 or i >len2????????(不共有的branch可以直接添加)

3.最后返回tree(label(b1)+label(b2),b)

（之前添加都是branch，所以b就是所求树的branch）

答案代码：?

    b1, b2 = branches(t1), branches(t2)
    b = []
    for i in range(max(len(b1), len(b2))):
        if i >= len(b1):
            b.append(b2[i])
        elif i >= len(b2):
            b.append(b1[i])
        else:
            b.append(add_trees(b1[i], b2[i]))
    return tree(label(t1) + label(t2), b)

完整答案代码（最近配了差不多两天的cs106l的配置，还没成功，有人配置成功的，麻烦私聊我，希望您能有时间）：?