Skip to content

Instantly share code, notes, and snippets.

@LarynQi
Last active Jul 15, 2020
Embed
What would you like to do?
CS61A SU20 Discussion 06 Midterm Review
import doctest
import sys
import argparse
"""
---USAGE---
python3 disc06.py <name_of_function>
e.g python3 disc06.py memory
---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 disc06.py <name_of_function> -v
- if you want to test all of your functions, run this:
python3 disc06.py all
"""
### Discussion 06 ###
#########
# Nonlocal
#########
# Q1.2
def memory(n):
"""
>>> f = memory(10)
>>> f(lambda x: x * 2)
20
>>> f(lambda x: x - 7)
13
>>> f(lambda x: x > 5)
True
"""
"*** UNCOMMENT SKELETON ***"
# def f(g):
# ________________________
# ________________________
# ________________________
# return f
#########
# Midterm Review
#########
# RQ1
# PDF: https://cs61a.org/assets/pdfs/61a-sp19-mt2.pdf#page=4
def in_nested(v, L):
"""Implement in_nested which takes in a value v and a nested list or an individual value L and returns whether
the value is contained in the list.
Hint: The built-in function type takes an object and returns the type of that object
>>> in_nested(5, [1, 2, [[3], 4]])
False
>>> in_nested(9, [[[1], [6, 4, [5, [9]]], 7], 7, 7])
True
>>> in_nested(1, 1)
True
"""
"*** UNCOMMENT SKELETON ***"
# if ________________________:
# return ________________________
# else:
# return ________________________
# RQ2
# PDF: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final.pdf#page=6
def factorize(n, k=2):
"""Implement factorize, which takes two integers n and k, both larger than 1. It returns the number
of ways that n can be expressed as a product of non-decreasing integers greater than or equal to k.
Return the number of ways to factorize positive integer n.
>>> factorize(7) # 7
1
>>> factorize(12) # 2*2*3, 2*6, 3*4, 12
4
>>> factorize(36) # 2*2*3*3, 2*2*9, 2*3*6, 2*18, 3*3*4, 3*12, 4*9, 6*6, 36
9
"""
"*** UNCOMMENT SKELETON ***"
# if _____________________________________________________________________________________:
# return 1
# elif ___________________________________________________________________________________:
# return 0
# elif ___________________________________________________________________________________:
# return factorize(_________________________________, ________________________________)
# return _________________________________________________________________________________
# RQ3
# PDF: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2.pdf#page=6
def combo(a, b):
"""Return the smallest integer with all of the digits of a and b (in order).
>>> combo(531, 432) # 45312 contains both _531_ and 4_3_2.
45312
>>> combo(531, 4321) # 45321 contains both _53_1 and 4_321.
45321
>>> combo(1234, 9123) # 91234 contains both _1234 and 9123_.
91234
>>> combo(0, 321) # The number 0 has no digits, so 0 is not in the result.
321
"""
"*** UNCOMMENT SKELETON ***"
# if ________________________:
# return a + b
# elif ________________________:
# return combo(___________________, __________________)_______________________________
# return ________(________________________, ________________________)
# RQ4
# PDF: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2.pdf#page=7
# Note: The written/PDF version uses the Tree class. We have not learned about this yet, and it
# is not in scope for the midterm. The concept is the same, and the skeleton below is correct.
def siblings(t):
"""Definition. A sibling of a node in a tree is another node with the same parent.
Return a list of the labels of all nodes that have siblings in t.
>>> a = tree(4, [tree(5), tree(6), tree(7, [tree(8)])])
>>> siblings(tree(1, [tree(3, [a]), tree(9, [tree(10)])]))
[3, 9, 5, 6, 7]
"""
"*** UNCOMMENT SKELETON ***"
# result = [_______________________________________________________________________________]
# for b in branches(t):
# _____________________________________________________________________________________
# return result
# RQ5
# PDF: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final.pdf#page=6
def scurry(f, n):
"""Return a function that calls f on a list of arguments after being called n times.
>>> scurry(sum, 4)(1)(1)(3)(2) # equivalent to sum([1, 1, 3, 2])
7
>>> scurry(len, 3)(7)([8])(-9) # equivalent to len([7, [8], -9])
3
"""
"*** UNCOMMENT SKELETON ***"
# def h(k, args_so_far):
# if k == 0:
# return ________________________________________________________________________
# return ____________________________________________________________________________
# return ________________________________________________________________________________
# 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")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment