"""Submission for CS61A Homework 7.

Name:
Login:
Collaborators:
"""

# Q1.

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

    >>> part(5)
    7
    """
    "*** YOUR CODE HERE ***"


# Q2.

def g(n):
    """Return the value of g, defined 
          g(n) = n,                                       if n <= 3
          g(n) = g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3),  if n > 3 
    For integers n > 0.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    "*** YOUR CODE HERE ***"

def g_iter(n):
    """Return the value of g, defined 
          g(n) = n,                                       if n <= 3
          g(n) = g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3),  if n > 3 
    For integers n > 0.

    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    "*** YOUR CODE HERE ***"

# Q3.

def g_counted(n):
    """Return a tuple (g(n), cost(n)), where cost(n) is the number of times
    the recursive version of g is called during the computation of g(n).

    >>> g_counted(2)
    (2, 1)
    >>> g_counted(4)
    (10, 4)
    >>> g_counted(5)
    (22, 7)
    """
    "*** YOUR CODE HERE ***"

# Q4.

from math import sqrt

class vect:
    """A vector in 2-dimensional Euclidean space.

    >>> v1 = vect(3, 4)
    >>> v1
    vect(3, 4)
    >>> print(v1)
    (3, 4)
    >>> v1.x
    3
    >>> v1.y
    4
    >>> v1.x = 7
    Traceback (most recent call last):
        ...
    AttributeError: can't set attribute
    >>> v1 * 3
    vect(9, 12)
    >>> 3 * v1
    vect(9, 12)
    >>> v2 = vect(4, -2)
    >>> v1 + v2
    vect(7, 2)
    >>> v1 - v2
    vect(-1, 6)
    >>> v1 * v2             # inner product = 12 - 8
    4
    >>> abs(v1)             # = sqrt(3**2 + 4**2)
    5.0
    """

    "*** YOUR CODE HERE ***"

# Q5.

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

    >>> partm(5)
    7
    >>> partm(500)
    2300165032574323995027
    """

    "*** YOUR CODE HERE ***"

## Q6.

class rlist:
    """A mutable recursive list."""

    empty = None

    def __init__(self, first, rest = empty):
        self.__first = first
        self.__rest = rest

    def first(r):
        return r.__first

    def rest(r):
        return r.__rest

    def set_first(r, new_first):
        r.__first = new_first
    def set_rest(r, new_rest):
        r.__rest = new_rest

    def rlist_to_list(r):
        """The standard Python list containing the same items as R."""
        result = []
        while r is not rlist.empty:
             result.append(r.first())
             r = r.rest()
        return result

def has_cycle(L):
    """True iff L is a circular rlist.

    >>> C = rlist(1, rlist(2, rlist(3)))
    >>> has_cycle(C)
    False
    >>> C.rest().rest().set_rest(C)
    >>> has_cycle(C)
    True
    >>> C = rlist(0, C)
    >>> has_cycle(C)
    True
    """
    "*** YOUR CODE HERE ***"
    
## Q7.  Extra for experts

def has_cycle2(L):
    """True iff L is a circular rlist.

    >>> C = rlist(1, rlist(2, rlist(3)))
    >>> has_cycle2(C)
    False
    >>> C.rest().rest().set_rest(C)
    >>> has_cycle2(C)
    True
    >>> C = rlist(0, C)
    >>> has_cycle2(C)
    True
    """
    "*** YOUR CODE HERE ***"

## Q8.  Extra for experts

from operator import sub, mul

def fact_maker():
"*** YOUR CODE HERE ***"
    return YOUR_CODE_HERE
"""
>>> fact_maker()(5)
120
"""