hw9.py (plain text)

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