###############################################################################
# ---------------- 15-112 Recitation # ---------------- #

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

# --------------------------------------------------------------------------- #
###############################################################################
# Farm Wars
###############################################################################
# LEARNING OBJECTIVES
# How do we use backtracking to solve a problem?

'''
You’re about to travel for summer vacation, so you need to pack up your stuff! 
However, you have so much stuff to bring home that you’ll need to use multiple bags. 
This is made more difficult by the fact that each item has a weight, and each bag has 
a maximum weight that it can handle- if a bag gets overloaded, it will break. Your 
task is to find a way to organize all of your items into all of your bags such that 
no item is left behind and no bag contains a heavier weight than its limit. Solve 
this problem by writing the function packItems(items, bagSizes). The function takes 
two lists: items, which is a list of the weights of all the items, and bagSizes, 
which is a list of the weight limits of all the bags. It should return a list of 
"bags", where a bag is a list of items (numbers). The bag list should be the same 
length as bagSizes, and each bag should not weigh more than the corresponding weight 
limit. For example, say you have two bags with weight limits of 12 and 9, and the 
following list of item weights: [4, 8, 1, 4, 3]. The function call for this would be
packItems([4, 8, 1, 4, 3], [12, 9])
and it would return
[ [4, 8], [1, 4, 3] ]
Note that the first bag sums to 12 (the first weight limit) while the second sums to 
8 (less than the second weight limit). There are other possible packings for this
 set of items; any valid packing is acceptable. If the provided bag sizes were instead 
 [10, 10], there would be no valid way to pack the bags; in that case, the function 
 should return None instead of a list of bags. You are guaranteed that item weights 
 and bag sizes will be non-negative.

'''

def packItems(items, bagSizes):
    return 42



###############################################################################
# Code Tracing
###############################################################################
# LEARNING OBJECTIVES
# How to solve recursive CT?
def f(n, d):

    print(d, n) 
    if  (n  <   1):
        return  2+abs(n)
    else:
        return  n   +   f(n-2, d+1)    +   f(n//2, d+1)
print(f(3, 0))



###############################################################################
# ROC
###############################################################################
# LEARNING OBJECTIVES
# How to solve recursive ROC?

def f(s,  m=1):
    t   =   str(m**2)
        if  (s  ==  ""):
           return  (m  ==  6)
        elif    (not    s.endswith(t)):
           return  False
        else:
           return  f(s[:len(s)-len(t)],  m+1)