# Egg Drop Strategyby Isai Damier, Android Engineer @ Google

```/***************************************************************************
* Author: Isai Damier
* Title: EggDropPuzzle
* Project: geekviewpoint
* Package: algorithms.dynamic.programming
*
* Description:
*   While eggs are fragile, there are heights from which a fallen egg will
*   not break. If you are given a measuring tape and a carton of eggs, can
*   you devise a strategy for finding the breaking height of the eggs using
*   the fewest trials possible?
*   A few constraints:
*    1] If you drop an egg and it didn't break, you can reuse it:
*       it's as good as new.
*    2] The eggs are completely interchangeable: same chemical
*       and mechanical structure.
*    3] You are guaranteed the eggs will break within the range of the
*       measuring tape, that is 1 <= B <= h, where B is the breaking height
*       and h is the length of the measuring tape.
*
* Solution approach:
*   1] If you have zero eggs, then the problem is unsolvable.
*   2] If you have one egg, the problem becomes trivial: you simply must
*      try all the heights starting with the lowest. If the tape is 15
*      centimeters tall, you must start at 1cm, then 2cm, then so on. If
*      after reaching 5cm you decide to skip to 7cm and the egg breaks, you
*      won't know if it would have broken at 6cm.
*   3] If you have two eggs, things get a bit tricky. You must drop the
*      first egg from a height x such that if it breaks, you can apply
*      step 2 the minimum number of times; and if it does not break, you
*      can re-apply step 3 the minimum number of times.
*
* Formulation:
*   Let P(n,h) means you have n eggs and a tape of height h. Then dropping
*   1 egg from some height x (1<=x<=h) has two possible effects:
*   a) if it breaks, then the problem becomes P(n-1,x-1):
*     You lost 1 egg and must test all the heights below x.
*   b) if it does not break, the problem becomes P(n, h-x):
*     you lost no egg but must test all the heights above x.
*
*   On the bright side, whether the egg breaks or not, "you will have
*   reduced the problem to a smaller problem whose solution you can use
*   toward solving the original problem." The quoted text is the description
*   of dynamic programming. Therefore we will use dynamic programming
*   to solve the problem.
*
*   So how do you select height x? Use brute force: try all heights from 1
*   to h, then pick the one which gives the minimum worst case drops:
*
*     for(int x=1; x<h; x++)
*       best = Math.min(best, Math.max(P(n-1,x-1),P(n,h-x)))
*
*   Why Math.max(P(n-1,x-1),P(n,h-x))? because you are looking for the worst
*   case drop of each x. Once you get all the worst case drops, then you
*   can choose the smallest one.
*
* Program:
*   P(int e, int h) {
*	    if(1 >= e) return h;//base case
*	    if(1 >= h) return 1;//base case
*	    int best = h+1;//h+1 is infinity
*	    for(int x=1; x < h; x++) {
*	      best = Math.min(best, Math.max(P(e-1,x-1),P(e,h-x)));
*	    }
*	    return best+1;
*	  }
**************************************************************************/
package algorithms.dynamic.programming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class EggDropPuzzle {

/*************************************************************************
* Function: dropStrategy
* @param
*     e: number of eggs
*     h: length to test
*
* Description: Given e eggs and a range of 1 to h, determine a worst case
*   strategy for dropping the eggs so that the total number of trials is
*   minimized. The result is one of many possible equivalent worst case
*   sequences.
*
* Technical Details:
*   This algorithm is an augmented version of numberOfDrops. The presented
*   strategy is based on the observation that of the worst cases, one will
*   always assume the eggs break until the last one is left to follow a
*   simple linear pattern. Recall that when the egg breaks, the resulting
*   problem is P(e-1, x-1). For any given h, B[h] is the height from which
*   to drop the first egg such that the number of total drops is optimum.
*   Hence, P can be rewritten as P(e-1,B[h]-1).
************************************************************************/
public List<Integer> dropStrategy(int e, int h) {
int[] B = new int[h + 1];
Arrays.fill(B, -1);
int[][] memo = new int[e + 1][h];
for (int x = 0; x <= e; x++) {
for (int y = 0; y < h; y++) {
memo[x][y] = Integer.MAX_VALUE;// infinity could also be s+1
}
}
List<Integer> result = new ArrayList<>();
while (0 < e) {
dropStrategy(e, h, memo, B);
if (B[h] != -1) {
} else {
break;
}
e--;
h = B[h] - 1;
}
return result;
}//dropStrategy

/*************************************************************************
* Function: dropStrategy
* @param
*     e: number of eggs
*     h: length to test
*     memo: table to memoize results to subproblems.
*     B: array to track the height from which to drop the first
*        egg for optimum result.
*
* Description: This is the recursive portion of the dropStrategy algorithm.
*   It is an augmented version of the recursive portion of numberOfDrops.
*
* Technical Details:
*   numberOfDrops is modified to track the height
*   x that yields the least number of drops for a given h.
************************************************************************/
private int dropStrategy(int e, int h, int[][] memo, int[] B) {
if (1 >= e) {
return h;
}
if (1 >= h) {
return 1;
}
int best = h + 1;// infinity
for (int a, b, x = 1; x < h; x++) {
if ((a = memo[e - 1][x - 1]) == Integer.MAX_VALUE) {
a = dropStrategy(e - 1, x - 1, memo, B);
}
if ((b = memo[e][h - x]) == Integer.MAX_VALUE) {
b = dropStrategy(e, h - x, memo, B);
}
b = Math.max(a, b);
if (best > b) {
B[h] = x;
best = b;
}
}
if (h < memo[0].length) {
memo[e][h] = best + 1;
}
return best + 1;
}//dropStrategy
}```
```package algorithms.dynamic.programming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class EggDropPuzzleTest {

/**
* Test of dropStrategy method, of class EggDropPuzzle.
*/
@Test
public void testDropStrategy() {
System.out.println("dropStrategy");
EggDropPuzzle eggDrops = new EggDropPuzzle();
List<List<Integer>> exp = new ArrayList<>();
for (int i : eggDrops.dropStrategy(2, 15)) {
if (!exp.get(0).contains(i)) {
fail("result does not contain " + i);
}
}
for (int i : eggDrops.dropStrategy(7, 15)) {
if (!exp.get(1).contains(i)) {
fail("result does not contain " + i);
}
}
for (int i : eggDrops.dropStrategy(5, 150)) {
if (!exp.get(2).contains(i)) {
fail("result does not contain " + i);
}
}
}
}```