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

Open in new window

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

Open in new window

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

Open in new window

Any ideas?
LVL 2
CipherISAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
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.

mlmccCommented:
Try doing it for a smaller floors number.  Try 3 eggs and 10 floors
CipherISAuthor 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?
CipherISAuthor 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;
}

Open in new window

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
CipherISAuthor Commented:
Found the solution and posted it.
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.