#------------------------TD8------------------------#


#####################[Code 1]##########################

def mypower(a, b):
    if b == 1:
        return a
    return a*mypower(a,b-1)

print(mypower(2, 8))



#####################[Code 2]##########################

def mymax(A):
    if len(A) == 1:
        return A[0]
    else:
        m2 = mymax(A[1:])
        if A[0] > m2:
            return A[0]
        else:
            return m2

print(mymax([3, 7, 12, 346, 13, 74]))



#####################[Code 3]##########################

def evenbeforeodd1(A):
    if len(A) == 1:
        return [ A[0] ]

    B = evenbeforeodd1(A[1:])

    if A[0]%2 == 0:
        B.insert(0, A[0])
    else: B.append(A[0])

    return B

print( evenbeforeodd1([4,1,7,5,9,3,1,2,4,2,7]) )



#####################[Code 4]##########################

def evenbeforeodd2(A):
    if len(A) == 1:
        if A[0]%2 == 0:
            return [ A[0] ], [ ]
        else:
            return [ ], [ A[0] ]

    B, C = evenbeforeodd2(A[1:])

    if A[0]%2 == 0:
        B.insert(0, A[0])
    else:
        C.insert(0, A[0])

    return B, C

print( evenbeforeodd2([4,1,7,5,9,3,1,2,4,2,7]) )



#####################[Code 5]##########################

def reverse(s):
    if len(s) == 1: return s
    else: return reverse(s[1:])+s[0]

print(reverse("hello"))



#####################[Code 6]##########################

def findeven_recursion(A):
    if len(A) == 0:
        return []

    B = findeven_recursion(A[1:])
    if A[0]%2 == 0:
        B.append(A[0])
    return B

print(findeven_recursion([3,1,5,4,4,2,1,22,7]))



#####################[Code 7]##########################

def findeven_loops(A):
    B = []

    for x in A:
        if x%2 == 0:
            B.append(x)
    return B

print(findeven_loops([3,1,5,4,4,2,1,22,7]))



#####################[Code 8]##########################

import sys, random, time
sys.setrecursionlimit(10**6)

def findeven_recursion(A):
    if len(A) == 0:
        return []
    B = findeven_recursion(A[1:])
    if A[0]%2 == 0:
        B.append(A[0])
    return B

def findeven_recursion_FAST(A,k):
    if k == 0:
        return []
    B = findeven_recursion_FAST(A, k-1)
    if A[k-1]%2 == 0:
        B.append(A[k-1])
    return B


n = 10000
I = [random.randint(0,10000) for _ in range(0, n)]

start = time.time()
print(len(findeven_recursion(I)))
print("findeven_recursion: ",  time.time() - start)

start = time.time()
print(len(findeven_recursion_FAST(I, len(I))))
print(f"indeven_recursion_FAST: ",  time.time() - start)



#####################[Code 9]##########################

def flattenAll(A):
    if len(A) == 0: return []

    B = flattenAll(A[1:])

    if type(A[0]) != int:
        return flattenAll(A[0]) + B
    else:
        return [A[0]] + B


A = [2, [ [ [3,4], [4] ], 1 ], [6] ]
print(flattenAll(A))

A = [ [ [ [3,4], [4] ] ] ]
print(flattenAll(A))



#####################[Code 10]##########################

def allSubsets(A):
    if len(A) == 1:
        return [ [], [A[0]] ]
    B = allSubsets(A[1:])
    n = len(B)
    for i in range(0, n):
        B.append( B[i] + [A[0]] )
    return B

print(allSubsets([1,2,3]))



#####################[Code 11]##########################

def allPermutations(A):
    if len(A) == 1:
        return [ [A[0]] ]
    B = allPermutations(A[1:])

    C = []
    for i in range(0, len(B)):
        for j in range(0, len(B[i])+1):
            w = list(B[i])
            w.insert(j, A[0])
            C.append(w)
    return C

print(allPermutations([1,2,3,4]))



#####################[Code 12]##########################

def allPermutations(A):
    if len(A) == 1:
        return [ A ]

    B = []
    for i in range(0, len(A)):
        p = A[i]
        C = A[:i] + A[i+1:]
        for x in allPermutations(C):
            B.append( [p] + x )
    return B

print(allPermutations([1,2,3,4]))



#####################[Code 13]##########################

def find_valid_start(gas, cost):
    n = len(gas)

    if n == 1:
        return 0

    for j in range(0, n):
        if cost[j] > gas[j]:
            cost_p = cost[:j] + cost[j+1:]
            cost_p[j-1] = cost[j-1] + cost[j] - gas[j]

            gas_p = gas[:j] + gas[j+1:]

            sol = find_valid_start(gas_p, cost_p)
            if sol >= j: sol += 1
            return sol
    return 0



#####################[Code 14]##########################

def findPalindrome(s):
    if len(s) == 1 or len(s) == 0:
        return s

    if s[0] == s[-1]:
        return s[0] + findPalindrome(s[1:-1]) + s[-1]
    else:
        t1 = findPalindrome(s[:-1])
        t2 = findPalindrome(s[1:])
        if len(t1) > len(t2):
            return t1
        else: return t2

print(findPalindrome("abcdfadfasdfpajsasdfkjasasdfasdfba"))



#####################[Code 15]##########################

def findPalindrome_slow(s):
    if len(s) == 1 or len(s) == 0:
        return s

    if s[0] == s[-1]:
        return s[0] + findPalindrome_slow(s[1:-1]) + s[-1]
    else:
        return max(findPalindrome_slow(s[:-1]), findPalindrome_slow(s[1:]), key = len)

print(findPalindrome_slow("abcdfadfasdfpajsasdfkjasasdfasdfba"))



#####################[Code 16]##########################

def listGame(A, i = 0, j = None):
    if j == None: j = len(A)-1

    if i == j: return A[i]

    mysum = 0
    for k in range(i, j+1): mysum += A[k]

    left = listGame(A, i+1, j)
    right = listGame(A, i, j-1)

    return max (mysum-left,  mysum-right)


import random
A = [ random.randint(0,100) for i in range(10) ]
print(A)
print(listGame(A))