Egg Drop Experiment: Number of Drops
by Isai Damier

/***************************************************************************
 * 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: numberOfDrops
   * @param
   *     e: number of eggs
   *     h: length to test
   *
   * Description: Find the fewest number of drops necessary to
   *   determine the breaking height of the given eggs.
   *
   * Technical Details:
   *   While program P above is sufficient to solve the problem, it is quite
   *   inefficient. It is generally good instinct to suspect any dynamic
   *   programming algorithm that does not use memoization. Memoization
   *   simply means using a memo to remember subproblems you have already
   *   solved so you don't waste time solving them again. The following
   *   algorithm augments memoization to P for a more efficient solution.
   *
   *   1] create a table to memoize results.
   *   2] call recursive eggDrop with e, h, and the table to
   *      get the optimum number of drops necessary.
   ************************************************************************/
  public int numberOfDrops(int e, int h) {
    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
      }
    }
    return numberOfDrops(e, h, memo);
  }//numberOfDrops

  /******************************************************************
   * Function: numberOfDrops
   * @param
   *     e: number of eggs
   *     h: length to test
   *     memo: table to memoize results to subproblems.
   *
   * Description: This is the recursive portion of the eggDrop algorithm.
   *
   * Technical Details:
   *    Remember the guarantee that the eggs will break within the
   *    range of the measuring tape (constraint #3).
   *
   *   1] if there is only one egg, then the worse case is to
   *      test each grade from 1 to h. So just return h.
   *   2] if there is only one grade to test (i.e. h=1), then it
   *      must be the optimal solution. Simply return 1.
   *   3] initialize variable 'best' to infinity.
   *   4] for each height x from 1 to h
   *      a) using either the memoized or the computed
   *         value, get the greater of numberOfDrops(e-1,i-1)
   *         and numberOfDrops(e,h-i)
   *      b) if the value in part-a is less than 'best', assign
   *         it to best.
   *   5] memoize the result as best+1. Plus 1 recognizes the
   *      present height, since the for loop excluded it.
   *   6] return the result as best+1.
   ****************************************************************/
  private int numberOfDrops(int e, int h, int[][] memo) {
    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 = numberOfDrops(e - 1, x - 1, memo);
      }
      if ((b = memo[e][h - x]) == Integer.MAX_VALUE) {
        b = numberOfDrops(e, h - x, memo);
      }
      best = Math.min(best, Math.max(a, b));
    }
    if (h < memo[0].length) {
      memo[e][h] = best + 1;
    }
    return best + 1;
  }//numberOfDrops
}
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 numberOfDrops method, of class EggDropPuzzle.
   */
  @Test
  public void testNumberOfDrops() {
    System.out.println("numberOfDrops");
    EggDropPuzzle eggDrops = new EggDropPuzzle();
    int[][] result = {{1, 1, 1, 2}, {2, 3, 2, 2}, {4, 6, 3, 2},
      {7, 10, 4, 2}, {11, 15, 5, 2}, {16, 21, 6, 2},
      {22, 28, 7, 2}, {29, 36, 8, 2}, {37, 45, 9, 2},
      {46, 55, 10, 2}, {56, 66, 11, 2}, {67, 78, 12, 2},
      {79, 91, 13, 2}, {92, 105, 14, 2}, {106, 120, 15, 2},
      {121, 136, 16, 2}, {137, 153, 17, 2}, {154, 171, 18, 2},
      {172, 190, 19, 2}, {191, 200, 20, 2}, {16, 31, 5, 5},
      {32, 62, 6, 5}, {63, 119, 7, 5}, {120, 153, 8, 5},
      {32, 63, 6, 8}, {64, 127, 7, 8}, {128, 182, 8, 8}};
    for (int[] R : result) {
      for (int s = R[0]; s <= R[1]; s++) {
        int x = eggDrops.numberOfDrops(R[3], s);
        if (R[2] != x) {
          fail(" Floor " + R[0] + ": expected " + R[2] + " found "
                  + x);
        }
      }
    }
  }
}