# Module 07 problems

# Part 1 - Warm up questions
# What is the worst case runtime, stated using big O notation, of the 
# following code? Determine your answer in terms of n, where n = the length of L, 
# in the last example. 
# Choose among:
# O(1), O(log n), O(n), O(n log n), O(n**2), O(2**n)
 
def fn(n):
    nrange = list(range(n))
    count = 0
    for i in nrange:
        j = n
        prod = 1
        while j > 0:
            prod = prod * j
            j = j - 1
        count = count + prod
    return count

def double_some(L):
    if L == []:
        return []
    elif L[0] % 10 == 1:
        return [2*L[0]] + double_some(L[1:])
    else:
        return [L[0]] + double_some(L[1:])
    

# Assuming n = len(L), determine the worst case runtime for 
# the following functions using big-O notation. 

def half_them(L):
    return list(map(lambda x: x//2, L))

def another_one(s):
    ans = []
    for c in s:
        occurrences = len(list(filter(lambda t: t==c, s)))
        ans = ans + [occurrences]
    return max(ans)


# Part 2 - Extra Practice

# Q1. 
# Let n = len(L)
def fn1(L):
    ans = []
    for x in L:
        if x[0]=='A':
            ans.append(x)
    return ans

# Q2.
# Let n = len(L)
def fn2(L):
    ans = []
    for x in L:
        if x[0]=='A':
            ans = ans + [x]
    return ans

# Q3: 
def fn3(n):
    ans = []
    for x in range(n):
        for y in range(n):
            ans.append(x)
    return ans

# Q4
def fn4(n):
    if n % 2 == 0:
        return list(range(n//2))
    else:
        return []

# Q5
def fn5(n):
    if n % 2 == 0:
        return "outcome1"
    elif n % 3 == 0:
        return "outcome2"
    elif n % 5 == 0:
        return "outcome3"
    else:
        return "outcome4"

# Q6
# n = len(s)
def fn6(s):
    t = ""
    for c in s:
        t = c + t
    return t

# Q7
# n = len(s)
def fn7(s):
    t = ""
    while s != "":
        t = s[0] + t
        s = s[1:]
    return t

# Q8
# n = len(s)
def fn8(s):
    t = ""
    p = 0
    while p < len(s):
        t = t + s[p]
        p = p + 2
    return t

# Q9:
# n = len(L)
def fn9(L):
    ans = L[:]
    for x in L:
        ans.insert(0, x*x)
    return ans

# Q10:
def fn10(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total = total + i*j
    return total

# Q11:
def fn11(n):
    total = 0
    for i in range(n):
        for j in range(5):
            total = total + i*j
    return total
                    
# Q12: 
# n = len(L)
def fn12(L):
    ans = []
    pos = 0
    while pos < len(L):
        total = 0
        rest = L[:pos]
        for x in rest:
            total = total + x
        ans.append(total)
        pos = pos + 1
    return ans

# Q13:
# n = len(s)
def fn13(s):
    L = []
    for c in s:
        for x in range(len(s)):
            L.append(c)
            return L

# Q14:
# Let n = len(s)
def fn14(s):
    count = 0
    for c in s:
        count = s.count(c)
    return count

# Q15:
# Let n = len(L)
def fn15(L):
    if L==[]:
        return 0
    else:
        return 1 + fn15(L[1:])

# Q16:
# Let n = len(L)
def fn16(L, pos):
    if pos > len(L):
        return 0
    else:
        return 1 + fn16(L, pos+1)

# Q17:
# let n = len(L)
def fn17(L, pos):
    if pos == len(L)-1:
        return L[-1]
    else:
        maxR = fn17(L, pos+1)
        return max(maxR, L[pos])

# Q18:
def fn18(n):
    if n==0:
        return 0
    elif fn18(n-1) > n//2:
        return fn18(n-1) - n//2
    else:
        return fn18(n-1) + n//2

# Q19: 
# Let n = len(L)
def fn19(L):
    L1 = L[0::2]
    if len(L) < 2:
        return []
    else:
        return fn19(L1)

# Q21:
def fn21(n):
    numbers = list(range(n))
    return list(map(lambda x: 2*x, numbers))
    
# Q22:
# Let n = len(L)
def fn22(L):
    counts = []
    for x in L:
        counts = [counts] + [L.count(x)]
    return list(map(lambda x:2*x, counts))

# Q23:
def fn23(n):
    L = list(range(1,n))
    M = list(map(lambda x: 2*x, L))
    N = list(filter(lambda y: y%2==1, M))
    return L + M + N

# Q24:
# let n = len(L)
def fn24(L):
    return list(map(lambda y: L.count(y), list(filter(lambda x: L.count(x)>1, L)))) 

# Q25:
# Let n = len(L)
def fn25(L):
    ans1 = list(range(1,len(L),3))
    ans2 = []
    i = 0
    while i < len(ans1):
        ans2.append(L[ans1[i]])
        ans2.append(sum(L))
        ans2.append(len(list(map(lambda x: x==L[0], ans2)))) 
        i = i + 4
    return ans2

# Q26
def fn26(lst): 
  if len(lst)<=1: return lst
  else:
    return fn26(lst[1:])+[lst[0]]

# Q27     
def fn27(lst):
    def rev(inverted, original, pos):
        if pos < 0: return inverted
        else:
            inverted.append(original[pos])
            return rev(inverted, original, pos-1)    
    backwards = []
    return rev(backwards, lst, len(lst)-1)

## ANSWERS
# Q1: Linear
# Q2: Quadratic
# Q3: Quadratic
# Q4: Linear
# Q5: Constant
# Q6: Quadratic
# Q7: Quadratic
# Q8: Quadratic
# Q9: Quadratic
# Q10: Quadratic
# Q11: Linear (inner loop is O(1) since its range does not depend on n)
# Q12: Quadratic
# Q13: Constant (since the return statement in the loop means only one iteration is performed)
# Q14: Quadratic
# Q15: Quadratic
# Q16: Linear
# Q17: Linear
# Q18: Exponential
# Q19: Linear
# Q21: Linear
# Q22: Quadratic
# Q23: Linear
# Q24: Quadratic
# Q25: Quadratic
# Q26: Quadratic
# Q27: Linear