# Homework 10 Solutions

## Iterator/Generator Questions

### Question 1: Scale

Implement an iterator class called `ScaleIterator`

that scales elements in an iterable `iterable`

by a number `scale`

. The elements are **not** scaled on initialization, they are scaled when they are retrieved from the iterator (by calling `next`

).

For testing, we are using the `naturals()`

generator, which is an infinite generator of the natural numbers (all positive integers, which does not include 0). The implementation of this generator can be found at the bottom of the starter code file.

```
class ScaleIterator:
"""An iterator the scales elements of the iterable by a number scale.
>>> s = ScaleIterator([1, 5, 2], 5)
>>> list(s)
[5, 25, 10]
>>> m = ScaleIterator(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
def __init__(self, iterable, scale):
self.iterable = iter(iterable)
self.scale = scale
def __iter__(self):
return self
def __next__(self):
return next(self.iterable) * self.scale
```

Use OK to test your code:

`python3 ok -q ScaleIterator`

### Question 2: Restart

Implement an iterator class called `IteratorRestart`

that will reset to the beginning when `__iter__`

is called again. Normally, calling `__iter__`

will simply continue from the last element that was iterated on, however you should implement this class such that it starts over from the very beginning.

In the provided doctest, we initialize an `IteratorRestart`

object that will iterate from ints 2 to 7. Every time a for loop is used, python implicitly calls `__iter__`

automatically on the object you are iterating through.

We iterate through all of the numbers in our IteratorRestart object, and then in the second for loop when `__iter__`

is called again, it resets the object. Thus, when we iterate again, it starts from the beginning.

```
class IteratorRestart:
"""
>>> iterator = IteratorRestart(2, 7)
>>> for num in iterator:
... print(num)
2
3
4
5
6
7
>>> for num in iterator:
... print(num)
2
3
4
5
6
7
"""
def __init__(self, start, end):
self.start = start
self.end = end
self.current = start
def __next__(self):
if self.current > self.end:
raise StopIteration
self.current += 1
return self.current - 1
def __iter__(self):
self.current = self.start
return self
```

Use OK to test your code:

`python3 ok -q IteratorRestart`

### Question 3: Hailstone

Write a generator that outputs the hailstone sequence from Lab 01.

Here's a quick refresher on how the hailstone sequence is defined:

- Pick a positive integer
`n`

as the start. - If
`n`

is even, divide it by 2. - If
`n`

is odd, multiply it by 3 and add 1. - Continue this process until
`n`

is 1.

```
def hailstone(n):
"""
>>> hs = hailstone(10)
>>> type(hs)
<class 'generator'>
>>> for num in hailstone(10):
... print(num)
...
10
5
16
8
4
2
1
"""
while n > 1:
yield n
if n % 2 == 0:
n //= 2
else:
n = n * 3 + 1
yield n
```

Use OK to test your code:

`python3 ok -q hailstone`

### Question 4: 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
```

Use OK to test your code:

`python3 ok -q pairs`

### Question 5: 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):
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):
return self
```

Use OK to test your code:

`python3 ok -q PairsIterator`

### Question 6: Merge

Implement `merge(r0, r1)`

, which takes two iterables `r0`

and `r1`

whose
elements are ordered. `merge`

yields elements from `r0`

and `r1`

in sorted
order, eliminating repetition. **You may also assume r0 and r1 represent infinite
sequences; that is, their iterators never raise StopIteration**.

See the doctests for example behavior. For testing, we are using the `naturals()`

generator, which is an infinite generator of the natural numbers (all positive integers, which does not include 0). The implementation of this generator can be found at the bottom of the starter code file.

```
def merge(r0, r1):
"""Yield the elements of strictly increasing iterables r0 and r1 and
make sure to remove the repeated values in both.
You can also assume that r0 and r1 represent infinite sequences.
>>> twos = naturals(initial = 2, step = 2)
>>> threes = naturals(initial = 3, step = 3)
>>> m = merge(twos, threes)
>>> type(m)
<class 'generator'>
>>> [next(m) for _ in range(10)]
[2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0 = iter(r0)
i1 = iter(r1)
e0 = next(i0)
e1 = next(i1)
while True:
yield min(e0, e1)
if e0 < e1:
e0 = next(i0)
elif e1 < e0:
e1 = next(i1)
else:
e0, e1 = next(i0), next(i1)
```

Use OK to test your code:

`python3 ok -q merge`