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.

Notes:

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

where

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:

For,

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.

**IMPLEMENTATION** : C++

#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;
}

OUTPUT:

laptop:~$ ./a.out

Enter the Number of Eggs :

1

Enter the Number of Floors :

36

The Minimum number of trials required is : 36

laptop:~$ ./a.out

Enter the Number of Eggs :

2

Enter the Number of Floors :

6

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.

xkcd

### Like this:

Like Loading...

*Related*

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!

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