C# Egg Drop

I've been looking at the Egg Drop question, trying to solve it.  I found two code samples providing the solutions which I provided below.

The first solution GetDrops seems to just loop endlessly.
The second solution PerformEggDrop returns 2 which I don't believe is correct considering what I've read it should be 12 or 14.
``````        private static void TestEggDrop()
{
var x = EggDropSolution.GetDrops(2, 100);
var result = EggDropSolution.PerformEggDrop(100, 2);
}
``````
``````    public static class EggDropSolution
{
public static int PerformEggDrop(int n, int k)
{

/* A 2D table where entery eggFloor[i][j]
will represent minimum number of trials
needed for i eggs and j floors. */
int[,] eggFloor = new int[n + 1, k + 1];
int res;
int i, j, x;

// We need one trial for one floor and
// 0 trials for 0 floors
for (i = 1; i <= n; i++)
{
eggFloor[i, 1] = 1;
eggFloor[i, 0] = 0;
}

// We always need j trials for one egg
// and j floors.
for (j = 1; j <= k; j++)
eggFloor[1, j] = j;

// Fill rest of the entries in table
// using optimal substructure property
for (i = 2; i <= n; i++)
{
for (j = 2; j <= k; j++)
{
eggFloor[i, j] = int.MaxValue;
for (x = 1; x <= j; x++)
{
res = 1 + Math.Max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);
if (res < eggFloor[i, j])
eggFloor[i, j] = res;
}
}
}

// eggFloor[n][k] holds the result
var solution = eggFloor[n, k];
return solution;
}
}
``````
``````        public static int GetDrops(int eggs, int floors)
{
//base case 1:
//if floors = 0 then no drops are required OR floors = 1 then 1 drop is required
if (floors == 0 || floors == 1)
return floors;

//base case 2:
//if only one egg is there then drops = floors
if (eggs == 1)
return floors;

int minimumDrops = Int32.MaxValue;
int tempResult;
//check dropping from all the floors 1 to floors and pick the minimum among those.
//for every drop there are 2 scenarios - a) either egg will break b) egg will not break
for (int i = 1; i <= floors; i++)
{
//for the worst case pick the maximum among a) and b)
tempResult = Math.Max(GetDrops(eggs - 1, i - 1), GetDrops(eggs, floors - i));
minimumDrops = Math.Min(tempResult, minimumDrops);
}

return minimumDrops + 1;
}
``````
Any ideas?
LVL 2
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Try doing it for a smaller floors number.  Try 3 eggs and 10 floors
1
Author Commented:
I tried 2 eggs and 10 floors, also 20 floors.

PerformEggDrop still returns 2.
GetDrops gives me a different number which I'm expecting but when I change floors to 100 it is taking WAY TOO LONG.

Any idea what the solution is?
0
Author Commented:
Below is the solution.  Found it at https://algorithms.tutorialhorizon.com/dynamic-programming-egg-dropping-problem/.  Look at n^2 complexity.
``````public static int GetDrops(int eggs, int floors)
{
int [,] eggDrops = new int [eggs + 1, floors + 1];

//base case 1:
//if floors = 0 then no drops are required // OR floors = 1 then 1 drop is required
for (int i = 1; i <= eggs ; i++)
{
eggDrops[i,0] = 0;
eggDrops[i,1] = 1;
}

//base case 2:
//if only one egg is there then drops = floors
for (int i = 1; i <=floors ; i++)
{
eggDrops[1,i] = i;
}

for (int i = 2; i <= eggs ; i++) {
for (int j = 2; j <= floors ; j++) {
eggDrops[i,j] = Int32.MaxValue;
int tempResult;
for (int k = 1; k <=j ; k++) {
tempResult = 1 + Math.Max(eggDrops[i-1,k-1], eggDrops[i,j-k]);
eggDrops[i,j] = Math.Min(tempResult,eggDrops[i,j]);
}
}
}
// eggDrops[eggs][floors] will have the result : minimum number of drops required in worst case
var result = eggDrops[eggs,floors];;
return result;
}
``````
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
.NET Programming

From novice to tech pro — start learning today.