# Diagnostic 5: Week 5 review

## Mutable Linked Lists

### Question 1: Slice

Implement a function `slice_link`

that slices a given `link`

. `slice_link`

should slice the `link`

starting at `start`

and ending one element before
`end`

, as with a normal Python list.

```
def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).
>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> new = slice_link(link, 1, 4)
>>> print_link(new)
<1 4 1>
"""
"*** YOUR CODE HERE ***"
if end == 0:
return Link.empty
elif start == 0:
return Link(link.first, slice_link(link.rest, 0, end-1))
else:
return slice_link(link.rest, start-1, end-1)
```

Note: This was an extra question in Lab 9.

### Question 2: Add Links

Let's implement a method in order to add together items of `link1`

and `link2`

.
Do not assume that the links are the same length.

```
def add_links(link1, link2):
"""Adds two Links, returning a new Link
>>> l1 = Link(1, Link(2))
>>> l2 = Link(3, Link(4, Link(5)))
>>> new = add_links(l1,l2)
>>> print_link(new)
<1 2 3 4 5>
"""
"*** YOUR CODE HERE ***"
if link1 is not Link.empty:
return Link(link1.first, add_links(link1.rest, link2))
elif link2 is not Link.empty:
return Link(link2.first, add_links(link1, link2.rest))
else:
return Link.empty
# Iterative version (using reverse)
def add_links(link1, link2):
result = Link.empty
while link1 is not Link.empty:
result = Link(link1.first, result)
link1 = link1.rest
while link2 is not Link.empty:
result = Link(link2.first, result)
link2 = link2.rest
return reverse(result)
```

Note: This was an extra question in Lab 9.

Implement `mutate_reverse`

, a recursive mutating version of `reverse`

. Have it
mutate the original `Link`

so that its elements are reversed.

```
def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.
>>> link = Link(1)
>>> mutate_reverse(link)
>>> link
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> mutate_reverse(link)
>>> link
Link(3, Link(2, Link(1)))
"""
"*** YOUR CODE HERE ***"
if link is Link.empty or link.rest is Link.empty:
return
mutate_reverse(link.rest)
while link.rest is not Link.empty:
link.first, link.rest.first = link.rest.first, link.first
link = link.rest
# O(n) solution
def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.
>>> link = Link(1)
>>> mutate_reverse(link)
>>> link
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> mutate_reverse(link)
>>> link
Link(3, Link(2, Link(1)))
"""
reverse_helper(link)
def reverse_helper(link):
if link.rest is not Link.empty:
second, last = link.rest, link
link = reverse_helper(second)
second.rest, last.rest = last, link.empty
return link
```

## Mutable Trees

### Question 3: Cumulative sum

Write a function `cumulative_sum`

that returns a new `Tree`

, where each entry is the sum of all entries in the corresponding subtree of the old `Tree`

.

```
def cumulative_sum(t):
"""Return a new Tree, where each entry is the sum of all entries in the
corresponding subtree of t.
>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative = cumulative_sum(t)
>>> t
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
>>> cumulative_sum(Tree(1))
Tree(1)
"""
"*** YOUR CODE HERE ***"
subtrees = [cumulative_sum(st) for st in t.subtrees]
new_entry = sum(st.entry for st in subtrees) + t.entry
return Tree(new_entry, subtrees)
```

### Question 4: Leaves

Write a function `leaves`

that returns a list of all the entries of the leaf
nodes of a `Tree`

.

```
def leaves(t):
"""Returns a list of all the entries of the leaf nodes of the Tree t.
>>> leaves(Tree(1))
[1]
>>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
[3, 4]
"""
"*** YOUR CODE HERE ***"
if t.is_leaf():
return [t.entry]
all_leaves = []
for b in t.subtrees:
all_leaves += leaves(b)
return all_leaves
```

## Binary Trees and Binary Search Trees

### Question 5: Size

Define the function `size`

which takes in a `BinaryTree`

as an argument and
returns the number of entries in the tree.

```
def size(b):
r""" Return the number of entries in the binary tree b.
>>> b = BinaryTree(4,
... BinaryTree(2,
... BinaryTree(1)),
... BinaryTree(6,
... BinaryTree(5)))
>>> size(b)
5
"""
"*** YOUR CODE HERE ***"
if b is BinaryTree.empty:
return 0
return 1 + size(tree.left) + size(tree.right)
```

### Question 6: Max

