Skip to content

Instantly share code, notes, and snippets.

@LarynQi

LarynQi/sol04.py Secret

Last active Jul 8, 2020
Embed
What would you like to do?
CS61A SU20 Discussion 04 Solution
import doctest
import sys
import argparse
"""
---USAGE---
python3 disc04.py <name_of_function>
e.g python3 disc04.py multiply
---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 sol04.py <name_of_function> -v
- if you want to test all of your functions, run this:
python3 sol04.py all
"""
### Discussion 04 ###
#########
# Recursion
#########
# Q1.1
def multiply(m, n):
"""
>>> multiply(5, 3)
15
"""
if n == 1:
return m
return m + multiply(m, n -1)
# Q1.2
def is_prime(n):
"""Iterative solution to is_prime."""
if n == 1:
return False
k = 2
while k < n:
if n % k == 0:
return False
k += 1
return True
def is_prime(n):
"""Recursive solution to is_prime.
>>> is_prime(7)
True
>>> is_prime(10)
False
>>> is_prime(1)
False
"""
def prime_helper(index):
if index == n:
return True
elif n % index == 0 or n == 1:
return False
else:
return prime_helper(index + 1)
return prime_helper(2)
#########
# Tree Recursion
#########
# Example: Fibonacci sequence
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
# Q2.1
def count_stair_ways(n):
if n == 0:
return 1
if n < 0:
return 0
return count_stair_ways(n - 1) + count_stair_ways(n - 2)
# Q2.2
def count_k(n, k):
"""
>>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 1
4
>>> count_k(4, 4)
8
>>> count_k(10, 3)
274
>>> count_k(300, 1) # Only one step at a time
1
"""
if n == 0:
return 1
elif n < 0:
return 0
else:
total = 0
i = 1
while i <= k:
total += count_k(n - i, k)
i += 1
return total
#########
# Lists
#########
"""
>>> fantasy_team = ['aaron rodgers', 'desean jackson']
>>> print(fantasy_team)
['aaron rodgers', 'desean jackson']
>>> fantasy_team[0]
'aaron rodgers'
>>> fantasy_team[len(fantasy_team) - 1]
'desean jackson'
>>> fantasy_team[-1]
'desean jackson'
"""
"""
>>> directors = ['jenkins', 'spielberg', 'bigelow', 'kubrick']
>>> directors[:2]
['jenkins', 'spielberg']
>>> directors[1:3]
['spielberg', 'bigelow']
>>> directors[1:]
['spielberg', 'bigelow', 'kubrick']
>>> directors[0:4:2]
['jenkins', 'bigelow']
>>> directors[::-1]
['kubrick', 'bigelow', 'spielberg', 'jenkins']
"""
# Q3.1
# Don't test this function until you've tried filling out the blanks,
# since the output will show you the correct answers.
def wwpd():
"""
>>> a = [1, 5, 4, [2, 3], 3]
>>> print(a[0], a[-1])
1 3
>>> len(a)
5
>>> 2 in a
False
>>> 4 in a
True
>>> a[3][0]
2
"""
pass
# Q3.2
def even_weighted(s):
"""
>>> x = [1, 2, 3, 4, 5, 6]
>>> even_weighted(x)
[0, 6, 20]
"""
return [i * s[i] for i in range(len(s)) if i % 2 == 0]
# Q3.3
def max_product(s):
"""Return the maximum product that can be formed using non-consecutive
elements of s.
>>> max_product([10, 3, 1, 9, 2]) # 10 * 9
90
>>> max_product([5, 10, 5, 10, 5]) # 5 * 5 * 5
125
>>> max_product([])
1
"""
if s == []:
return 1
elif len(s) == 1: # Base case optional
return s[0]
else:
return max(max_product(s[1:]), s[0] * max_product(s[2:]))
# Quiz
def check_hole_number(n):
"""
>>> check_hole_number(123)
False
>>> check_hole_number(3241968)
True
>>> check_hole_number(3245968)
False
"""
if n // 10 == 0:
return True
return ((n // 10) % 10 < (n % 10) and ((n // 10) % 10) < ((n // 100) % 10)) and check_hole_number(n // 100)
def check_mountain_number(n):
"""
>>> check_mountain_number(103)
False
>>> check_mountain_number(153)
True
>>> check_mountain_number(123456)
True
>>> check_mountain_number(2345986)
True
"""
def helper(x, is_increasing):
if x // 10 == 0:
return True
if is_increasing and (x % 10) < ((x // 10) % 10):
return helper(x // 10, is_increasing)
return (x % 10) > ((x // 10) % 10) and helper(x // 10, False)
return helper(n, True)
### 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