passphrase = ‘*** PASSPHRASE HERE ***’
def midsem_survey(p):
You do not need to understand this code.
>>> midsem_survey(passphrase)
‘3d9f1125b109b311959d068240016badb874603eab75302a445e1a50’
import hashlib
return hashlib.sha224(p.encode(‘utf-8’)).hexdigest()
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(mass):
“””Construct a planet of some mass.”””
assert mass > 0
“*** YOUR CODE HERE ***”
def mass(w):
“””Select the mass of a planet.”””
assert is_planet(w), ‘must call mass on a planet’
“*** YOUR CODE HERE ***”
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)
>>> total_weight(u)
>>> total_weight(v)
if is_planet(m):
return mass(m)
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)
>>> balanced(v)
>>> w = mobile(arm(3, t), arm(2, u))
>>> balanced(w)
>>> balanced(mobile(arm(1, v), arm(1, w)))
>>> balanced(mobile(arm(1, w), arm(1, v)))
>>> from construct_check import check
>>> # checking for abstraction barrier violations by banning indexing
>>> check(HW_SOURCE_FILE, ‘balanced’, [‘Index’])
“*** YOUR CODE HERE ***”
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))
>>> print_tree(totals_tree(u))
>>> print_tree(totals_tree(v))
>>> from construct_check import check
>>> # checking for abstraction barrier violations by banning indexing
>>> check(HW_SOURCE_FILE, ‘totals_tree’, [‘Index’])
“*** YOUR CODE HERE ***”
def replace_loki_at_leaf(t, lokis_replacement):
“””Returns a new tree where every leaf value equal to “loki” has
been replaced with lokis_replacement.
>>> yggdrasil = tree(‘odin’,
… [tree(‘balder’,
… [tree(‘loki’),
… tree(‘freya’)]),
… tree(‘frigg’,
… [tree(‘loki’)]),
… tree(‘loki’,
… [tree(‘sif’),
… tree(‘loki’)]),
… tree(‘loki’)])
>>> laerad = copy_tree(yggdrasil) # copy yggdrasil for testing purposes
>>> print_tree(replace_loki_at_leaf(yggdrasil, ‘freya’))
>>> laerad == yggdrasil # Make sure original tree is unmodified
“*** YOUR CODE HERE ***”
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)
>>> has_path(greetings, ‘h’)
>>> has_path(greetings, ‘i’)
>>> has_path(greetings, ‘hi’)
>>> has_path(greetings, ‘hello’)
>>> has_path(greetings, ‘hey’)
>>> has_path(greetings, ‘bye’)
>>> has_path(greetings, ‘hint’)
assert len(word) > 0, ‘no path for empty word.’
“*** YOUR CODE HERE ***”
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)
def interval(a, b):
“””Construct an interval from a to b.”””
assert a <= b, 'Lower bound cannot be greater than upper bound'
return [a, b]
def lower_bound(x):
"""Return the lower bound of interval x."""
"*** YOUR CODE HERE ***"
def upper_bound(x):
"""Return the upper bound of interval x."""
"*** YOUR CODE HERE ***"
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)
def mul_interval(x, y):
"""Return the interval that contains the product of any value in x and any
value in y."""
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 sub_interval(x, y):
"""Return the interval that contains the difference between any value in x
and any value in y."""
"*** YOUR CODE HERE ***"
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)
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)
r1 = interval(1, 1) # Replace this line!
r2 = interval(1, 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))
>>> print_tree(tree(1, [tree(2)]))
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> print_tree(numbers)
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)
return tree(label(t), [copy_tree(b) for b in branches(t)])