#
Egg Drop Strategy

/*************************************************************************** * 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) { result.add(B[h]); } 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<>(); exp.add(Arrays.asList(5, 1)); exp.add(Arrays.asList(8, 4, 2)); exp.add(Arrays.asList(31, 15, 7, 3, 1)); 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); } } } }