Define the function `bst_max`

which takes in a binary search tree and returns
the max of all of the values of each node in the tree. Be sure to take
advantage of the properties of the binary search tree to get an efficient
solution.

You may assume the input is a non-empty `BinaryTree`

.

```
def bst_max(b):
r""" Returns the max of all the values of each node in b.
Calling bst_max on the following tree should return 6:
4
/ \
2 6
/ /
1 5
>>> b = BinaryTree(4,
... BinaryTree(2,
... BinaryTree(1)),
... BinaryTree(6,
... BinaryTree(5)))
>>> bst_max(t)
6
"""
"*** YOUR CODE HERE ***"
if b.right is BinaryTree.empty:
return b.entry
return bst_max(b.right)
```

### Question 7: Min

Define the function `bst_min`

which takes in a binary search tree and returns
the min of all of the values of each node in the tree. Be sure to take
advantage of the properties of the binary search tree to get an efficient
solution.

You may assume the input is a non-empty `BinaryTree`

.

```
def bst_min(b):
r""" Returns the min of all the values of each node in b.
Calling bst_min on the following tree should return 1:
4
/ \
2 6
/ /
1 5
>>> b = BinaryTree(4,
... BinaryTree(2,
... BinaryTree(1)),
... BinaryTree(6,
... BinaryTree(5)))
>>> bst_min(t)
1
"""
"*** YOUR CODE HERE ***"
if b.left is BinaryTree.empty:
return b.entry
return bst_min(b.left)
```

## Interfaces

For the following interface questions, you'll be implementing magic methods for
the following `Rational`

class, which represents a rational number. A rational
number consists of a numerator and a denominator, both of which are integers.

```
from fractions import gcd
class Rational:
def __init__(self, numer, denom):
factor = gcd(numer, denom)
self.numer = numer // factor
self.denom = denom // factor
```

### Question 8: Repr

Implement the `__repr__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __repr__(self):
"""
>>> r = Rational(4, 6)
>>> r
Rational(2, 3)
>>> repr(r)
'Rational(2, 3)'
"""
"*** YOUR CODE HERE ***"
return 'Rational({0}, {1})'.format(self.numer, self.denom)
```

### Question 9: Str

Implement the `__str__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __str__(self):
"""
>>> r = Rational(4, 6)
>>> print(r)
2 / 3
>>> str(r)
'2 / 3'
"""
"*** YOUR CODE HERE ***"
return '{0} / {1}'.format(self.numer, self.denom)
```

### Question 10: Add

Implement the `__add__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __add__(self, other):
"""
>>> r1 = Rational(2, 3)
>>> r2 = Rational(4, 5)
>>> r1 + r2
Rational(22, 15)
>>> r1 + 6
Rational(20, 3)
"""
"*** YOUR CODE HERE ***"
if isinstance(other, Rational):
return Rational(self.numer * other.denom + self.denom * other.numer,
self.denom * other.denom)
elif isinstance(other, int):
return Rational(self.numer + self.denom * other, self.denom)
```

### Question 11: Neg

Implement the `__neg__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __neg__(self):
"""
>>> r = Rational(2, 3)
>>> -r
Rational(-2, 3)
"""
"*** YOUR CODE HERE ***"
return Rational(-self.numer, self.denom)
```

### Question 12: Sub

Implement the `__sub__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __sub__(self, other):
"""
>>> r1 = Rational(2, 3)
>>> r2 = Rational(4, 5)
>>> r1 - r2
Rational(-2, 15)
>>> r1 - 1
Rational(-1, 3)
"""
"*** YOUR CODE HERE ***"
return self + (-other)
```

### Question 13: Mul

Implement the `__mul__`

method for the `Rational`

class. See the
doctests for expected behavior.

```
def __mul__(self, other):
"""
>>> r1 = Rational(2, 3)
>>> r2 = Rational(9, 5)
>>> r1 * r2
Rational(6, 5)
>>> r1 * 5
Rational(10, 3)
"""
"*** YOUR CODE HERE ***"
if isinstance(other, Rational):
return Rational(self.numer * other.numer, self.denom * other.denom)
elif isinstance(other, int):
return Rational(self.numer * other, self.denom)
```

## Iterators and Generators

### Question 14: Does it work?

Consider the following iterators. Which ones work and which ones don't? Why?

```
class IteratorA:
def __init__(self):
self.start = 5
def __next__(self):
if self.start == 100:
raise StopIteration
self.start += 5
return self.start
def __iter__(self):
return self
```

