In this kata you must determine the lowest floor in a building from which you cannot drop an egg without it breaking. You may assume that all eggs are the same; if one egg breaks when dropped from floor `n`, all eggs will. If an egg survives a drop from some floor, it will survive a drop from any floor below too. 

You are given `num_eggs` eggs and are allowed to make a maximum of `num_drops` drops. If an egg does not break when dropped, it may be reused. You may assume that it is feasible to determine the floor with the given number of eggs and drops.

Example 1: 
You are given 1 egg and 10 drops. You start by dropping the egg from the first floor (floor numbering starts at 1). If it breaks, the answer is 1. If it does not break, you drop it from the second floor. If it breaks, the answer is 2. Otherwise you continue in the same manner until you reach a floor where the egg breaks. You may assume that you will reach that floor before you have exhausted your drops (i.e., in this example, the egg will break when dropped from floor 10 or lower).

Example 2: You are given 2 eggs and 10 drops. The highest floor for which this problem has a solution is floor 55, so you may assume that the answer is floor 55 or a lower floor. You will have to determine how the number 55 is derived and generalize it for any number of eggs and drops.

To solve this problem, you need to write a function `solve` that takes an argument `emulator` and returns the lowest floor from which an egg will break if dropped. The `emulator` object has the following properties and method which you may invoke:

  1. `emulator.eggs` returns the number of eggs you have left. You may use this property to detemine the number of eggs you are given initially.
  2. `emulator.drops` returns the the number of drops you have left. You may use this property to detemine the number of drops you are given initially.
  3. `emulator.drop(n)` returns `True` if an egg dropped from floor `n` breaks and `False` if it does not break. The number of times that you may invoke this method is limited to the number of drops you were given. If invoked after no drops are left, it will throw an exception. Same happens if you invoke this method after all your eggs are broken. 

You are not allowed to access any other method or state attribute of the `emulator` object, even if you can. This is considered cheating and is a very dishonorable thing to do! Note that `emulator.__dict__` has been disabled. 

