Homework 4: Data Abstraction, Trees

Q9: Div Interval（这题有坑）

Alyssa implements division below by multiplying by the reciprocal of?y. Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Add an?assert?statement to Alyssa's code to ensure that no such interval is used as a divisor:

def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
    return mul_interval(x, reciprocal_y)

?1.第二个解锁样例：

输入：AssertionError（大小写可能有错误）

?2.需要修改两个函数:

（第二个样例把x,y重新定义为lambda，而不是列表）

TypeError: 'function' object is not subscriptable(如果没判断x是否为函数)

（不建议这样做，抽象后的代码在p3）

from inspect import isfunction
def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    if isfunction(x):
        p1 = x(0) * y(0)
        p2 = x(0) * y(1)
        p3 = x(1) * y(0)
        p4 = x(1) * y(1)
        return lambda x: min(p1, p2, p3, p4) if x == 0 else max(p1, p2, p3, p4)
    else:
        p1 = x[0] * y[0]
        p2 = x[0] * y[1]
        p3 = x[1] * y[0]
        p4 = x[1] * y[1]
        return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]

def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    assert lower_bound(y) >0 or upper_bound(y)<0, "AssertionError!"
    reciprocal_y = interval(1 / upper_bound(y), 1 / lower_bound(y))
    return mul_interval(x, reciprocal_y)

3.（才发现这样是为了验证抽象，修改代码后在下面）：

def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    p1 = lower_bound(x)*lower_bound(y)
    p2 = lower_bound(x)*upper_bound(y)
    p3 = upper_bound(x)*lower_bound(y)
    p4 = upper_bound(x)*upper_bound(y)
    return interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))

4.pass情况：?

Assignment: Homework 4
OK, version v1.18.1
=====================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests

---------------------------------------------------------------------
Test summary
    2 test cases passed! No cases failed.

Q11: Quadratic

Write a function?quadratic?that returns the interval of all values?f(t)?such that?t?is in the argument interval?x?and?f(t)?is a?quadratic function:

f(t) = a*t*t + b*t + c

Make sure that your implementation returns the smallest such interval, one that does not suffer from the multiple references problem.

Hint: the derivative?f'(t) = 2*a*t + b, and so the extreme point of the quadratic is?-b/(2*a):

注意使用抽象函数：?

def quadratic(x, a, b, c):
    """Return the interval that is the range of the quadratic defined by
    coefficients a, b, and c, for domain interval x.

    >>> str_interval(quadratic(interval(0, 2), -2, 3, -1))
    '-3 to 0.125'
    >>> str_interval(quadratic(interval(1, 3), 2, -3, 1))
    '0 to 10'
    """
    "*** YOUR CODE HERE ***"
    def f(t):
        return a * t * t + b * t + c

    l,r=f(lower_bound(x)),f(upper_bound(x))
    turning_point = -b / (2 * a)
    
    if upper_bound(x)>turning_point>lower_bound(x):
        return interval(min(l,r,f(turning_point)),max(l,r,f(turning_point)))
    else:
        return interval(min(l,r),max(l,r))

完整答案代码:

HW_SOURCE_FILE = __file__


def mobile(left, right):
    """Construct a mobile from a left arm and a right arm."""
    assert is_arm(left), "left must be a arm"
    assert is_arm(right), "right must be a 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 a 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 a arm."""
    return type(s) == list and len(s) == 3 and s[0] == 'arm'


def length(s):
    """Select the length of a arm."""
    assert is_arm(s), "must call length on a arm"
    return s[1]


def end(s):
    """Select the mobile or planet hanging at the end of a arm."""
    assert is_arm(s), "must call end on a arm"
    return s[2]


def planet(size):
    """Construct a planet of some size."""
    assert size > 0
    return ['planet', size]


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


