//=============================================
//
// You have 2 light bulbs
// You are in an office building that is 100 stories high.
// Using the fewest possible number of drops from windows in your office building,
// determine the highest floor you can drop a lightbulb from and have it survive: for example,
// they might be able to take the drop from the 30th floor, but not the 31st.
// You can break both lightbulbs in your search.
// State the worst case number of drops needed and explain how you arrived at that answer.
//
//==============================================
//Includes
#include
#include
//Defines
//#define DISPLAY_DROPS
//==============================================
bool DropLightBulb( int nTestNumber, int nAnswer )
{
#ifdef DISPLAY_DROPS
std::cout << "Dropping LightBulb from Floor = " << nTestNumber << std::endl;
#endif
//Returns true if the lightbulb broke
return nTestNumber > nAnswer;
}
//==============================================
int CalculateHighestDropPoint( int nStartStep, int nAnswer, int nMaxFloors )
{
int nMainStepFloor = 0;
int nMainStepPreviousFloor = 0;
int nNumberOfDrops = 0;
int nFinalFloor = 0;
int nLastKnownValidDrop = 0;
do
{
//If the main step is equal to the max floors, and it still hasn't broken
//Then its impossible to break by dropping it from this building.
if( nMainStepFloor == nMaxFloors )
{
return nNumberOfDrops;
}
//Calculate the next floor to test
//Previous Dropped Floor + ( Last Step Size - 1 )
int nNextFloor = ( nMainStepFloor > 0 ) ? ( nMainStepFloor + ( ( nMainStepFloor - nMainStepPreviousFloor ) - 1 ) ) : nStartStep;
//Check to see if we exceeded the max floors
if( nNextFloor > nMaxFloors )
{
nNextFloor = nMaxFloors;
}
nMainStepPreviousFloor = nMainStepFloor;
nMainStepFloor = nNextFloor;
//Keep track of the number of steps
nNumberOfDrops++;
//Drop an LightBulb
}while( !DropLightBulb( nMainStepFloor, nAnswer ) );
//Increment by ones from nPrevousFloor + 1 to nMainStepFloor - 1;
nFinalFloor = nMainStepPreviousFloor;
do
{
//Save the last known good floor
nLastKnownValidDrop = nFinalFloor;
//This saves a step and a LightBulb from breaking
//nMainStepFloor is guaranteed to break
//nMainStepFloor - 1 didn't break so this is our answer
if( nFinalFloor == ( nMainStepFloor - 1 ) )
break;
//Increase the number of steps
nNumberOfDrops++;
//Try the next floor
nFinalFloor++;
//Continue testing until we break the next LightBulb, then we know the final floor
}while( !DropLightBulb( nFinalFloor, nAnswer ) );
printf( "The highest floor is %i \n", nLastKnownValidDrop );
return nNumberOfDrops;
}
//==============================================
int main( )
{
//My first thought was to use a binary method, but quickly I realized that results in a terrible worst case.
//Because I'd have to drop at 50 first, if that breaks, then I have to start from 1 and count up as high as 49.
//
//My next thought was break this up by 10%, something like 10, 20, 30, etc, and if it breaks at one of those increments
//then I would just start from the previous increment and go up by ones.
//This yields a best case of 3 and a worst case of 19.
//
//So after determining that any fixed step doesn't yield good enough results I moved to a method
//That uses the summation formula to solve the first step and then the next step is currentStep + ( lastStepSize - 1 )
//This yields a worse case of 14 and a best case of 3
//The number of stories we are dropping the LightBulb's from
const int nNumberOfFloors = 100;
//Solving the summation formula for ( n * ( n + 1 ) / 2 ) = nNumberOfStories
//Make this even simplier by just using ( n^2 / 2 ) = 100 or n^2 = 200, where n ~ 14
int nStartStep = 14;
while( true )
{
//Retrieve the highest floor that
//This just makes testing a ton eaiser
int nAnswer = 0;
std::cout << "Enter the floor (999 to quit): ";
std::cin >> nAnswer;
if( nAnswer == 999 )
{
break;
}
//Verify its in range
if( nAnswer > 0 && nAnswer <= nNumberOfFloors )
{
//This function returns the number of drops it took to discover the answer "nAnswer"
int nHighestDropPoint = CalculateHighestDropPoint( nStartStep, nAnswer, nNumberOfFloors );
std::cout << "Number of Drops to find highest drop point = " << nHighestDropPoint << std::endl;
}
//Just in case a string was entered instead
std::cin.clear( );
std::cin.ignore( );
}
return 0;
}