CS61A SU20 Discussion 04 Solution

sol04.py

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