"""CS 61A HW 03
Name:
Login:
TA:
Section:
"""

#### Q1
def g(n):
    """Recursively find g(n) as defined in the homework spec

    g(n) = n,                                       if n <= 3
           g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3),  if n > 3

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(4)
    10
    >>> g(10)
    1657
    """
    "*** YOUR CODE HERE ***"

def g_iter(n):
    """Iteratively find g(n) as defined in the homework spec

    g(n) = n,                                       if n <= 3
           g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3),  if n > 3

    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(4)
    10
    >>> g_iter(10)
    1657
    """
    "*** YOUR CODE HERE ***"

#### Q2

def continued_frac(n_term, d_term, k):
    """Returns the k-term continued fraction with numerators defined by n_term
    and denominators defined by d_term.

    >>> # 1 / golden ratio
    ... round(continued_frac(lambda x: 1, lambda x: 1, 8), 3)
    0.618
    >>> # 1 / (1 + (2 / (2 + (3 / (3 + (4 / 4))))))
    ... round(continued_frac(lambda x: x, lambda x: x, 4), 6)
    0.578947
    """
    "*** YOUR CODE HERE ***"

#### Q3

def tower_of_hanoi(n, start, end):
    """Print the moves required to solve the tower of hanoi game if we start
    with n disks on the start pole and want to move them all to the end pole.

    The game is to assumed to have 3 poles (which is traditional).

    >>> tower_of_hanoi(1, 1, 3)
    Move 1 disk from rod 1 to rod 3
    >>> tower_of_hanoi(2, 1, 3)
    Move 1 disk from rod 1 to rod 2
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 2 to rod 3
    >>> tower_of_hanoi(3, 1, 3)
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 1 to rod 2
    Move 1 disk from rod 3 to rod 2
    Move 1 disk from rod 1 to rod 3
    Move 1 disk from rod 2 to rod 1
    Move 1 disk from rod 2 to rod 3
    Move 1 disk from rod 1 to rod 3
    """
    "*** YOUR CODE HERE ***"
    print("Move 1 disk from rod", start, "to rod", end)
    "*** YOUR CODE HERE ***"

#### Q4
def part_help(m, k):
    """Return the number of partitions of m that use integers greater than
    or equal to k.

    >>> part_help(3, 2) # 3
    1
    >>> part_help(3, 1) # 3, 2 + 1, 1 + 1 + 1
    3
    """
    "*** YOUR CODE HERE ***"

def part(n):
    """Return the number of partitions of positive integer n.

    >>> part(5)
    7
    >>> part(7)
    15
    """
    return part_help(n, 1)

#### Extra for Experts
#### Q5

def factorial(n):
    """Computes the factorial of n using a single expression involving lambdas,
    mathematical operators, and the ternary operator.

    >>> factorial(5)
    120
    >>> factorial(6)
    720
    """
    return "ONE LINER HERE"