Homework 10 Solutions

hw10.py solution

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:

  1. Pick a positive integer n as the start.
  2. If n is even, divide it by 2.
  3. If n is odd, multiply it by 3 and add 1.
  4. 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