Due by 11:59pm on Monday, 7/10

## Instructions

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.

### 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.

>>> new = change(lst, 3, 1)
1 2 1
>>> newer = change(new, 1, 2)
2 2 2
2 2 2
"""
``````

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.

>>> reversed_primes = reverse_iterative(primes)
7 5 3 2
"""

def reverse_recursive(s):
"""Return a reversed version of a linked list s.

>>> reversed_primes = reverse_recursive(primes)
7 5 3 2
"""
``````

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.

>>> new = insert(lst, 9001, 1)
1 9001 2 3
>>> newer = insert(new, 9002, 15)
1 9001 2 3 9002
"""
``````

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
"""
``````

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
"""
``````

Use OK to test your code:

``python3 ok -q same_shape``

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)])])
2
4
6
8
10
12
14
16
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
"""
``````

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 a `mobile` or `weight`.
• 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

def size(w):
"""Select the size of a weight."""

def is_weight(w):
"""Whether w is a weight, not a mobile."""
``````

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
"""
``python3 ok -q balanced``