No problem, this is a beautiful iterator.

```
class IteratorB:
def __init__(self):
self.start = 5
def __iter__(self):
return self
```

Oh no! Where is `__next__`

? This fails to implement the iterator
interface because calling `__iter__`

doesn't return something that has
a `__next__`

method.

```
class IteratorC:
def __init__(self):
self.start = 5
def __next__(self):
if self.start == 10:
raise StopIteration
self.start += 1
return self.start
```

This also fails to implement the iterator interface. Without the
`__iter__`

method, the `for`

loop will error. The `for`

loop needs to
call `__iter__`

first because some objects might not implement the
`__next__`

method themselves, but calling `__iter__`

will return an
object that does.

```
class IteratorD:
def __init__(self):
self.start = 1
def __next__(self):
self.start += 1
return self.start
def __iter__(self):
return self
```

This is technically an iterator, because it implements both `__iter__`

and
`__next__`

. Notice that it's an infinite sequence! Sequences like these are
the reason iterators are useful. Because iterators delay computation, we can
use a finite amount of memory to represent an infinitely long sequence.

### Question 15: Str

Write an iterator that takes a string as input:

```
class Str:
def __init__(self, str):
self.str = str
def __iter__(self):
return self.str.__iter__()
```

That works (why?), but just kidding.

```
class Str:
"""
>>> s = Str("hello")
>>> for char in s:
... print(char)
...
h
e
l
l
o
"""
def __init__(self, str):
"*** YOUR CODE HERE ***"
self.str = str
self.i = -1
def __iter__(self):
"*** YOUR CODE HERE ***"
return self
def __next__(self):
self.i += 1
if self.i >= len(self.str):
raise StopIteration
return self.str[self.i]
```

### Question 16: Countdown

Write a generator that counts down to 0.

Write it in both ways: using a generator function on its own, and
within the `__iter__`

method of a class.

```
def countdown(n):
"""
>>> for number in countdown(5):
... print(number)
...
5
4
3
2
1
0
"""
"*** YOUR CODE HERE ***"
while n >= 0:
yield n
n = n - 1
```

```
class Countdown:
"""
>>> for number in Countdown(5):
... print(number)
...
5
4
3
2
1
0
"""
"*** YOUR CODE HERE ***"
def __init__(self, cur):
self.cur = cur
def __iter__(self):
return self
def __next__(self):
result = self.cur
if result < 0:
raise StopIteration
self.cur -= 1
return result
# Alternate solution that makes __iter__ a generator function:
class Countdown:
def __init__(self, cur):
self.cur = cur
def __iter__(self):
while self.cur >= 0:
yield self.cur
self.cur -= 1
```

### Question 17: Hailstone

Write a generator that outputs the hailstone sequence from homework 1.

```
def hailstone(n):
"""
>>> for num in hailstone(10):
... print(num)
...
10
5
16
8
4
2
1
"""
"*** YOUR CODE HERE ***"
i = n
while i > 1:
yield i
if i % 2 == 0:
i //= 2
else:
i = i * 3 + 1
yield i
```

### Question 18: Pairs (generator)

Write a generator function `pairs`

that takes a list and yields all the
possible pairs of elements from that list.

Note that this means that you should be yielding a *tuple*.

```
def pairs(lst):
"""
>>> type(pairs([3, 4, 5]))
<class 'generator'>
>>> for x, y in pairs([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
"*** YOUR CODE HERE ***"
for i in lst:
for j in lst:
yield i, j
```

### Question 19: Pairs (iterator)

Now write an iterator that does the same thing. You are only allowed to use a linear amount of space - so computing a list of all of the possible pairs is not a valid answer. Notice how much harder it is - this is why generators are useful.

```
class PairsIterator:
"""
>>> for x, y in PairsIterator([3, 4, 5]):
... print(x, y)
...
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
"""
def __init__(self, lst):
"*** YOUR CODE HERE ***"
self.lst = lst
self.i = 0
self.j = 0
def __next__(self):
"*** YOUR CODE HERE ***"
if self.i == len(self.lst):
raise StopIteration
result = (self.lst[self.i], self.lst[self.j])
if self.j == len(self.lst) - 1:
self.i += 1
self.j = 0
else:
self.j += 1
return result
def __iter__(self):
"*** YOUR CODE HERE ***"
return self
```