# Homework 7

*Due by 11:59pm on Monday, 7/24*

## Instructions

Download hw07.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.

# Homework Questions

## Linked Lists

### Question 1: Every Other

Implement `every_other`

, which takes a linked list `s`

. It mutates `s`

such
that all of the odd-indexed elements (using 0-based indexing) are removed from
the list. For example:

```
>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
>>> s.rest.rest is Link.empty
True
```

If `s`

contains fewer than two elements, `s`

remains unchanged.

Do not return anything!

`every_other`

should mutate the original list.

```
def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q every_other`

### Question 2: Mutable Mapping

Implement `deep_map_mut(fn, link)`

, which applies a function `fn`

onto
all elements in the given linked list `link`

. If an element is itself a
linked list, apply `fn`

to each of its elements, and so on.

Your implementation should mutate the original linked list. Do not create any new linked lists.

Hint: The built-in`isinstance`

function may be useful.`>>> s = Link(1, Link(2, Link(3, Link(4)))) >>> isinstance(s, Link) True >>> isinstance(s, int) False`

```
def deep_map_mut(fn, link):
"""Mutates a deep link by replacing each item found with the
result of calling fn on the item. Does NOT create new Links (so
no use of Link's constructor)
Does not return the modified Link object.
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> deep_map_mut(lambda x: x * x, link1)
>>> print_link(link1)
<9 <16> 25 36>
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q deep_map_mut`

### Question 3: Two List

Implement a function `two_list`

that takes in two lists and returns a linked list. The first list contains the
values that we want to put in the linked list, and the second list contains the number of each corresponding value.
Assume both lists are the same size and have a length of 1 or greater. Assume all elements in the second list
are greater than 0.

```
def two_list(lst1, lst2):
"""
Returns a linked list according to the two lists that were passed in. Assume
lst1 and lst2 are the same size. Elements in lst1 represent the value, and the
corresponding element in lst2 represents the number of this value is desired in the
final linked list. Assume all elements in lst2 are greater than 0. Assume both
lists have at least one element.
>>> a = [1, 3, 2]
>>> b = [1, 1, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(3, Link(2)))
>>> a = [1, 3, 2]
>>> b = [2, 2, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(1, Link(3, Link(3, Link(2)))))
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q two_list`

### Question 4: Cycles

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.rest.rest.rest.rest.rest.first
3
```

Implement `has_cycle`

,that returns whether its argument, a `Link`

instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which`Link`

objects you've already seen.

```
def has_cycle(link):
"""Return whether link 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
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q has_cycle`

**Extra question**: *This question is not worth extra credit and is entirely
optional. It is designed to challenge you to think creatively!*

Implement `has_cycle_constant`

with only constant space. (If you followed
the hint above, you will use linear 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_constant(link):
"""Return whether link 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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q has_cycle_constant`

## Trees

### Question 5: Cumulative Sum

Write a function `cumulative_sum`

that mutates the Tree `t`

, where each node's
root becomes the sum of all entries in the subtree rooted at the node.

```
def cumulative_sum(t):
"""Mutates t where each node's root becomes the sum of all entries in the
corresponding subtree rooted at t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative_sum(t)
>>> t
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q cumulative_sum`

### Question 6: Prune Min

Write a function that prunes a tree t mutatively. Tree t and its branches always have zero branches or two branches. For the trees with two branches, reduce the number of branches from two to one by keeping the branch that has the smaller root value. Do nothing with trees with zero branches. Prune the tree from the bottom up. The result should be a linear tree.

```
def prune_min(t):
"""Prune the tree mutatively from the bottom up. Assume the tree and its branches always have either two branches or none. Prune the tree by
reducing the number of branches from two to one, choosing the branch with the smaller root value. Assume branches have differing root values.
Do nothing with trees with zero branches.
>>> t1 = Tree(6)
>>> prune_min(t1)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_min(t2)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(3, [Tree(1), Tree(2)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_min(t3)
>>> t3
Tree(6, [Tree(3, [Tree(1)])])
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q prune_min`

### Question 7: Long Paths

Implement `long_paths`

, which returns a list of all *paths* in a tree with
length at least `n`

. A path in a tree is a linked list of node values that
starts with the root and ends at a leaf. Each subsequent element must be from a
child of the previous value's node. The *length* of a path is the number of
edges in the path (i.e. one less than the number of nodes in the path).
Paths are listed in order from left to right.

```
def long_paths(tree, n):
"""Return a list all paths in tree with length at least n.
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12)])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
... print(path)
...
Link(0, Link(1, Link(2)))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
Link(0, Link(6, Link(9)))
Link(0, Link(11, Link(12)))
>>> for path in long_paths(whole, 3):
... print(path)
...
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
>>> long_paths(whole, 4)
[]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q long_paths`