Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

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

<1 4 1>
"""
if end == 0:
elif start == 0:
else:

Note: This was an extra question in Lab 9.

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):

<1 2 3 4 5>
"""
else:

# Iterative version (using reverse)
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.

"""
return

# O(n) solution
"""Mutates the Link so that its elements are reversed.

"""

## 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)
"""
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]
"""
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
"""
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
"""
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
"""
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)'
"""
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'
"""
return '{0} / {1}'.format(self.numer, self.denom)``````

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)
"""
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)
"""
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)
"""
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)
"""
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):
self.str = str
self.i = -1
def __iter__(self):
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
"""
while n >= 0:
yield n
n = n - 1``````
``````class Countdown:
"""
>>> for number in Countdown(5):
...     print(number)
...
5
4
3
2
1
0
"""
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
"""
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
"""
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):
self.lst = lst
self.i = 0
self.j = 0
def __next__(self):