"""Submission for CS61A Homework 13.

Name:
Login:
Collaborators:
"""

class Stream(object):
    """A lazily computed recursive list."""

    def __init__(self, first, compute_rest, empty=False):
        self.first = first
        self._compute_rest = compute_rest
        self.empty = empty
        self._rest = None
        self._computed = False

    @property
    def rest(self):
        assert not self.empty, 'Empty streams have no rest.'
        if not self._computed:
            self._rest = self._compute_rest()
            self._computed = True
        return self._rest

    def prepend(self, x):
        """The stream resulting from prepending X in front of SELF."""
        r = Stream(x, None)
        r._rest = self
        r._computed = True
        return r

    def __str__(self):
        if self.empty:
            return '<empty stream>'
        return '[{0}, ...]'.format(self.first)

    def __iter__(self):
        """Return an iterator over the elements in the stream.

        >>> s1 = make_integer_stream(1) # [1, 2, 3, 4, 5, ...]
        >>> i = iter(s1)
        >>> next(i)
        1
        >>> next(i)
        2
        >>> next(i)
        3
        """
        # Q1.
        "*** YOUR CODE HERE ***"

    def __getitem__(self, k):
        """Return the k-th element of the stream.

        >>> s = make_integer_stream(5)
        >>> s[0]
        5
        >>> s[1]
        6
        >>> [s[i] for i in range(7,10)]
        [12, 13, 14]
        """
        # Q1.
        "*** YOUR CODE HERE ***"

def make_integer_stream(first=1):
    """Return an infinite stream of increasing integers."""
    def compute_rest():
        return make_integer_stream(first+1)
    return Stream(first, compute_rest)

def map_stream(fn, s):
    """Return a stream of the values of fn applied to the elements of stream s.

    >>> s = make_integer_stream(3)
    >>> ms = map_stream(lambda x: x*x, s)
    >>> [ ms[i] for i in range(4) ]
    [9, 16, 25, 36]
    """
    if s.empty:
        return s
    def compute_rest():
        return map_stream(fn, s.rest)
    return Stream(fn(s.first), compute_rest)



# Q2.

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

    >>> s = scale_stream(make_integer_stream(3), 5)
    >>> s.first
    15
    >>> print(s.rest)
    [20, ...]
    >>> scale_stream(s.rest, 10)[2]
    300
    """
    "*** YOUR CODE HERE ***"


# Q3.

def merge(s0, s1):
    """Return a stream over the elements of s0 and s1, removing repeats.

    >>> ints = make_integer_stream(1)
    >>> twos = scale_stream(ints, 2)
    >>> threes = scale_stream(ints, 3)
    >>> m = merge(twos, threes)
    >>> [m[i] for i in range(10)]
    [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()
    >>> [s[i] for i in range(20)]
    [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36]
    """
    def rest():
        "*** YOUR CODE HERE ***"
    s = Stream(1, rest)
    return s

# Q6.

def unabbrev(w, V):
    """The shortest word, u, in V such that w can be formed from u by
    removing characters.  Returns w itself if there is no such u or if there
    is more than one shortest.
    >>> V = {' arrived', 'truly', 'tally', 'shipment', 'has', 'yours',
    ...      'your', 'our', 'congratulations' }
    >>> unabbrev('pmt', V)
    'shipment'
    >>> unabbrev('tllrr', V)
    'tllrr'
    >>> unabbrev('tly', V)
    'tly'
    """
    "*** YOUR CODE HERE ***"

# Q7. Extra for experts.

def abbrev(w, V):
    """A shortest word, a, such that unabbrev(a, V) == w.  Assumes that
    w in V.  In the example, below, for example, a might be 'c'.
    >>> V = {' arrived', 'truly', 'tally', 'shipment', 'has', 'yours',
    ...      'your', 'our', 'congratulations' }
    >>> a = abbrev('congratulations', V)
    >>> len(a)
    1
    >>> unabbrev(a, V)
    'congratulations'
    """
    "*** YOUR CODE HERE ***"


# Q8. Extra for experts.

class Tree:
    """An n-ary tree with internal values."""
    def __init__(self, value, branches=[]):
        self.value = value
        self.branches = branches

def values(t):
    """Yield values of a tree by interleaving iterators of the branches.

    >>> T = Tree
    >>> t = T(1, [T(2, [T(4), T(6, [T(8)])]), T(3, [T(5), T(7)])])
    >>> tuple(values(t))
    (1, 2, 3, 4, 5, 6, 7, 8)
    """
    "*** YOUR CODE HERE ***"

def interleave(*iterables):
    """Interleave elements of iterables.

    >>> tuple(interleave([1, 4], [2, 5, 7, 8], [3, 6]))
    (1, 2, 3, 4, 5, 6, 7, 8)
    """
    "*** YOUR CODE HERE ***"