HW 3
Abstraction, Lists, Trees and a classic (Mobiles) problem from the original SICP by MIT
The Mobiles problem was quite interesting. :)
Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/hw/hw03/
Solution: https://github.com/tomthestrom/cs61a/blob/master/homeworks/hw03/hw03.py
Q1: Taxicab Distance
Implement taxicab, which computes the taxicab distance between two intersections using the following data abstraction.
def intersection(st, ave):
"""Represent an intersection using the Cantor pairing function."""
return (st+ave)*(st+ave+1)//2 + ave
def street(inter):
return w(inter) - avenue(inter)
def avenue(inter):
return inter - (w(inter) ** 2 + w(inter)) // 2
w = lambda z: int(((8*z+1)**0.5-1)/2)
def taxicab(a, b):
"""Return the taxicab distance between two intersections.
>>> times_square = intersection(46, 7)
>>> ess_a_bagel = intersection(51, 3)
>>> taxicab(times_square, ess_a_bagel)
9
>>> taxicab(ess_a_bagel, times_square)
9
"""
"*** YOUR CODE HERE ***"Q1: Solution
def taxicab(a, b):
"""Return the taxicab distance between two intersections.
>>> times_square = intersection(46, 7)
>>> ess_a_bagel = intersection(51, 3)
>>> taxicab(times_square, ess_a_bagel)
9
>>> taxicab(ess_a_bagel, times_square)
9
"""
"*** YOUR CODE HERE ***"
return abs(street(a) - street(b)) + abs(avenue(a) - avenue(b))Q2: Flatten
Write a function flatten that takes a (possibly deep) list and "flattens" it. For example:
>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]Make sure your solution does not mutate the input list.
def flatten(lst):
"""Returns a flattened version of lst.
>>> flatten([1, 2, 3]) # normal list
[1, 2, 3]
>>> x = [1, [2, 3], 4] # deep list
>>> flatten(x)
[1, 2, 3, 4]
>>> x # Ensure x is not mutated
[1, [2, 3], 4]
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> flatten(x)
[1, 1, 1, 1, 1, 1]
>>> x
[[1, [1, 1]], 1, [1, 1]]
"""
"*** YOUR CODE HERE ***"Q2: Solution
def flatten(lst):
"""Returns a flattened version of lst.
>>> flatten([1, 2, 3]) # normal list
[1, 2, 3]
>>> x = [1, [2, 3], 4] # deep list
>>> flatten(x)
[1, 2, 3, 4]
>>> x # Ensure x is not mutated
[1, [2, 3], 4]
>>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> flatten(x)
[1, 1, 1, 1, 1, 1]
>>> x
[[1, [1, 1]], 1, [1, 1]]
"""
"*** YOUR CODE HERE ***"
flat_lst = []
for item in lst:
if type(item) == list:
flat_lst += flatten(item)
else:
flat_lst += [item]
return flat_lstQ3: Replace Leaf
Define replace_leaf, which takes a tree t, a value old, and a value new. replace_leaf returns a new tree that's the same as t except that every leaf value equal to old has been replaced with new.
def replace_leaf(t, old, new):
"""Returns a new tree where every leaf value equal to old has
been replaced with new.
>>> 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 ***"Q3: Solution
def replace_leaf(t, old, new):
"""Returns a new tree where every leaf value equal to old has
been replaced with new.
>>> 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 is_leaf(t) and label(t) == old:
new_label = new
else:
new_label = label(t)
new_branches = [replace_leaf(b, old, new) for b in branches(t)]
return tree(new_label, new_branches)Mobiles
Acknowledgements. This mobile example is based on a classic problem from Structure and Interpretation of Computer Programs, Section 2.2.2.
Hint: for more information on this problem (with more pictures!) please refer to this document
A mobile is a type of hanging sculpture. A binary mobile consists of two sides. Each side is a rod of a certain length, from which hangs either a weight or another mobile.
We will represent a binary mobile using the data abstractions below.
A
mobilehas a leftsideand a rightside.A
sidehas a positive length and something hanging at the end, either amobileorweight.A
weighthas a positive size
Q4: Weights
We will represent a binary mobile using the data abstractions below.
A
mobilehas a leftsideand a rightside.A
sidehas a positive length and something hanging at the end, either amobileorweight.A
weighthas a positive size
def mobile(left, right):
"""Construct a mobile from a left side and a right side."""
assert is_side(left), "left must be a side"
assert is_side(right), "right must be a side"
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 side of a mobile."""
assert is_mobile(m), "must call left on a mobile"
return m[1]
def right(m):
"""Select the right side of a mobile."""
assert is_mobile(m), "must call right on a mobile"
return m[2]def side(length, mobile_or_weight):
"""Construct a side: a length of rod with a mobile or weight at the end."""
assert is_mobile(mobile_or_weight) or is_weight(mobile_or_weight)
return ['side', length, mobile_or_weight]
def is_side(s):
"""Return whether s is a side."""
return type(s) == list and len(s) == 3 and s[0] == 'side'
def length(s):
"""Select the length of a side."""
assert is_side(s), "must call length on a side"
return s[1]
def end(s):
"""Select the mobile or weight hanging at the end of a side."""
assert is_side(s), "must call end on a side"
return s[2]Implement the weight data abstraction by completing the weight constructor and the size selector so that a weight is represented using a two-element list where the first element is the string 'weight'. The total_weight example is provided to demonstrate use of the mobile, side, and weight abstractions.
def weight(size):
"""Construct a weight of some size."""
assert size > 0
"*** YOUR CODE HERE ***"
def size(w):
"""Select the size of a weight."""
assert is_weight(w), 'must call size on a weight'
"*** YOUR CODE HERE ***"
def is_weight(w):
"""Whether w is a weight."""
return type(w) == list and len(w) == 2 and w[0] == 'weight'Q4: Solution
def weight(size):
"""Construct a weight of some size."""
assert size > 0
"*** YOUR CODE HERE ***"
return ['weight', size]
def size(w):
"""Select the size of a weight."""
assert is_weight(w), 'must call size on a weight'
"*** YOUR CODE HERE ***"
return w[1]Q5: Balanced
Hint: for more information on this problem (with more pictures!) please refer to this document
Implement the balanced function, which returns whether m is a balanced mobile. A mobile is balanced if two conditions are met:
The torque applied by its left side is equal to that applied by its right side. Torque of the left side is the length of the left rod multiplied by the total weight hanging from that rod. Likewise for the right.
Each of the mobiles hanging at the end of its sides is balanced.
Hint: You may find it helpful to assume that weights themselves are balanced.
def balanced(m):
"""Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> w = mobile(side(3, t), side(2, u))
>>> balanced(w)
False
>>> balanced(mobile(side(1, v), side(1, w)))
False
>>> balanced(mobile(side(1, w), side(1, v)))
False
"""
"*** YOUR CODE HERE ***"Q5: Solution
def balanced(m):
"""Return whether m is balanced.
>>> t, u, v = examples()
>>> balanced(t)
True
>>> balanced(v)
True
>>> w = mobile(side(3, t), side(2, u))
>>> balanced(w)
False
>>> balanced(mobile(side(1, v), side(1, w)))
False
>>> balanced(mobile(side(1, w), side(1, v)))
False
"""
"*** YOUR CODE HERE ***"
def get_side_torque(side):
return length(side) * total_weight(end(side))
def is_mobile_balanced(m):
return get_side_torque(left(m)) == get_side_torque(right(m))
if is_mobile(m):
return is_mobile_balanced(m) and balanced(end(left(m))) and balanced(end(right(m)))
else:
return TrueQ6: Totals
Implement totals_tree, which takes a mobile (or weight) and returns a tree whose root is its total weight and whose branches are trees for the ends of the sides.
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
"""
"*** YOUR CODE HERE ***"Q6: Solution
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
"""
"*** YOUR CODE HERE ***"
if is_weight(m):
return tree(size(m))
else:
left_branch = totals_tree(end(left(m)))
right_branch = totals_tree(end(right(m)))
return tree(total_weight(m), [left_branch, right_branch])Last updated