Make the frequent cases fast and the rare case correct

EGG DROPPING PUZZLE – Dynamic Programming – C++

This is a famous puzzle that is solved by Dynamic programming approach using Memoization.

Firstly Let me introduce memoization :
It is a technique to optimize and make programs faster. This technique has found its use in dynamic programming as in lot of cases we need to store results (optimal substructures).memoizing avoids repeating the calculation of results for previously-processed inputs. More about Memoization here

Problem statement: Find the minimum number of trials required to determine the lowest floor in a building from which when we drop a egg it should NOT break. We need an algorithm that lowers the number of drops.

1. An egg that survives a fall can be used again.
2. A broken egg must be discarded.
3. The effect of a fall is the same for all eggs.
4. If an egg breaks when dropped, then it would break if dropped from a higher window.
5. If an egg survives a fall then it would survive a shorter fall.
6. It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor windows do not cause an egg to break.

The question becomes harder when we are given an option to use more than one number of eggs. Off course the floors vary as you test it on various buildings.

Solution: It easy when we have 1 egg for a 36 floor building. You need to break minimum 36 eggs to find out.

For N eggs with H floors
the dynamic state pair s = (n,k) can be defined
n = number of test eggs available, n = 0,1,2,3,…,N-1.
k = number of (consecutive) floors yet to be tested, k = 0,1,2,…,H-1.

Steps: let h be an arbitrary floor
Drop from floor h. If it breaks,test floors 1 to h-1 with e-1 eggs.
If it doesn’t break,test floors h+1 to f with e eggs
find worst case number of drops. since 1 drop already used.
find minimum over all floors

The functional equation for this problem:
W(n,k) := minimum number of trials required to identify the value of the critical floor under the Worst Case Scenario given that the process is in state s=(n,k).

it can be shown that
W(n,k) = 1 + min{max(W(n-1,x-1) , W(n,k-x)): x in {1,2,…,k}} , n = 2,…,N ; k = 2,3,4,…,H
with W(n,1) = 1 for all n>0 and W(1,k) = k for all k

Now, the above literature is same as in the Wikipedia article at Egg Dropping Puzzle .

Following is the implementation of the above functional equation.


#include <iostream>
using namespace std;
// Initialize maximum no of EGGs and floors
const int EGGS = 50;
const int FLOORS = 1000;

int array[EGGS+1][FLOORS+1];

//function to compute the trials
int omlette(const int e, const int f)
	// basic cases or rare cases only. i say such cases are rare as i like Manhattan
   	if (e == 1) return f;
   	if (f == 0) return 0;
   	if (f == 1) return 1;
   	// Memoization at work. to check if we have already calculated a value.
   	if ( array[e][f] >= 0 )
      		return array[e][f];

   	// initialize minimum number of drops to number of floors 
   	int min = f;
   	for (int n = 1; n <= f; ++n)
      		const int a = omlette(e-1, n-1);//drop from floor n. If it breaks,test floors 1 to n-1 with e-1 eggs.
      		const int b = omlette(e, f-n); // If it doesn't break,test floors n+1 to f with e eggs.
      		const int c = 1 + (a > b ? a : b);// find worst case number of drops. since 1 drop already used.
      		min = (c < min ? c : min); // minimum for all n.
	array[e][f] = min; // Memoization of the result

   return min;

int main()
	int e;
   	// for 1 egg check all floors . Making sure of the rare case
   	for (int f = 1; f <= FLOORS; ++f)
      		array[1][f] = f;
	for (e = 2; e <= EGGS; ++e) // making sure of the rare case
      		array[e][1] = 1; // With just 1 floor we only need one drop.
      		array[e][0] = 0; // With zero floors we don't need any drops.

   	// rest of array is made -1. Will be used later for computation. these are frequent cases
   	for (e = 2; e <= EGGS; ++e)
      		for (int f = 2; f <= FLOORS; ++f)
         		array[e][f] = -1;
      int eggs, floors;
      cout<<"Enter the Number of Eggs : \n";
      cin >> eggs;
      cout<<"Enter the Number of Floors : \n";
      cin >> floors;
      cout <<"The Minimum number of trials required is : "<< " " << omlette(eggs,floors) << endl;
   return 0;


laptop:~$ ./a.out
Enter the Number of Eggs :
Enter the Number of Floors :
The Minimum number of trials required is : 36

laptop:~$ ./a.out
Enter the Number of Eggs :
Enter the Number of Floors :
The Minimum number of trials required is : 3

Variation of the problem could be to find the exact lowest floor from which the egg can be dropped

Thanks for Reading !
If you liked this article please rate it.


2 responses to “EGG DROPPING PUZZLE – Dynamic Programming – C++

  1. Prateek October 30, 2014 at 8:42 pm

    Reblogged this on Random Things From an Engineer and commented:
    This is a helpful DP problem, with the explanation to boot. A famous interview question too!

  2. Pingback: Resources for Interviewing for a Tech Internship at Google and Facebook | Cyborg24: Tech Culture and Education

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: