###############################################################################
# ---------------- 15-112 Recitation #15: Recursive and OOPy Applications ---------------- #

# This is a starter file of the problems we did in recitation. A good way to
# use this file is to try to re-write problems you saw in recitation from
# scratch. This way, you can test your understanding and ask on Piazza or
# office hours if you have questions :)

# --------------------------------------------------------------------------- #
###############################################################################
# Big Oh analysis
###############################################################################
# LEARNING OBJECTIVES
# How do we solve more advanced recursion problems?

#What is the big OH of these functions?
def bigOh1(L): 
# assume L is an NxN (square) 2d list 
    M=[] 
    for i in range(len(L)): 
        for j in range(i, len(L)): 
            M.append(L[i][j]) 
            M.sort() 
    return 112 if (112 not in M) else M.index(112)

def bigOh2(s): 
    # s is a string of length N 
    myS = s * len(s) 
    t = set() 
    for i in range(len(s)): 
        if s[i] not in t: 
            t.add(s[i]) 
            k = 1 
            while k < len(myS): 
                k *= 2 
                if str(k) in s: 
                    print("wooo") 
    return s


###############################################################################
# More Big Oh
###############################################################################
# LEARNING OBJECTIVES
# How to think about Big Oh

'''
Answer the following questions.

Your code takes 5 seconds to run on an input of length 1000. How long does your 
code take to run on an input of length 2000 if it has a big Oh of n^2?

Your code takes 0.005 seconds to run on an input of length 1000 and 0.01 seconds 
to run on an input of length 4000. What is the big oh?

Your code takes 10 seconds to run on an input of length 1,000,000 and 20 seconds 
to run on an input of length 2,000,000.  What is the big oh?
'''

###############################################################################
# Dictionary CT
###############################################################################
# LEARNING OBJECTIVES
# How to do CT with dictionaries

def ct2(d,  key):
    while (key in d) and ((key+2) not in d):
        d[key+2] = key+1
        key = d[key]
    L = [   ]
    for key in  sorted(d.keys()):
        L.append(10*key + d[key])
    return  L

print(ct2({1:5, 0:2}, 0))


###############################################################################
# FindTriplets
###############################################################################
# LEARNING OBJECTIVES
# How do we solve a problem using sets and dictionaries?
# How do we write efficient code?

'''
Write the function findTriplets(L) that takes as input a list L of integers of 
length N and returns a set of all triplets in the list whose sum is equal to 0. 
For example, if the given list is [-1, 0, -3, 2, 1], you should return {(1, 0, -1), 
(-3, 2, 1)} (or any permutation of those numbers). If there is no valid triplet, you 
should return the empty set. You may assume that L is a list containing only integers. 
This must be written in N^2 time. 
'''

def findTriplets(L):
    return {42}


###############################################################################
# Dictionary ROC
###############################################################################
# LEARNING OBJECTIVES
# How do we solve dictionary ROC

def roc1Helper(d): 
    s = "" for key in d: 
        if key % 2 == 0: 
            s += d[key] 
    return s

def roc1(d): 
    assert(sorted(d.keys()) == list(range(0,4)))
    s = roc2Helper(d) 
    return s == "good luck!"