Lab 10 Solutions

lab10.zip

Solution Files

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

>>> 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
    """
    count = 0
    for _ in range(n):
        if next(t) == x:
            count += 1
    return count

Use Ok to test your code:

python3 ok -q count_occurrences

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!
    """
    t = iter(s)
    for _ in range(k):
        yield next(t)
    raise ValueError("It's a trap!")

Use Ok to test your code:

python3 ok -q trap

Walkthrough:

YouTube link

Q4: Generate Permutations

Given a sequence of unique elements, a permutation of the sequence is a list containing the elements of the sequence in some arbitrary order. For example, [1, 2, 3], [2, 1, 3], [1, 3, 2], and [3, 2, 1] are some of the permutations of the sequence [1, 2, 3].

Implement perms, a generator function that takes in a sequence seq and returns a generator that yields all permutations of seq. For this question, assume that seq will not be empty.

Permutations may be yielded in any order.

Hint: Remember, it's possible to loop over generator objects because generators are iterators!

def perms(seq):
    """Generates all permutations of the given sequence. Each permutation is a
    list of the elements in SEQ in a different order. The permutations may be
    yielded in any order.

    >>> p = perms([100])
    >>> type(p)
    <class 'generator'>
    >>> next(p)
    [100]
    >>> try: # Prints "No more permutations!" if calling next would cause an error
    ...     next(p)
    ... except StopIteration:
    ...     print('No more permutations!')
    No more permutations!
    >>> sorted(perms([1, 2, 3])) # Returns a sorted list containing elements of the generator
    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
    >>> sorted(perms((10, 20, 30)))
    [[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
    >>> sorted(perms("ab"))
    [['a', 'b'], ['b', 'a']]
    """
    if not seq:
        yield []
    else:
        for p in perms(seq[1:]):
            for i in range(len(seq)):
                yield p[:i] + [seq[0]] + p[i:]

Use Ok to test your code:

python3 ok -q perms

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.