Due by 11:59pm on Monday, 3/16
Download hw06.zip. Inside the archive, you will find a file called hw06.py, along with a copy of the OK autograder.
Submission: When you are done, submit with
python3 ok --submit. You may submit more than once before
the deadline; only the final submission will be scored.
The ok program helps you test your code and track your progress.
The first time you run the autograder, you will be asked to log in with your
@berkeley.edu account using your web browser. Please do so. Each time you run
ok, it will back up your work and progress on our servers.
You can run all the doctests with the following command:
python3 okTo test a specific question, use the -q option with the
name of the function:
python3 ok -q <function>By default, only tests that fail will appear. If you
want to see how you did on all tests, you can use the -v
option:
python3 ok -vIf you do not want to send your progress to our server or you have any
problems logging in, add the --local flag to block all
communication:
python3 ok --localWhen you are ready to submit, run ok with the
--submit option:
python3 ok --submitReadings: You might find the following references useful:
The Link class from lecture implements the linked list data type:
class Link:
"""A linked list.
>>> s = Link(3, Link(4, Link(5)))
>>> len(s)
3
>>> s[2]
5
>>> s
Link(3, Link(4, Link(5)))
"""
empty = ()
def __init__(self, first, rest=empty):
assert rest is Link.empty or isinstance(rest, Link)
self.first = first
self.rest = rest
def __getitem__(self, i):
if i == 0:
return self.first
else:
return self.rest[i-1]
def __len__(self):
return 1 + len(self.rest)
def __repr__(self):
if self.rest:
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''
return 'Link({0}{1})'.format(self.first, rest_str)Implement deep_map, which takes a function f and a Link s. It returns a
linked list with the same structure as s, but with f applied to any
element within s or any Link instance contained in s. The deep_map
function differs from map_link in lecture when s contains a Link as an
element. The deep_map function should recursively apply fn to each of that
Link's elements rather than to that Link itself.
Hint: You may find the built-in isinstance function useful.
def deep_map(f, s):
"""Return a Link with the same structure as s but with fn mapped over
its elements and any elements of linked lists contained anywhere within it.
>>> s = Link(1, Link(Link(2, Link(3)), Link(4)))
>>> deep_map(lambda x: x * x, s)
Link(1, Link(Link(4, Link(9)), Link(16)))
>>> s # unchanged
Link(1, Link(Link(2, Link(3)), Link(4)))
>>> deep_map(lambda x: 2 * x, Link(s, Link(Link(Link(5)))))
Link(Link(2, Link(Link(4, Link(6)), Link(8))), Link(Link(Link(10))))
"""
"*** YOUR CODE HERE ***"Implement reverse, which takes a linked list s and returns a linked list
containing the elements of s in reverse order. The original s should be
unchanged.
def reverse(s):
"""Return a linked list with the elements of s in reverse order.
>>> s = Link(3, Link(5, Link(4, Link(6))))
>>> reverse(s)
Link(6, Link(4, Link(5, Link(3))))
>>> s
Link(3, Link(5, Link(4, Link(6))))
"""
"*** YOUR CODE HERE ***"The Link class can represent lists with cycles. That is, a list may
contain itself as a sublist.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s[20]
3You cannot print a list with a cycle, because its string representation would be infinite.
Implement has_cycle that returns whether its argument, a Link instance,
contains a cycle.
For an extra (optional) challenge, try to implement has_cycle_constant, which
has the same behavior but requires only constant space. The solution is short
(less than 20 lines of code), but requires a clever idea. Try to discover the
solution yourself before asking around:
def has_cycle(s):
"""Return whether Link s contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
"""
"*** YOUR CODE HERE ***"
def has_cycle_constant(s):
"""Return whether Link s contains a cycle.
>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle_constant(t)
False
"""
# Challenge: replace this line with your implementation
return has_cycle(s)A mobile is a type of hanging sculpture. A simple binary mobile consists
of two branches, left and right. Each branch is a rod of a certain length,
from which hangs either a weight or another mobile.
Improve the classes for Branch, Weight, and Mobile below in the
following ways:
weight that gives the total weight of the mobile.is_balanced that
returns True if and only if the Mobile is balanced.When you are finished, all doctests below should pass:
class Mobile:
"""A binary mobile has branches; each branch has a weight or a mobile.
>>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
>>> m.weight
3
>>> m.is_balanced()
True
>>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
>>> m.weight
3
>>> m.left.contents.is_balanced()
False
>>> m.is_balanced() # All submobiles must be balanced for m to be balanced
False
>>> m.left.contents.right.contents.weight = 0.5
>>> m.left.contents.is_balanced()
True
>>> m.is_balanced()
False
>>> m.right.length = 1.5
>>> m.is_balanced()
True
"""
def __init__(self, left, right):
for v in (left, right):
if type(v) != Branch:
raise TypeError(str(v) + ' is not a Branch')
self.left = left
self.right = right
@property
def weight(self):
"""The total weight of the mobile."""
"*** YOUR CODE HERE ***"
def is_balanced(self):
"""True if and only if the mobile is balanced."""
"*** YOUR CODE HERE ***"
class Branch:
"""A branch of a binary mobile."""
def __init__(self, length, contents):
if type(contents) not in (Weight, Mobile):
raise TypeError(str(contents) + ' is not a Weight or Mobile')
self.length = length
self.contents = contents
@property
def torque(self):
"""The torque on the branch"""
return self.length * self.contents.weight
class Weight:
"""A weight at the end of a branch."""
def __init__(self, weight):
self.weight = weight
def is_balanced(self):
return True