Egg Drop Problem

Egg_Drop


Given : n number of eggs. An egg could be dropped from any floor of a building having k floors.

Objective : Find the minimum number of attempts to find out the lowest floor in the building from which if the egg is dropped, would break.

  • An attempt consist of dropping an egg from any floor of the building.
  • If the egg does not break after dropping it from floor f, it would not break when dropped from the floors below f.
  • If the egg breaks after dropping from floor f, it would obviously break when dropped from the floors above f.
  • A broken egg cannot be used again.

Note: If all the eggs are broken while attempting to find out the threshold (bottom-most egg-breaking floor), we lose the information from previous attempts.



Example :
1 egg and 3 floors
If the building has 3 floors and we have just 1 egg, then in the worst-case we would need to drop the egg from each of the 3 floors to find out the bottom-most floor that would cause the egg to break.
[ 3 Attempts needed ]

2 eggs and 1 floor
If there is only 1 floor then it would take only 1 attempt for any ( N > 0 ) number of eggs.
Similarly, if there are no floors ( 0 floors ) then there would be 0 attempts.
[ 1 Attempt needed ]

2 eggs and 3 floors
Attempt 1 : We could be smarter by trying the middle floor i.e floor number 2.
If the egg doesn’t break we would go to floor 3.
    Attempt 2 : Drop the egg from floor 3 if it breaks, we know the threshold i.e floor 3.
Else If the egg breaks we would go to floor 1.
    Attempt 2 : Drop the egg from floor 1, if it breaks, we know the threshold i.e floor 1 if it doesn’t the threshold is floor 2.
[ 2 Attempts needed ]



The egg drop problem could be solved recursively as well as using dynamic programming. Egg_Drop

Recursion
int Egg_Drops ( eggs, floors )

    If ( eggs == 1 )
        return floors
    If ( floors == 0 or floors == 1 ) then
        return floors
    Initialize attempt = max number
    For the current_floor beginning with 1 upto floors
        There are 2 possibilities : Egg breaks or Egg doesn’t break
        attempt = min ( attempt, 1 + max [ EggDrops ( eggs - 1, current_floor - 1 ),
                                                             EggDrops ( eggs, floors - current_floor ) ] )
    return attempt

Time Complexity : The time complexity of the recursive algorithm is O ( 2 floors )



Dynamic Programming
int Egg_Drops ( eggs, floors )

    Create cache [ eggs + 1 ] [ floors + 1 ]

    Irrespective of the number of eggs, if there is only 1 floor, then it would take just 1 attempt.
    Similary if there are no floors ( 0 floors ), then it would take 0 attempts.
    For the egg e from 0 upto eggs
        cache [ e ] [ 0 ] = 0
        cache [ e ] [ 1 ] = 1

    If there is only 1 egg, then the attempts would same as the number of floors.
    Also if there are no eggs ( 0 eggs ) then there would be 0 attempts.
    For the floor f from 0 upto floors
        cache [ 1 ] [ f ] = f
        cache [ 0 ] [ f ] = 0

    For egg e from 2 upto eggs
        For floor f from 2 upto floors
              cache [ e ] [ f ] = max number
              For current_floor from 2 upto f
                     Attempts = 1 + max ( cache [ e - 1 ] [ current_floor - 1 ], cache [ e ] [ f - current_floor ] )
                     cache [ e ] [ f ] = min ( cache [ e ] [ f ], Attempts )
    return cache [ eggs ] [ floors ]

Time Complexity : The time complexity of the dynamic programming algorithm is O ( eggs . floors 2 )



C++ Finding the minimum egg drop attempts to find the threshold floor.

#include<algorithm>
#include<iostream>
#include<climits>
#include<map>

using namespace std;

int EggDrops (int eggs, int floors) {

    int cache[eggs+1][floors+1];

    // If there are no floors (i.e 0 floors) we would have zero attempts.
    // If there is only 1 floor, there would only be 1 attempt.
    for (int e=0; e<=eggs; e++) {
        cache[e][0] = 0;
        cache[e][1] = 1;
    }

    // If there is only 1 egg then we could need attempts 
    // same as the number of floors in worst case.
    // If there are 0 eggs, there would be 0 attempts.
    for (int f=0; f<=floors; f++) {
        cache[1][f] = f;
        cache[0][f] = 0;
    }

    /*
    floors  k   | 
            .   |
            .   |
            f   | <- If an egg breaks at floor f, then we would need to check the floors below 'f'
           f-1  |    to find the bottom-most floor from which an egg if dropped would break.
            .   |    i.e (f-1) floors with one less egg from available eggs.
            2   |    If the egg doesn't break, then we would need to check the floors above f
            1   |    i.e from floor f + 1 till n i.e (k-f) floors with the same number of eggs. 

        Note : If an egg breaks or it doesn't break, every drop is considered an attempt.
    */

    for (int e=2; e<=eggs; e++) {
        for (int f=2; f<=floors; f++) {
            cache[e][f] = INT_MAX;
            for (int current_floor = 2; current_floor <= f; current_floor++) {
                // On the current floor there are two possible scenarios (Egg breaks, Egg doesn't break).
                int attempts = 1 + max(cache[e-1][current_floor-1], cache[e][f-current_floor]);
                cache[e][f] = min(cache[e][f], attempts);
            }
        }
    }

    return cache[eggs][floors];
}

map<pair<int, int>, int> cache_map;
int EggDropsRec (int eggs, int floors) {

    if (eggs == 1)
        return floors;

    if (floors == 0 || floors == 1)
        return floors;

    if (cache_map.find(make_pair(eggs, floors)) != cache_map.end()) {
        return cache_map.find(make_pair(eggs, floors))->second;
    }

    int attempt = INT_MAX;
    for (int current_floor=1; current_floor<=floors; current_floor++) {
        // Two possibilities 
        // 1.Egg breaks 
        // 2.Egg doesn't break
        attempt = min(attempt, 1 + max(EggDropsRec(eggs-1, current_floor-1), EggDropsRec(eggs, floors-current_floor)));
    }
    cache_map.insert(make_pair(make_pair(eggs, floors), attempt));
    return attempt;
}

int main() {

    int eggs = 2, floors = 300;
    cout << "Dynamic Programming" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
    cout << "Recursion" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

    eggs = 5, floors = 100;
    cout << "\nDynamic Programming" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDrops(eggs, floors) << endl;
    cout << "Recursion" << endl;
    cout << "Eggs : " << eggs << " Floors : " << floors << " Attempts required : " << EggDropsRec(eggs, floors) << endl;

    return 0;
}

Output

Dynamic Programming
Eggs : 2 Floors : 300 Attempts required : 24
Recursion
Eggs : 2 Floors : 300 Attempts required : 24

Dynamic Programming
Eggs : 5 Floors : 100 Attempts required : 7
Recursion
Eggs : 5 Floors : 100 Attempts required : 7


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.