Due by 11:59pm on Friday, April 17.

Starter Files

Download lab10.zip.

WWPD with Iterators

Q1: WWPD: Iterators

Important: Enter StopIteration if a StopIteration exception occurs, Error if you believe a different error occurs, and Iterator if the output is an iterator object.

Important: Python's built-in function map, filter, and zip return iterators, not lists.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q iterators-wwpd -u
Copy
✂️

>>> s = [1, 2, 3, 4]
>>> t = iter(s)
>>> next(s)
______
Error
>>> next(t)
______
1
>>> next(t)
______
2
>>> next(iter(s))
______
1
>>> next(iter(s))
______
1
>>> u = t
>>> next(u)
______
3
>>> next(t)
______
4

>>> r = range(6)
>>> r_iter = iter(r)
>>> next(r_iter)
______
0
>>> [x + 1 for x in r]
______
[1, 2, 3, 4, 5, 6]
>>> [x + 1 for x in r_iter]
______
[2, 3, 4, 5, 6]
>>> next(r_iter)
______
StopIteration

>>> map_iter = map(lambda x : x + 10, range(5))
>>> next(map_iter)
______
10
>>> next(map_iter)
______
11
>>> list(map_iter)
______
[12, 13, 14]
>>> for e in filter(lambda x : x % 4 == 0, range(1000, 1008)):
...     print(e)
______
1000
1004
>>> [x + y for x, y in zip([1, 2, 3], [4, 5, 6])]
______
[5, 7, 9]

Required Questions

Q2: Count Occurrences

Implement count_occurrences, which takes an iterator t, an integer n, and a value x. It returns the number of elements in the first n elements of t that are equal to x.

You can assume that t has at least n elements.

Important: You should call next on t exactly n times. If you need to iterate through more than n elements, think about how you can optimize your solution.

from typing import Iterator  # "t: Iterator[int]" means t is an iterator that yields integers

def count_occurrences(t: Iterator[int], n: int, x: int) -> int:
    """Return the number of times that x is equal to one of the
    first n elements of iterator t.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(s, 10, 9)
    3
    >>> t = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> count_occurrences(t, 3, 10)
    2
    >>> u = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> count_occurrences(u, 1, 3)  # Only iterate over 3
    1
    >>> count_occurrences(u, 3, 2)  # Only iterate over 2, 2, 2
    3
    >>> list(u)                     # Ensure that the iterator has advanced the right amount
    [1, 2, 1, 4, 4, 5, 5, 5]
    >>> v = iter([4, 1, 6, 6, 7, 7, 6, 6, 2, 2, 2, 5])
    >>> count_occurrences(v, 6, 6)
    2
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q count_occurrences
Copy
✂️

Q3: Trap

Write a generator function that yields the first k values in iterable s, but raises a ValueError exception if any more values are requested. You may assume that s has at least k values.

To raise an exception, use a raise statement:

>>> def foo():
...     raise ValueError("This is an error message.")
...
>>> foo()
ValueError: This is an error message.

def trap(s, k):
    """Return a generator that yields the first K values in iterable S,
    but raises a ValueError exception if any more values are requested.

    >>> t = trap([3, 2, 1], 2)
    >>> next(t)
    3
    >>> next(t)
    2
    >>> next(t)
    Traceback (most recent call last):
        ...
    ValueError: It's a trap!
    >>> list(trap(range(5), 5))
    Traceback (most recent call last):
        ...
    ValueError: It's a trap!
    >>> t2 = trap(map(abs, reversed(range(-6, -4))), 2)
    >>> next(t2)
    5
    >>> next(t2)
    6
    >>> next(t2)
    Traceback (most recent call last):
        ...
    ValueError: It's a trap!
    >>> t3 = trap([1, 5, 6, 7, 10], 3)
    >>> next(t3)
    1
    >>> next(t3)
    5
    >>> next(t3)
    6
    >>> next(t3)
    Traceback (most recent call last):
        ...
    ValueError: It's a trap!
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q trap
Copy
✂️

Q4: Hailstone

Write a generator function that outputs the hailstone sequence starting at number n.

Here's a quick reminder of 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.

Make sure you don't create an infinite generator!

As an extra challenge, try writing a solution using recursion. Since hailstone returns a generator, you can yield from a call to hailstone!

def hailstone(n):
    """Yields the elements of the hailstone sequence starting at n.

    >>> 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
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.