hw13.py (plain text)


"""CS 61A HW 13
Name:
Login:
TA:
Section:
"""


from stream import *


#### Core Questions
#### Q1
def scale_stream(s, k):
    """Return a stream over the elements of s scaled by k.

    >>> s = scale_stream(integers_starting_from(3), 5)
    >>> s.first
    15
    >>> print(s.rest)
    Stream(20, <compute_rest>)
    >>> scale_stream(s.rest, 10).rest.rest.first
    300
    """
    "*** YOUR CODE HERE ***"


#### Q2
def uniq(s):
    """A stream consisting of the unique items in S (that is, with all but
    the first occurrence of any value removed from S.

    >>> show_stream(uniq(convert_to_stream([1, 2, 2, 1, 0, 4, 2, 3, 1, 9, 0])))
    '1, 2, 0, 4, 3, 9'
    """
    "*** YOUR CODE HERE ***"
    

#### Q3
class IterableStream(Stream):
    """A lazily computed recursive list which is iterable."""
    def __repr__(self):
        if self.empty:
            return '<empty stream>'
        return 'IterableStream({0}, <compute_rest>)'.format(repr(self.first))

    def __iter__(self):
        """Return an iterator (specifically a generator) to iterate over the
        items in a stream.

        >>> s = IterableStream(1,
        ...            lambda: IterableStream(2,
        ...                           lambda: IterableStream(3,
        ...                                          lambda: IterableStream.the_empty_stream))) 
        ... 
        >>> for item in s:
        ...     print(item)
        ... 
        1
        2
        3
        """
        "*** YOUR CODE HERE ***"


#### Reinforcement Questions
#### Q4
def make_stream_of_streams():
    """
    >>> stream_of_streams = make_stream_of_streams()
    >>> stream_of_streams
    Stream(Stream(1, <compute_rest>), <compute_rest>)
    >>> stream_of_streams.first
    Stream(1, <compute_rest>)
    >>> stream_of_streams.rest.rest.rest.first
    Stream(4, <compute_rest>)
    >>> stream_of_streams.rest.first.rest.first
    3
    >>> show_stream(stream_of_streams, count=3)
    "'1, 2, 3, ...', '2, 3, 4, ...', '3, 4, 5, ...', ..."
    """
    "*** YOUR CODE HERE ***"


#### Q5
def make_generators_generator(g):
    """Generates all the "sub"-generators of the generator returned by the
    generator function g.

    >>> def ints_to(n):
    ...     for i in range(1, n + 1):
    ...          yield i
    ... 
    >>> def ints_to_5():
    ...     for item in ints_to(5):
    ...         yield item
    ... 
    >>> for gen in make_generators_generator(ints_to_5):
    ...     print("Next Generator:")
    ...     for item in gen:
    ...         print(item)
    ... 
    Next Generator:
    1
    Next Generator:
    1
    2
    Next Generator:
    1
    2
    3
    Next Generator:
    1
    2
    3
    4
    Next Generator:
    1
    2
    3
    4
    5
    """
    "*** YOUR CODE HERE ***"


#### Q6
def decimal_rep(num, denom):
    """
    >>> one_third = decimal_rep(1, 3)
    >>> show_stream(one_third)
    '0, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...'
    >>> ten_thirds = decimal_rep(10, 3)
    >>> show_stream(ten_thirds)
    '3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...'
    >>> one_half = decimal_rep(1, 2)
    >>> show_stream(one_half)
    '0, 5, 0, 0, 0, 0, 0, 0, 0, 0, ...'
    """
    "*** YOUR CODE HERE ***"


#### Q7
def merge(s0, s1):
    """Return a stream over the elements of s0 and s1, removing repeats.  It is
    assumed that s0 and s1 are streams of increasing numbers.

    >>> ints = integers_starting_from(1)
    >>> twos = scale_stream(ints, 2)
    >>> threes = scale_stream(ints, 3)
    >>> m = merge(twos, threes)
    >>> show_stream(m)
    '2, 3, 4, 6, 8, 9, 10, 12, 14, 15, ...'
    """
    if s0.empty:
        return s1
    if s1.empty:
        return s0
    e0, e1 = s0.first, s1.first
    if e0 < e1:
        return Stream(e0, lambda: merge(s0.rest, s1))
    elif e1 < e0:
        return Stream(e1, lambda: merge(s0, s1.rest))
    else:
        "*** YOUR CODE HERE ***"


def make_s():
    """Return a stream over all positive integers with only factors 2, 3, & 5.

    >>> s = make_s()
    >>> show_stream(s, 15)
    '1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ...'
    """
    def rest():
        "*** YOUR CODE HERE ***"
    s = Stream(1, rest)
    return s


#### Q8
def rle(strm, max_run_length=10):
    """
    >>> example_stream = convert_to_stream([1, 1, 1, 2, 3, 3])
    >>> show_stream(example_stream)
    '1, 1, 1, 2, 3, 3'
    >>> encoded_example = rle(example_stream)
    >>> show_stream(encoded_example)
    '(3, 1), (1, 2), (2, 3)'
    >>> shorter_encoded_example = rle(example_stream, 2)
    >>> show_stream(shorter_encoded_example)
    '(2, 1), (1, 1), (1, 2), (2, 3)'
    
    >>> ones = make_ones()
    >>> encoded_ones = rle(ones)
    >>> show_stream(encoded_ones, 3)
    '(10, 1), (10, 1), (10, 1), ...'
    >>> shorter_encoded_ones = rle(ones, 3)
    >>> show_stream(shorter_encoded_ones, 3)
    '(3, 1), (3, 1), (3, 1), ...'
    
    >>> naturals = integers_starting_from(1)
    >>> encoded_naturals = rle(naturals)
    >>> show_stream(encoded_naturals, 3)
    '(1, 1), (1, 2), (1, 3), ...'
    """
    "*** YOUR CODE HERE ***"


#### Extra for Experts
#### Q9
def make_deep_infinite_stream(n):
    """
    >>> show_stream(make_deep_infinite_stream(1))
    '1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...'
    >>> show_stream(make_deep_infinite_stream(2), 3)
    "'1, 2, 3, ...', '2, 3, 4, ...', '3, 4, 5, ...', ..."
    >>> show_stream(make_deep_infinite_stream(3), 2)
    "''1, 2, ...', '2, 3, ...', ...', ''2, 3, ...', '3, 4, ...', ...', ..."
    """
    "*** YOUR CODE HERE ***"