# Homework 7 Solutions

## Solution Files

You can find the solutions in hw07.py.

# Required Questions

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

## Linked Lists

### Q1: Store Digits

Write a function `store_digits`

that takes in an integer `n`

and returns
a linked list where each element of the list is a digit of `n`

.

Important: Do not use any string manipulation functions like`str`

and`reversed`

.

```
def store_digits(n):
"""Stores the digits of a positive number n in a linked list.
>>> s = store_digits(1)
>>> s
Link(1)
>>> store_digits(2345)
Link(2, Link(3, Link(4, Link(5))))
>>> store_digits(876)
Link(8, Link(7, Link(6)))
>>> store_digits(2450)
Link(2, Link(4, Link(5, Link(0))))
>>> # a check for restricted functions
>>> import inspect, re
>>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
>>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
"""
result = Link.empty
while n > 0:
result = Link(n % 10, result)
n //= 10
return result
```

Use Ok to test your code:

`python3 ok -q store_digits`

### Q2: Mutable Mapping

Implement `deep_map_mut(func, link)`

, which applies a function `func`

onto
all elements in the given linked list `lnk`

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

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`

Construct Check: The last doctest of this question ensures that you do not create new linked lists. If you are failing this doctest, ensure that you are not creating link lists by calling the constructor, i.e.`s = Link(1)`

```
def deep_map_mut(func, lnk):
"""Mutates a deep link lnk by replacing each item found with the
result of calling func 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))))
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
>>> try:
... deep_map_mut(lambda x: x * x, link1)
... finally:
... Link.__init__ = hold
>>> print(link1)
<9 <16> 25 36>
"""
if lnk is Link.empty:
return
elif isinstance(lnk.first, Link):
deep_map_mut(func, lnk.first)
else:
lnk.first = func(lnk.first)
deep_map_mut(func, lnk.rest)
```

Use Ok to test your code:

`python3 ok -q deep_map_mut`

### Q3: 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(vals, counts):
"""
Returns a linked list according to the two lists that were passed in. Assume
vals and counts are the same size. Elements in vals represent the value, and the
corresponding element in counts represents the number of this value desired in the
final linked list. Assume all elements in counts are greater than 0. Assume both
lists have at least one element.
>>> a = [1, 3]
>>> b = [1, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(3))
>>> a = [1, 3, 2]
>>> b = [2, 2, 1]
>>> c = two_list(a, b)
>>> c
Link(1, Link(1, Link(3, Link(3, Link(2)))))
"""
def helper(count, index):
if count == 0:
if index + 1 == len(vals):
return Link.empty
return Link(vals[index + 1], helper(counts[index + 1] - 1, index + 1))
return Link(vals[index], helper(count - 1, index))
return helper(counts[0], 0)
#Iterative solution
def two_list_iterative(vals, counts):
result = Link(None)
p = result
for index in range(len(vals)):
item = vals[index]
for _ in range(counts[index]):
p.rest = Link(item)
p = p.rest
return result.rest
```

Use Ok to test your code:

`python3 ok -q two_list`

## Mutable Trees

### Q4: Add Leaves

Implement `add_d_leaves`

, a function that takes in a `Tree`

instance `t`

and a number `v`

.

We define the depth of a node in `t`

to be the number of edges from the root to that node. The depth of root is therefore 0.

For each node in the tree, you should add `d`

leaves to it, where `d`

is the depth of the node. Every added leaf should have a label of `v`

. If the node at this depth has existing branches, you should add these leaves to the end of that list of branches.

For example, you should be adding 1 leaf with label `v`

to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Here is an example of a tree `t`

(shown on the left) and the result after `add_d_leaves`

is applied with `v`

as 5.

Try drawing out the second doctest to visualize how the function is mutating

`t3`

.

Hint:Use a helper function to keep track of the depth!

```
def add_d_leaves(t, v):
"""Add d leaves containing v to each node at every depth d.
>>> t_one_to_four = Tree(1, [Tree(2), Tree(3, [Tree(4)])])
>>> print(t_one_to_four)
1
2
3
4
>>> add_d_leaves(t_one_to_four, 5)
>>> print(t_one_to_four)
1
2
5
3
4
5
5
5
>>> t1 = Tree(1, [Tree(3)])
>>> add_d_leaves(t1, 4)
>>> t1
Tree(1, [Tree(3, [Tree(4)])])
>>> t2 = Tree(2, [Tree(5), Tree(6)])
>>> t3 = Tree(3, [t1, Tree(0), t2])
>>> print(t3)
3
1
3
4
0
2
5
6
>>> add_d_leaves(t3, 10)
>>> print(t3)
3
1
3
4
10
10
10
10
10
10
0
10
2
5
10
10
6
10
10
10
"""
def add_leaves(t, d):
for b in t.branches:
add_leaves(b, d + 1)
t.branches.extend([Tree(v) for _ in range(d)])
add_leaves(t, 0)
```

Use Ok to test your code:

`python3 ok -q add_d_leaves`

## Submit

Make sure to submit this assignment by uploading any files you've edited **to the appropriate Gradescope assignment.** For a refresher on how to do this, refer to Lab 00.

# Exam Practice

Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!

Linked Lists

- Fall 2020 Final Q3: College Party
- Fall 2018 MT2 Q6: Dr. Frankenlink
- Spring 2017 MT1 Q5: Insert

Mutable Trees