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: MEDIUM_HARD
Tags: Dynamic programming

Complete search

Ad-hoc
Skill types: Dynamic programming

Complete search

Starter code:
def solve(emulator):
	

Solutions:
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


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


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
	minFloor = 0
	print(next_jump(num_eggs + 1, num_drops + 1))
	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 = minFloor
			else:
				minFloor = currFloor
		else:
			num_drops = emulator.drops
			num_eggs = emulator.eggs
			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
			else:
				minFloor = currFloor
	return currFloor + 1

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


from functools import lru_cache

@lru_cache(maxsize=None)
def highest_floor(eggs, 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):
	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):
			eggs -= 1
			if eggs == 0 or drops == 0:
				return n
		else:
			lower_bound = n
	return n + 1