def is_planet(w):
    """Whether w is a planet."""
    return type(w) == list and len(w) == 2 and w[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_weight(m):
    """Return the total weight of m, a planet or mobile.

    >>> t, u, v = examples()
    >>> total_weight(t)
    3
    >>> total_weight(u)
    6
    >>> total_weight(v)
    9
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'total_weight', ['Index'])
    True
    """
    if is_planet(m):
        return size(m)
    else:
        assert is_mobile(m), "must get total weight of a mobile or a planet"
        return total_weight(end(left(m))) + total_weight(end(right(m)))


def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> w = mobile(arm(3, t), arm(2, u))
    >>> balanced(w)
    False
    >>> balanced(mobile(arm(1, v), arm(1, w)))
    False
    >>> balanced(mobile(arm(1, w), 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 ***"

    def check_balance(test_arm):
        if is_planet(test_arm[2]):
            weight = total_weight(test_arm[2])
        else:
            if not balanced(test_arm[2]):
                return False
            else:
                weight = total_weight(test_arm[2])
        return length(test_arm), weight

    if check_balance(m[1]):
        left_len, left_weight = check_balance(m[1])
    else:
        return False

    if check_balance(m[2]):
        right_len, right_weight = check_balance(m[2])
    else:
        return False
    if left_len * left_weight == right_len * right_weight:
        return True
    else:
        return False


def totals_tree(m):
    """Return a tree representing the mobile with its total weight at the root.

    >>> t, u, v = examples()
    >>> print_tree(totals_tree(t))
    3
      2
      1
    >>> print_tree(totals_tree(u))
    6
      1
      5
        3
        2
    >>> print_tree(totals_tree(v))
    9
      3
        2
        1
      6
        1
        5
          3
          2
    >>> from construct_check import check
    >>> # checking for abstraction barrier violations by banning indexing
    >>> check(HW_SOURCE_FILE, 'totals_tree', ['Index'])
    True
    """
    "*** YOUR CODE HERE ***"
    if is_planet(m):
        return [m[1]]
    else:
        toal_label = total_weight(m[1][2]) + total_weight(m[2][2])
        return tree(toal_label, [totals_tree(m[1][2]), totals_tree(m[2][2])])


# totals_tree(t)

def replace_leaf(t, find_value, replace_value):
    """Returns a new tree where every leaf value equal to find_value has
    been replaced with replace_value.

    >>> yggdrasil = tree('odin',
    ...                  [tree('balder',
    ...                        [tree('thor'),
    ...                         tree('freya')]),
    ...                   tree('frigg',
    ...                        [tree('thor')]),
    ...                   tree('thor',
    ...                        [tree('sif'),
    ...                         tree('thor')]),
    ...                   tree('thor')])
    >>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
    >>> print_tree(replace_leaf(yggdrasil, 'thor', 'freya'))
    odin
      balder
        freya
        freya
      frigg
        freya
      thor
        sif
        freya
      freya
    >>> laerad == yggdrasil # Make sure original tree is unmodified
    True
    """
    "*** YOUR CODE HERE ***"
    if not t:
        return []
    if label(t) == find_value and not branches(t):
        t_branches = list(replace_leaf(branch1, find_value, replace_value) for branch1 in branches(t))
        return tree(replace_value, t_branches)
    else:
        t_branches = list(replace_leaf(branch1, find_value, replace_value) for branch1 in branches(t))
        return tree(label(t), t_branches)


def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
    target = []
    target.append(label(t))
    for t_branch in branches(t):
        target += preorder(t_branch)
    return target


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

    >>> 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
    """
    assert len(phrase) > 0, 'no path for empty phrases.'
    "*** YOUR CODE HERE ***"

    # 检查首项
    i = 1
    find_setence = preorder(t)
    if phrase[0] != find_setence[0]:
        return False
    else:
        if i == len(phrase):
            return True
    # 查找后续部分
    for alpha in find_setence[1:]:
        if alpha == phrase[i]:
            i += 1
            if i == len(phrase):
                return True
    return False


def interval(a, b):
    """Construct an interval from a to b."""
    return [a, b]


def lower_bound(x):
    """Return the lower bound of interval x."""
    "*** YOUR CODE HERE ***"
    return x[0]


def upper_bound(x):
    """Return the upper bound of interval x."""
    "*** YOUR CODE HERE ***"
    return x[1]


def str_interval(x):
    """Return a string representation of interval x.
    """
    return '{0} to {1}'.format(lower_bound(x), upper_bound(x))


def add_interval(x, y):
    """Return an interval that contains the sum of any value in interval x and
    any value in interval y."""
    lower = lower_bound(x) + lower_bound(y)
    upper = upper_bound(x) + upper_bound(y)
    return interval(lower, upper)


from inspect import isfunction


def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    # if isfunction(x):
    #     p1 = x(0) * y(0)
    #     p2 = x(0) * y(1)
    #     p3 = x(1) * y(0)
    #     p4 = x(1) * y(1)
    #     return lambda x: min(p1, p2, p3, p4) if x == 0 else max(p1, p2, p3, p4)
    # else:
    #     p1 = x[0]*y[0]
    #     p2 = x[0] * y[1]
    #     p3 = x[1] * y[0]
    #     p4 = x[1] * y[1]
    #     return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]
    p1 = lower_bound(x)*lower_bound(y)
    p2 = lower_bound(x)*upper_bound(y)
    p3 = upper_bound(x)*lower_bound(y)
    p4 = upper_bound(x)*upper_bound(y)
    return interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4))


def sub_interval(x, y):
    """Return the interval that contains the difference between any value in x
    and any value in y."""
    "*** YOUR CODE HERE ***"
    return interval(lower_bound(x) - upper_bound(y), upper_bound(x) - lower_bound(y))


def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    # assert lower_bound(y) >0 or upper_bound(y)<0, "AssertionError!"
    # reciprocal_y = interval(1 / upper_bound(y), 1 / lower_bound(y))
    # return mul_interval(x, reciprocal_y)
    assert 0 < lower_bound(y) or 0 > upper_bound(y)
    reciprocal_y = interval(1 / upper_bound(y), 1 / lower_bound(y))
    return mul_interval(x, reciprocal_y)


def multiple_references_explanation():
    return """The multiple reference problem..."""


def quadratic(x, a, b, c):
    """Return the interval that is the range of the quadratic defined by
    coefficients a, b, and c, for domain interval x.

    >>> str_interval(quadratic(interval(0, 2), -2, 3, -1))
    '-3 to 0.125'
    >>> str_interval(quadratic(interval(1, 3), 2, -3, 1))
    '0 to 10'
    """
    "*** YOUR CODE HERE ***"
    def f(t):
        return a * t * t + b * t + c

    l,r=f(lower_bound(x)),f(upper_bound(x))
    turning_point = -b / (2 * a)

    if upper_bound(x)>turning_point>lower_bound(x):
        return interval(min(l,r,f(turning_point)),max(l,r,f(turning_point)))
    else:
        return interval(min(l,r),max(l,r))
    # if not isfunction(x):
    #     x1 = x
    # else:
    #     x1 = [x(0), x(1)]
    #
    # turning_point = -b / (2 * a)
    #
    # if lower_bound(x) < turning_point < upper_bound(x):
    #     if a > 0:
    #         if not isfunction(x):
    #             return [f(turning_point), max(f(x1[0]), f(x1[1]))]
    #         else:
    #             return lambda x:f(turning_point) if x==0 else max(f(x1[0]), f(x1[1]))
    #     else:
    #         if not isfunction(x):
    #             return [min(f(x1[0]), f(x1[1])), f(turning_point)]
    #         else:
    #             return lambda x:  min(f(x1[0]), f(x1[1])) if x == 0 else f(turning_point)
    # else:
    #     if not isfunction(x):
    #         return [min(f(x1[0]), f(x1[1])), max(f(x1[0]), f(x1[1]))]
    #     else:
    #         return lambda x:min(f(x1[0]), f(x1[1]))if x==0 else max(f(x1[0]), f(x1[1]))



def par1(r1, r2):
    return div_interval(mul_interval(r1, r2), add_interval(r1, r2))


def par2(r1, r2):
    one = interval(1, 1)
    rep_r1 = div_interval(one, r1)
    rep_r2 = div_interval(one, r2)
    return div_interval(one, add_interval(rep_r1, rep_r2))


def check_par():
    """Return two intervals that give different results for parallel resistors.

    >>> r1, r2 = check_par()
    >>> x = par1(r1, r2)
    >>> y = par2(r1, r2)
    >>> lower_bound(x) != lower_bound(y) or upper_bound(x) != upper_bound(y)
    True
    """
    r1 = interval(2, 1)  # Replace this line!
    r2 = interval(2, 1)  # Replace this line!
    return r1, r2


# Tree ADT

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)])