'''
Group Members
=============
'''
userids = ['Thormundur15'] # fill in this array with strings of usernames

def m2p1(n):
    '''Given a non-negative integer n calculate n-th Tribonacci number, using recursion.
    '''
    if n <= 1: return 0
    if n == 2: return 1

    return m2p1(n-1) + m2p1(n-2) + m2p1(n-3)

memo = {0:0, 1:0, 2:1}

def m2p2(n):
    '''Given a non-negative integer n calculate n-th Tribonacci number, using recursion and memoization.
    '''

    if n < 0: return 0

    if n in memo:
        return memo[n]

    else:
        new_value = m2p2(n-1) + m2p2(n-2) + m2p2(n-3)
        memo[n] = new_value
        return new_value

def m2p3(n):
    '''Given a non-negative integer n calculate n-th Tribonacci number using memoization with a list, and without using recursion
    '''
    T = [0,0,1] + [0]*(n-1)

    for i in range(3,n+1):
        T[i] = T[i-3] + T[i-2] + T[i-1]

    return T[n]

def m2p4(n):
    '''Given a non-negative integer n calculate n-th Tribonacci number, without using recursion and only storing three values.
    '''
    if n <= 1: return 0

    t2, t1, t0 = 1,0,0

    for i in range(3,n+1):

        t2, t1, t0 = t0+t1+t2, t2, t1

    return t2

def m2p5(n,L):
    '''Project Euler Problem 31.
The input n is a positive integer and the input L is a list of coin values.
The returned value is the number of ways n can be split using the coin values in the list L.
    '''
    T = [1] + [0]*n
    for i in L:
        for j in range(i, n+1):
            T[j] += T[j-i]
    return T[n]

def m2p6(k):
    '''Project Euler Problem 76.
The input k should be a positive integer. The returned value is the number of
different ways k can be written as a sum of at least two positive integers.
    '''
    T = [1] + [0]*k
    for i in range(1, k):
        for j in range(i, k+1):
            T[j] += T[j-i]
    return T[k]


def m2p7(k):
    '''Project Euler Problem 77.
The input k should be a positive integer. The returned value is the smallest positive
integer n such that the number of ways to write n as a sum of primes exceeds k
    '''
    if(k == 1): return 6
    P = Primes()
    summ = 0
    while(True):
        T = [1] + [0]*summ
        for i in P:
            for j in range(i, summ+1):
                T[j] += T[j-i]
            if(i > 1000):
                break
        if T[summ] > k:
            break
        summ += 1
    return summ

def m2p8(k):
    '''Project Euler Problem 78.
The input k should be a positive integer. The returned value is the smallest positive
integer n such that number of ways n coins can be separated into piles is divisible by k.
    '''
    ''''''
    T = [1] + [0]*k
    for i in range(1, k):
        for j in range(i, k+1):
            T[j] += T[j-i]
    return T[k] + 1

def m2p9(M):
    '''Project Euler Problem 81.
The input M should be an n x n matrix containing integers, given as a list of lists.
The output is the minimal path sum, as defined on Project Euler.
    '''
    for i in range(len(M)):
        for j in range(len(M)):
            if(i and j):
                M[i][j] += min(M[i-1][j], M[i][j-1])
            elif(i):
                M[i][j] += M[i-1][j]
            elif(j):
                M[i][j] += M[i][j-1]
    return M[len(M)-1][len(M)-1]