###############################################################################
# ------------------ 15-112 Recitation 13: Recursion Part 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 :)

# --------------------------------------------------------------------------- #

###############################################################################
# Inheritance Notes
###############################################################################
#Specifying a Superclass
class A(object):
    def __init__(self, x):
        self.x = x
    def f(self):
        return 10*self.x

class B(A):
    def g(self):
        return 1000*self.x

#print(A(5).f()) 
#print(B(7).g()) 
#print(B(7).f()) 
#print(A(5).g()) 

#Overriding methods
class A(object):
    def __init__(self, x):
        self.x = x
    def f(self):
        return 10*self.x
    def g(self):
        return 100*self.x

class B(A):
    def __init__(self, x=42, y=99):
        super().__init__(x) # call overridden init!
        self.y = y
    def f(self):
        return 1000*self.x
    def g(self):
        return (super().g(), self.y)

a = A(5)
b = B(7)
#print(a.f()) 
#print(a.g()) 
#print(b.f()) 
#print(b.g()) 


#IsInstance vs Type
class A(object): pass
class B(A): pass
a = A()
b = B()
#print(type(a) == A) 
#print(type(b) == A) 
#print(type(a) == B) 
#print(type(b) == B) 
#print()
#print(isinstance(a, A)) 
#print(isinstance(b, A)) 
#print(isinstance(a, B)) 
#print(isinstance(b, B)) 

#Monster Demo
class Monster(object):
    def __init__(self):
        pass

    def attack(self): # returns damage to be dealt
        pass

    def defend(self, damage): # does damage to self
        pass

# In this class, we'll partially overwrite the init method, and make a new, class-specific method
class MagicMonster(Monster):
    def __init__(self):
        pass
        
    def heal(self): # only magic monsters can heal themselves!
        pass

# In this class, we'll overwrite a specific method
class NecroMonster(Monster):
    def attack(self): # NecroMonsters can attack even when 'killed'
        pass

###############################################################################
# CT
###############################################################################
# LEARNING OBJECTIVES
# How do we approach recursive CT problems?
# How do we debug recursive problems using depth?
# What does the computer do during recursion?

def f(x, d):
    print(" "*d, "f(%d)" % x)
    if (x < 3):
        result = 3
    else:
        result = 2*f(x-2, d+1)+ f(x-3, d+1)
    print(" "*d, "-->", result)
    return result

# print(f(5, 0))

###############################################################################
# hasSubsetSum
###############################################################################
# LEARNING OBJECTIVES
# How do we approach recursive problems?
# How do we handle multiple recursive calls?

'''
Write the function hasSubsetSum(L, tgt) that takes a target number tgt and a
list L of integers, and returns True if a subset of L’s elements sums to tgt.
For example:
L = [1, 3, 4]
hasSubsetSum(L, 3) # True
hasSubsetSum(L, 8) # True
hasSubsetSum(L, 0) # True, for any list
hasSubsetSum(L, 9) # False
'''
def hasSubsetSum(L, tgt):
    return False

def testHasSubsetSum():
    L = [1, 3, 4]
    assert(hasSubsetSum(L, 3))
    assert(hasSubsetSum(L, 8))
    assert(hasSubsetSum(L, 0))
    assert(not hasSubsetSum(L, 9))