Note: [This kata](http://www.codewars.com/kata/faberge-easter-eggs-crush-test) is similar although not the same.

Difficulty: interview

Starter code:

def solve(emulator):
	

Solutions:
#THanks to easter eggs kata ;*

def height(n, m):
    if n >= m:
        return (2 ** (min(n, m)) - 1)
    f = 1
    res = 0
    for i in range(n):
        f = f * (m - i) // (i + 1)
        res += f
    return res

def solve(emulator):
    m = emulator.drops
    n = emulator.eggs
    h = 0
    tryh = 0
    while n and m:
        tryh = height(n - 1, m - 1) + 1
        if emulator.drop(h + tryh):
            n -= 1
        else:
            h += tryh
        m -= 1
    return(h + 1)
    # continue here


def solve(emulator):

    def max_height(eggs, drops):
        if eggs == 0 or drops == 0: return 0
        return max_height(eggs - 1, drops - 1) + 1 + max_height(eggs, drops - 1)

    low = 1
    high = max_height(emulator.eggs, emulator.drops)
    while low <= high:
        n = min(low + max_height(emulator.eggs - 1, emulator.drops - 1), high)
        if emulator.drop(n): high = n - 1
        else: low = n + 1
    return low


def max_floor(eggs, drops):
    return sum(max_floor(eggs-1, d) + 1 for d in range(drops)) if eggs else 0

def solve(emulator):
    floor = 1
    while emulator.eggs and emulator.drops:
        while emulator.drops:
            test = floor + max_floor(emulator.eggs-1, emulator.drops-1) + 1
            if emulator.drop(test): break
            floor = test
    return floor+1


def solve(emulator):
    num_drops = emulator.drops
    num_eggs = emulator.eggs
    floor = 0

    def height(eggs, drops):
        max_floor = 0
        if eggs <= 0: return 0
        elif eggs == 1: return drops
        else:
            for x in range(1,drops+1):
                max_floor += height(eggs - 1, drops - x) + 1
            return max_floor

    while num_drops and num_eggs:
        temp = height(num_eggs - 1, num_drops -1) + 1
        if not emulator.drop(floor + temp):
            floor += temp
            num_drops -= 1
        else:
            num_eggs -= 1
            num_drops -= 1

    return floor + 1

def solve(emulator):
    num_drops = emulator.drops
    num_eggs = emulator.eggs
    #generate table for max heights with certain numbers of eggs and drops
    HEIGHTS = heights(num_eggs, num_drops)
    return solve_part(emulator, 0, HEIGHTS[num_eggs][num_drops], HEIGHTS)+1
    
    
def solve_part(emulator, min_floor, max_floor, HEIGHTS):
    #solve for the highest possible floor without breaking
    if min_floor == max_floor:
        return min_floor
    else:
        num_drops = emulator.drops
        num_eggs = emulator.eggs
        partition = HEIGHTS[num_eggs-1][num_drops-1]
        partition_point = min_floor + partition + 1
        if emulator.drop(partition_point):
            return solve_part(emulator, min_floor, partition_point-1, HEIGHTS)
        else:
            return solve_part(emulator, partition_point, max_floor, HEIGHTS)
        
def heights(n, m):
    heights = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            heights[i][j] = heights[i-1][j-1] + heights[i][j-1] + 1
    return heights




from functools import lru_cache

@lru_cache(None)
def T(n,k):
    return 0 if n==0 or k==0 else T(n-1,k-1)+1+T(n-1,k)

def solve(e):
    d={0:False}
    floormax=0
    while e.eggs>0 and e.drops>0:
        n=floormax+1+T(e.drops-1,e.eggs-1)
        d[n]=t=e.drop(n)
        if not t:floormax=n
    return min([k for k,v in d.items() if v])

flockhash={}

def solve(emulator):

    num_drops = emulator.drops
    num_eggs = emulator.eggs
    
    def climbing(eggs,drops):
    
        if eggs==1 : return 1
        everest=flockhash.get((eggs,drops))
        if everest!=None : return everest
        everest=1
        for kamikaze in range(1,drops):
            everest+=climbing(eggs-1,drops-kamikaze) 
        flockhash[(eggs,drops)]=everest
        return everest
        
    last_broken_egg=1
    floor=1+climbing(num_eggs,num_drops)
    exfloor=1
    
    while num_eggs and num_drops :
        
        if emulator.drop(floor) : 
            last_broken_egg=floor
            num_eggs-=1
            floor=exfloor
        else:
            exfloor=floor
            
        num_drops-=1
        floor+=climbing(num_eggs,num_drops)
    else:
    
        return last_broken_egg
        
        
        
        
        
        

                



#better solution exist?
flockhash={}

def solve(emulator):

    num_drops = emulator.drops
    num_eggs = emulator.eggs
    
    def climbing(eggs,drops):
    
        if eggs==1 : return 1
        everest=flockhash.get((eggs,drops))
        if everest!=None : return everest
        everest=1
        for kamikaze in range(1,drops):
            everest+=climbing(eggs-1,drops-kamikaze) 
        flockhash[(eggs,drops)]=everest
        return everest
        
    last_broken_egg=1
    floor=1+climbing(num_eggs,num_drops)
    exfloor=1
    
    while num_eggs and num_drops :
        
        if emulator.drop(floor) : 
            last_broken_egg=floor
            num_eggs-=1
            #num_drops-=1
            floor=exfloor#+climbing(num_eggs,num_drops)
        else:
            #num_drops-=1
            exfloor=floor
            #floor+=climbing(num_eggs,num_drops)
            
        num_drops-=1
        floor+=climbing(num_eggs,num_drops)
    else:
    
        return last_broken_egg
        
        
        
        
        
        

                



def solve(emulator):
    print("Drops")
    print((emulator.drops))
    num_drops = emulator.drops
    print("Eggs")
    print((emulator.eggs))
    num_eggs = emulator.eggs
    currFloor = 0
    broke = False
    maxFloor = -1#initial state
    minFloor = 0
    #print(find_sum_to_current(num_drops))
    print((next_jump(num_eggs + 1,num_drops + 1)))
    
    #make max floor based on eggs to the power of dropc count ( -1, -1)
    #then do lion in desert based on the new range - calc is a little different, must think of cases where eggs always break
    while emulator.drops > 0 and  emulator.eggs > 0:
        if emulator.eggs == 1:         
            currFloor += 1
            print(currFloor)
            broke = emulator.drop(currFloor)
            if broke:
                return currFloor
            else:
                minFloor = currFloor
        elif emulator.eggs == 2:
            currFloor += emulator.drops
            print(currFloor)
            broke = emulator.drop(currFloor)
            if broke:
                maxFloor = currFloor
                #currFloor = maxFloor - emulator.drops * (emulator.eggs)
                currFloor = minFloor #+ emulator.eggs
            else:
                minFloor = currFloor
        else:
            num_drops = emulator.drops
            num_eggs = emulator.eggs
            #currFloor += 1 + maxFindRange((num_eggs - 1,num_drops - 1)#maybe +1 
            currFloor += next_jump(num_eggs, num_drops)
            print(("up  by: " + str(next_jump(num_eggs,num_drops)) + " eggs: " + str(num_eggs) + " drops: " + str(num_drops)))
            print(currFloor)
            broke = emulator.drop(currFloor)
            if broke:
                maxFloor = currFloor
                currFloor = minFloor #+ emulator.eggs
            else:
                minFloor = currFloor
    return currFloor + 1
    
    

    
    
#def maxFindRange(eggCount, dropCount):
#    if eggCount >= dropCount:
#        return dropCount#find_sum_to_current(dropCount)#dropCount + 1
#    elif eggCount == 1:
#        return dropCount
#    elif eggCount == 2:
#        return find_sum_to_current(dropCount)
#    else:
#        number = 0#maybe 0 or 1
#        for i in range (1, dropCount + 1):
#            #number += (eggCount - 2) * (find_sum_to_current(dropCount - i - 1) - 1)
#            number += #1 + (eggCount - 2) * (find_sum_to_current(dropCount - i - 1))
#            #solve for negative numbers
#        return number + maxFindRange(eggCount - 1, dropCount - 1)
#    #returns the highest amount that can be tested
        
def find_sum_to_current(dropCount):
    number = 0
    for i in range (1, dropCount + 1):
        number += i
    return number
    
def next_jump(num_egg, num_drop):
    if num_egg == 1 or num_drop == 1:
        return 1
    else:
        sum = 0
        for i in range (0, num_drop):
            sum += next_jump(num_egg - 1, i)
        if(num_egg > 2):
            sum+=1
        return sum
    
    
    # continue here


from functools import lru_cache


@lru_cache(maxsize=None)
def highest_floor(eggs, drops):
    """Return the highest floor for the given numbers of eggs and drops"""
    if eggs > drops:
        eggs = drops
    if eggs <= 1:
        return drops if eggs == 1 else 0
    return highest_floor(eggs-1, drops-1) + 1 + highest_floor(eggs, drops-1)


def solve(emulator):
    """Return the least floor for which the egg breaks"""
    drops = emulator.drops
    eggs = emulator.eggs

    lower_bound, n = 0, 0
    while drops > 0:
        n = lower_bound + highest_floor(eggs-1, drops-1) + 1
        drops -= 1
        if emulator.drop(n): # it broke for floor n
            eggs -= 1
            if eggs == 0 or drops == 0:
                return n
        else:
            lower_bound = n
    return n + 1