CS61A SU20 Discussion 06 Solution

sol06.py

import doctest
import sys
import argparse

"""
---USAGE---

python3 sol06.py <name_of_function>

e.g python3 sol06.py stepper

---NOTES---

- if you pass all the doctests, you will get no terminal output
    - if you want to see the verbose output (all output shown even if the function is correct), run this:

    python3 sol06.py <name_of_function> -v

- if you want to test all of your functions, run this:

    python3 sol06.py all

"""

### Discussion 06 ### 

#########
# Nonlocal
#########

# Q1.1
def stepper(num):
    """
    >>> s = stepper(3)
    >>> s()
    4
    >>> s()
    5
    """
    "*** ENVIRONMENT DIAGRAM ***"
    def step():
        nonlocal num
        num = num + 1
        return num
    return step
# Walkthrough: https://www.youtube.com/watch?v=XsdTV6cAAjY&vq=hd1080&t=38m38s

# Q1.2
def memory_1(n):
    """
    >>> f = memory_1(10)
    >>> f(lambda x: x * 2)
    20
    >>> f(lambda x: x - 7)
    13
    >>> f(lambda x: x > 5)
    True
    """
    def f(g):
        nonlocal n
        n = g(n)
        print(n)
    return f

#########
# Midterm Review
#########

# Q2.1
def sixty_one_a():
    """
    >>> from operator import add
    >>> six = 1
    >>> def ty(one, a):
    ...     summer = one(a, six)
    ...     return summer
    >>> six = ty(add, 6)
    >>> summer = ty(add, 6)
    """
    "*** ENVIRONMENT DIAGRAM ***"
    pass
# Python Tutor: https://tinyurl.com/sixty-one-a

# Q2.2
def nonlocalist():
    """
    >>> prepend, get = nonlocalist()
    >>> prepend(2)
    >>> prepend(3)
    >>> prepend(4)
    >>> get(0)
    4
    >>> get(1)
    3
    >>> get(2)
    2
    >>> prepend(8)
    >>> get(2)
    3
    """
    get = lambda x: "Index out of range!"
    def prepend(value):
        nonlocal get
        f = get
        def get(i):
            if i == 0:
                return value
            return f(i - 1)
    return prepend, lambda x: get(x)

# Q2.3
def list_comp():
    """
    >>> f = lambda x: [print(i) for i in range(1, x + 1)] # method 1
    >>> f = f(10)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    >>> f
    [None, None, None, None, None, None, None, None, None, None]
    >>> f = lambda x: x and (f(x - 1) or print(x)) # method 2
    >>> f = f(10)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    >>> f
    """
    pass

# Q2.4
square = lambda x: x * x
double = lambda x: 2 * x
def memory_2(x, f):
    """Return a higher-order function that prints its memories.
    >>> f = memory_2(3, lambda x: x)
    >>> f = f(square)
    3
    >>> f = f(double)
    9
    >>> f = f(print)
    6
    >>> f = f(square)
    3
    None
    """
    def g(h):
        print(f(x))
        return memory_2(x, h)
    return g

# Q2.5
def announce_losses(who, last_score=0):
    """
    >>> f = announce_losses(0)
    >>> f1 = f(10, 0)
    >>> f2 = f1(1, 10) # Player 0 loses points due to swine swap
    Oh no! Player 0 just lost 9 point(s).
    >>> f3 = f2(7, 10)
    >>> f4 = f3(7, 11) # Should not announce when player 0's score does not change
    >>> f5 = f4(11, 12)
    """
    assert who == 0 or who == 1, 'The who argument should indicate a player.'
    def say(score0, score1):
        if who == 0:
            score = score0
        elif who == 1:
            score = score1
        if score < last_score:
            print("Oh no! Player", who, "just lost", last_score - score, "point(s).")
        return announce_losses(who, score)
    return say

# Q2.6
def fox_says(start, middle, end, num):
    """
    >>> fox_says('wa', 'pa', 'pow', 3)
    'wa-pa-pa-pa-pow'
    >>> fox_says('fraka', 'kaka', 'kow', 4)
    'fraka-kaka-kaka-kaka-kaka-kow'
    """
    def repeat(k):
        if k == 1:
            return middle
        else:
            return middle + '-' + repeat(k-1)
    return start + '-' + repeat(num) + '-' + end

# Q2.7
def primary_stress(t):
    """
    >>> word = tree("", [
    ...    tree("w", [tree("s", [tree("min")]), tree("w", [tree("ne")])]),
    ...    tree("s", [tree("s", [tree("so")]), tree("w", [tree("ta")])])])
    >>> primary_stress(word)
    'so'
    >>> phrase = tree("", [
    ...    tree("s", [tree("s", [tree("law")]), tree("w", [tree("degree")])]),
    ...    tree("w", [tree("requirement")])])
    >>> primary_stress(phrase)
    'law'
    """
    def helper(t, num_s):
        if is_leaf(t):
            return [label(t), num_s]
        if label(t) == "s":
            num_s = num_s + 1
        return max([helper(b, num_s) for b in branches(t)], key = lambda a: a[1])
    return helper(t, 0)[0]

# Q2.8
def subset_sum(seq, k):
    """
    >>> subset_sum([2, 4, 7, 3], 5)         # 2 + 3 = 5
    True
    >>> subset_sum([1, 9, 5, 7, 3], 2)
    False
    >>> subset_sum([1, 1, 5, -1], 3)
    False
    >>> 3 in [1, 2, 3] # Note: You can use the in operator to determine if an element belongs to a list
    True
    >>> 4 in [1, 2, 3]
    False
    """
    if len(seq) == 0:
        return False
    elif k in seq:
        return True
    else:
        return subset_sum(seq[1:], k - seq[0]) or subset_sum(seq[1:], k)

# Tree ADT

# Constructor
def tree(label, branches=[]):
    """Construct a tree with the given label value and a list of branches."""
    for branch in branches:
        assert is_tree(branch)
    return [label] + list(branches)

# Selector
def label(tree):
    """Return the label value of a tree."""
    return tree[0]

# Selector
def branches(tree):
    """Return the list of branches of the given tree."""
    return tree[1:]

def is_tree(tree):
    """Returns True if the given tree is a tree, and False otherwise."""
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

# For convenience
def is_leaf(tree):
    """Returns True if the given tree's list of branches is empty, and False
    otherwise."""
    return not branches(tree)

### For running tests only. Not part of discussion content ###

parser = argparse.ArgumentParser(description="Test your work")
parser.add_argument("func", metavar="function_to_test", help="Function to be tested")
parser.add_argument("-v", dest="v", action="store_const", const=True, default=False, help="Verbose output")
args = parser.parse_args()
try:
    if args.func == "all":
        if args.v:
            doctest.testmod(verbose=True)
        else:
            doctest.testmod()
    else:
        if args.v:
            doctest.run_docstring_examples(globals()[args.func], globals(), verbose=True, name=args.func)
        else:
            doctest.run_docstring_examples(globals()[args.func], globals(), name=args.func)
except:
    sys.exit("Invalid Arguments")