Homework 10
Due at 11:59:59 pm on Thursday, 4/18/2024.

Instructions

Download hw10.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Readings: This homework relies on following references:

• Section 4.2

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):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        return self

    def __next__(self):
        "*** YOUR CODE HERE ***"

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):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"

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
    """
    "*** YOUR CODE HERE ***"

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
    """
    "*** YOUR CODE HERE ***"

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):
        "*** YOUR CODE HERE ***"

    def __next__(self):
        "*** YOUR CODE HERE ***"

    def __iter__(self):
        "*** YOUR CODE HERE ***"

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)
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q merge

Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

• hw10.py