Homework 4
Due by 11:59pm on Monday, 7/10
Instructions
Download hw04.zip.
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. Check that you have successfully submitted your code on
okpy.org.
See Lab 0
for more instructions on submitting assignments.
Using OK: If you have any questions about using OK, please refer to this guide.
Readings: You might find the following references useful:
You may choose to work with a partner on homework questions, but you must submit your own solution. That is, share ideas rather than code.
Linked Lists
Question 1: Change
Write a function that takes in a linked list, lst
, and two elements,
s
and t
. The function returns a copy of lst
but with all instances of s
replaced with t
.
def change(lst, s, t):
"""Returns a link matching lst but with all instances of s (if any)
replaced by t.
>>> lst = link(1, link(2, link(3)))
>>> new = change(lst, 3, 1)
>>> print_link(new)
1 2 1
>>> newer = change(new, 1, 2)
>>> print_link(newer)
2 2 2
>>> newest = change(newer, 5, 1)
>>> print_link(newest)
2 2 2
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q change
Question 2: Reverse
Write iterative and recursive functions that reverse a given linked list,
producing a new linked list with the elements in reverse order. Use only the
link
constructor and first
and rest
selectors to manipulate linked lists.
(You may write and use helper functions.)
def reverse_iterative(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reversed_primes = reverse_iterative(primes)
>>> print_link(reversed_primes)
7 5 3 2
"""
"*** YOUR CODE HERE ***"
def reverse_recursive(s):
"""Return a reversed version of a linked list s.
>>> primes = link(2, link(3, link(5, link(7, empty))))
>>> reversed_primes = reverse_recursive(primes)
>>> print_link(reversed_primes)
7 5 3 2
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q reverse_iterative
python3 ok -q reverse_recursive
Question 3: Insert
Implement the insert
function that creates a copy of the original
list with an item inserted at the specific index. If the index is
greater than the current length, you should insert the item
at the end of the list. Review your solution for change
if you are
stuck.
Hint: This will be much easier to implement using recursion, rather than using iteration!
Note: Remember we are not actually inserting the item into the original linked list. Instead, we are creating a copy of the original linked list, but with the provided item added at the specified index. The original linked list stays the same.
def insert(lst, item, index):
"""Returns a link matching lst but with the given item inserted at the
specified index. If the index is greater than the current length, the item
is appended to the end of the list.
>>> lst = link(1, link(2, link(3)))
>>> new = insert(lst, 9001, 1)
>>> print_link(new)
1 9001 2 3
>>> newer = insert(new, 9002, 15)
>>> print_link(newer)
1 9001 2 3 9002
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q insert
Trees
Question 4: Acorn Finder
The squirrels on campus need your help! There are a lot of trees on campus and
the squirrels would like to know which ones contain acorns. Define the function
acorn_finder
, which takes in a tree and returns True
if the tree contains a
node with the value 'acorn'
and False
otherwise.
def acorn_finder(t):
"""Returns True if t contains a node with the value 'acorn' and
False otherwise.
>>> scrat = tree('acorn')
>>> acorn_finder(scrat)
True
>>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
>>> acorn_finder(sproul)
True
>>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
>>> acorn_finder(numbers)
False
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q acorn_finder
Question 5: Same shape
Define a function same_shape
that, given two trees, t1
and t2
,
returns True
if the two trees have the same shape (but not
necessarily the same data in each node) and False
otherwise.
def same_shape(t1, t2):
"""Return True if t1 is indentical in shape to t2.
>>> test_tree1 = tree(1, [tree(2), tree(3)])
>>> test_tree2 = tree(4, [tree(5), tree(6)])
>>> test_tree3 = tree(1,
... [tree(2,
... [tree(3)])])
>>> test_tree4 = tree(4,
... [tree(5,
... [tree(6)])])
>>> same_shape(test_tree1, test_tree2)
True
>>> same_shape(test_tree3, test_tree4)
True
>>> same_shape(test_tree2, test_tree4)
False
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q same_shape
Question 6: 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 first two, 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 ***"
Use OK to test your code:
python3 ok -q add_trees
Mobiles
Acknowledgements. This mobile example is based on a classic problem from Structure and Interpretation of Computer Programs, Section 2.2.2.
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, which use
the tree
data abstraction for their representation.
- A
mobile
has a left side (index 0) and a right side (index 1). - A
side
has a length and a structure, which is either amobile
orweight
. - A
weight
has a size, which is a positive number.
Question 7: Weights
Implement the weight
data abstraction by completing the weight
constructor,
the size
selector, and the is_weight
predicate so that a weight is
represented using a tree. The total_weight
example is provided in hw04.py to demonstrate
use of the mobile, side, and weight abstractions.
def mobile(left, right):
"""Construct a mobile from a left side and a right side."""
return tree(None, [left, right])
def sides(m):
"""Select the sides of a mobile."""
return branches(m)
def side(length, mobile_or_weight):
"""Construct a side: a length of rod with a mobile or weight at the end."""
return tree(length, [mobile_or_weight])
def length(s):
"""Select the length of a side."""
return root(s)
def end(s):
"""Select the mobile or weight hanging at the end of a side."""
return branches(s)[0]
def weight(size):
"""Construct a weight of some size."""
assert size > 0
"*** YOUR CODE HERE ***"
def size(w):
"""Select the size of a weight."""
"*** YOUR CODE HERE ***"
def is_weight(w):
"""Whether w is a weight, not a mobile."""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q total_weight
Question 8: Balanced
Implement the balanced
function, which returns whether m
is a balanced
mobile. A mobile is said to be balanced if the torque applied by its left
side is equal to that applied by its right side (that is, if the length
of the left rod multiplied by the total weight hanging from that rod is equal
to the corresponding product for the right side) and if each of the submobiles
hanging off its sides is 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 ***"
Use OK to test your code:
python3 ok -q balanced