"""CS 61A HW 09 Name: Login: TA: Section: """ from rlist import * #### Core Questions #### Q1 def deep_map_mut(fn, lst): """Deeply maps a function over a Python list, replacing each item in the original list object. Does NOT create new lists by either using literal notation ([1, 2, 3]), +, or slicing. Does NOT return the mutated list object. >>> l = [1, 2, [3, [4], 5], 6] >>> deep_map_mut(lambda x: x * x, l) >>> l [1, 4, [9, [16], 25], 36] """ "*** YOUR CODE HERE ***" #### Q2 FIB_MEMO = { 0 : 0, 1 : 1 } def prints_calls(fn): """Decorator which causes the function to print each call to that function in addition to performing the original operations >>> @prints_calls ... def fact(n): ... if n == 0: ... return 1 ... return n * fact(n - 1) ... >>> fact_4 = fact(4) fact(4) fact(3) fact(2) fact(1) fact(0) >>> fact_4 24 """ def printing_fn(*args): if len(args) == 1: print(str(fn.__name__) + '(' + str(args[0]) + ')') else: print(str(fn.__name__) + str(args)) return fn(*args) return printing_fn def memoized_fib(n): """A memoized version of the fibonacci recursive function. Uses FIB_MEMO global variable to keep track of fibonacci numbers that this function has already computed. >>> FIB_MEMO == { 0 : 0, 1 : 1 } True >>> memoized_fib(6) 8 >>> FIB_MEMO == { 0 : 0, ... 1 : 1, ... 2 : 1, ... 3 : 2, ... 4 : 3, ... 5 : 5, ... 6 : 8 } True >>> memoized_fib = prints_calls(memoized_fib) >>> fib_6 = memoized_fib(6) memoized_fib(6) >>> fib_6 8 """ "*** YOUR CODE HERE ***" #### Q3 def rlist_deep_map_mut(fn, rl): """Mutates a deep rlist by replacing each item found with the result of calling fn on the item. Does NOT create new RLists (so no use of RList's constructor, the add operator, or RList.populate)! Does not return the modified RList object. >>> test_rl = RList.populate(1, 2, RList.populate(3, RList(4), 5), 6) >>> str(test_rl) '<1, 2, <3, <4>, 5>, 6>' >>> rlist_deep_map_mut(lambda x: x * x, test_rl) >>> str(test_rl) '<1, 4, <9, <16>, 25>, 36>' """ "*** YOUR CODE HERE ***" #### Reinforcement Questions #### Q4 def deep_filter_mut(pred, lst): """Deeply maps a function over a Python list, replacing each item in the original list object. Does NOT create new lists by either using literal notation ([1, 2, 3]), +, or slicing. Does NOT return the mutated list object. >>> l = [1, 2, [3, [4], 5], 6] >>> deep_filter_mut(lambda x: x % 2 != 0, l) >>> l [1, [3, [], 5]] >>> l2 = [1, 2, 3, 4] >>> deep_filter_mut(lambda x: x < 0, l2) >>> l2 [] >>> l3 = [1, 2, [3, [4], 5], 6] >>> deep_filter_mut(lambda x: x < 0, l3) >>> l3 [[[]]] """ "*** YOUR CODE HERE ***" #### Q5 def memoized(fn): """Decorator which memoizes a function to avoid recomputing calls that it has already evaluated. >>> @memoized ... @prints_calls ... def fact(n): ... if n == 0: ... return 1 ... return n * fact(n - 1) ... >>> fact_4 = fact(4) fact(4) fact(3) fact(2) fact(1) fact(0) >>> fact_4 24 >>> fact_4_dup = fact(4) >>> fact_4_dup 24 """ fn_memo = {} def memoized_fn(*args): "*** YOUR CODE HERE ***" return memoized_fn #### Q6 class Abbrev: """An abbreviation map.""" def __init__(self, full_names): """Initialize self to handle abbreviations for the words in the sequence of strings full_names. It is an error if a name appears twice in full_names. """ "*** YOUR CODE HERE ***" def complete(self, cmnd): """The member of my word list that the string cmnd abbreviates, if it exists and is unique. cmnd abbreviates a string S in my word list if cmnd == S, or cmnd is a prefix of S and of no other command in my word list. Raises ValueError if there is no such S. >>> a = Abbrev(['continue', 'catch', 'next', ... 'st', 'step', 'command']) >>> a.complete('ne') 'next' >>> a.complete('co') Traceback (most recent call last): ... ValueError: not unique: 'co' >>> a.complete('st') 'st' >>> a.complete('foo') Traceback (most recent call last): ... ValueError: unknown command: 'foo' """ "*** YOUR CODE HERE ***" def minimal_abbreviation(self, cmnd): """The string, S, of shortest length such that self.complete(S) == cmnd. >>> a = Abbrev(['continue', 'catch', 'next', ... 'st', 'step', 'command']) >>> a.minimal_abbreviation('continue') 'con' >>> a.minimal_abbreviation('next') 'n' >>> a.minimal_abbreviation('step') 'ste' >>> a.minimal_abbreviation('st') 'st' >>> a.minimal_abbreviation('ste') Traceback (most recent call last): ... ValueError: unknown command: 'ste' """ "*** YOUR CODE HERE ***" #### Extra for Experts #### Q7 def detect_cycle(rl): """Returns True if there is a cycle in the rlist. Uses constant space (does not use additional data structures that grow over time). >>> c = RList.populate(1, 2) >>> detect_cycle(c) False >>> c.rest.rest = c >>> detect_cycle(c) True >>> detect_cycle(RList(0, c)) True """ "*** YOUR CODE HERE ***"