"""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 '' 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 ***"