###############################################################################
# ---------------- 15-112 Recitation #18: Final Review 1 ---------------- #

# 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 :)

# --------------------------------------------------------------------------- #
###############################################################################
# Palindrome Partition
###############################################################################
# LEARNING OBJECTIVES
# Review Backtracking
'''
Write the function palindromePartition(s) that given an input string s, returns
 a 1D list L, such that every element of L is a palindromic string and furthermore, 
 all the strings in L concatenated together give the original string s or returns 
 None if such a solution does not exist. Note : We are only interested in meaningful 
 outputs. Note that for any string s, a trivial solution is to return the list L 
 of the individual characters in s. (strings of length 1 are palindromic by default) 
 Therefore your solution must not return a list of individual characters in s. 
 
 or example:
palindromePartition("geeks") == ["g", "ee", "k", "s"] # "ee" has length > 1 
palindromePartition("abcde") == None # only has the trivial solution 
palindromePartition("racecar") == ["racecar"] # whole word is a palindrome!

You must use recursive backtracking to solve this problem.

'''

def palindromePartition(s):
    return [42]


###############################################################################
# Sting ROC
###############################################################################
# LEARNING OBJECTIVES
# Review String ROC

def roc2(s):
    if not isinstance(s, str): return False
    if not s.isalpha(): return False

    enc = ''
    for i in range(len(s)):
        charEnc = '%d' % (ord(s[-1-i]) - ord('a'))
        if len(charEnc) > 1: return False
        enc += charEnc

    return int(enc[::-1]) == 43384


###############################################################################
# Big OH
###############################################################################
# LEARNING OBJECTIVES
# Review BIg OH

# What is the big OH of the following functions

def bigOh1(N):
    # assume N is an integer
    i = 3
    while(i**3 < N):
        i += 3
    return None

def bigOh2(L): 
# assume L is a list with N elements 
    X = len(L) 
    Y = [0] * 42 
    for val in L: 
        Y[val % 42] += 42 
    return set(L + sorted(Y))

def bigOh3(L): 
    N = len(L) 
    result = 0 
    for i in range(2N, N**2, 3): 
        if (i not in L): 
            for j in range(i, N): 
                result += (i * j)//N 
    return result



###############################################################################
# topFrequencies
###############################################################################
# LEARNING OBJECTIVES
# Review efficiency with sets/dictionaries

'''
Write the function topFrequencies(T, W), which takes in T, a string of text 
(which you may assume contains only lowercase letters and spaces), and W, a 
set of words we are interested in finding in the text T. This function should 
return a dictionary of the words in W with the top 5 frequencies in T. In this 
output, the keys are the integer frequencies and values are strings which are 
the word that has that corresponding frequency. If more than one word has that 
frequency, the value should be a set of those words instead. 

For example:
topFrequencies("a a is a letter a b is also a letter and a b is also is letter", 
{"a", "b", "c", "is", "and", "letter", "also"} ) == 
{ 6: "a", 4: "is", 3: "letter", 2: {"also", "b"}, 1: "and" }
topFrequencies("h a c k o n e t w e l v e i s a w e s o m e c c", 
{"a", "b", "c", "d", "e", "f", "g", "h", "i"} ) == 
{ 5: "e", 3: "c", 2: "a", 1: {"h", "i"}, 0: {"b", "d", "f", "g"} }

If the output dictionary would contain fewer than 5 key-value pairs, 
the function should return the largest possible frequency dictionary 
(typically consisting of all the words in W). One such scenario is when 
W or T contains fewer than 5 words.

topFrequencies("i love puzzles puzzles are super great", 
{"puzzles", "super", "love", "you"} ) == 
{ 2: "puzzles", 1: {"super","love"}, 0: "you" }

For full credit, your solution should run in O(N) time, where N is the 
length of the input text T. (Hint: note that therefore, your solution 
cannot depend on the number of elements in W.) 

'''

def topFrequencies(T, W):
    return {42:42}