Skip to content

Instantly share code, notes, and snippets.

@LarynQi

LarynQi/sol06.py Secret

Last active Jul 15, 2020
Embed
What would you like to do?
CS61A SU20 Discussion 06 Midterm Review Solution
import doctest
import sys
import argparse
"""
---USAGE---
python3 sol06.py <name_of_function>
e.g python3 sol06.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 sol06.py <name_of_function> -v
- if you want to test all of your functions, run this:
python3 sol06.py all
"""
### Discussion 06 ###
# Walkthrough videos can be find on the website!
#########
# 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
"""
def f(g):
nonlocal n
n = g(n)
print(n)
return f
#########
# Midterm Review
#########
# RQ1
# PDF: https://cs61a.org/assets/pdfs/61a-sp19-mt2.pdf#page=4
# SOL: https://cs61a.org/assets/pdfs/61a-sp19-mt2-solution.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
"""
# Solution 1
if type(L) != list:
return L == v
else:
return any([in_nested(v, sub) for sub in L])
# Solution 2
if type(L) == type(v) or L == []:
return L == v
else:
return in_nested(v, L[0]) or in_nested(v, L[1:])
# Solution 3
if type(L) is list:
return L != [] and (in_nested(v, L[0]) or in_nested(v, L[1:]))
else:
return v == L
# RQ2
# PDF: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final.pdf#page=6
# SOL: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final-solution.pdf#page=6
def factorize(n, k=2):
"""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
"""
if k == n:
return 1
elif k > n:
return 0
elif n % k > 0:
return factorize(n, k + 1)
return factorize(n // k, k) + factorize(n, k + 1)
# RQ3
# PDF: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2.pdf#page=6
# SOL: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2_sol.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
"""
if min(a, b) == 0:
return a + b
elif a % 10 == b % 10:
return combo(a // 10, b // 10) * 10 + a % 10
else:
return min(combo(a // 10, b) * 10 + a % 10, combo(a, b // 10) * 10 + b % 10)
# RQ4
# PDF: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2.pdf#page=7
# SOL: https://cs61a.org/exam/sp18/mt2/61a-sp18-mt2_sol.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]
"""
result = [label(b) for b in branches(t) if len(branches(t)) > 1]
for b in branches(t):
result.extend(siblings(b))
return result
# RQ5
# PDF: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final.pdf#page=6
# SOL: https://inst.eecs.berkeley.edu/~cs61a/sp18/assets/pdfs/61a-sp18-final-solution.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
"""
def h(k, args_so_far):
if k == 0:
return f(args_so_far)
return lambda x: h(k-1, args_so_far + [x])
return h(n, [])
# # 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