# 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 theoriginallinked 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 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
"*** 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`