Nth Egg Drop
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
const maxHeight = 5000;
const secretHeight = getSecretHeight(1, maxHeight);
var verbose = true;
function getSecretHeight( min, max ){
min = min || 1;
max = max || 100;
var result = Math.abs(( Math.random() * 1000 ) % max );
return Math.round( Math.max( min, result ), 1 );
}
function getOptimumIncrement( maxHeight ){
maxHeight = parseInt(maxHeight || 100 );
return Math.round(( Math.sqrt( 1 + 8*(maxHeight) ) - 1 )/2, 1);
}
function drop(height){
return height > secretHeight;
}
function passOne(){
var drops = 0;
var increment = getOptimumIncrement(maxHeight);
var height = 0;
var lastDrop = 0;
if(verbose) console.log( "Height : ", height, "; Last Drop : ", lastDrop, "; Increment : ", increment );
do{
height += increment;
increment--;
if(verbose) console.log( "Drop @ ", height );
if( !drop(height) ){
lastDrop = height;
drops++;
}
if(verbose) console.log( "Height : ", height, "; Last Drop : ", lastDrop, "; Increment : ", increment );
} while( !drop(height) && height < maxHeight && increment > 0 );
return{ height, lastDrop, drops };
}
function passTwo( parameters ){
var start = parameters.lastDrop + 1 || 0;
var end = parameters.height - 1 || 0;
var drops = 0;
var safeHeight = 0;
if( start && end ){
for( var i = start; start < end; i++ ){
if( drop(i) ){
safeHeight = --i;
break;
}
drops++;
}
}
console.log( "Safe Height found @ ", safeHeight, " after ", ( drops + ( parameters.drops || 0 ) ), " drops" );
return { safeHeight, drops : drops + ( parameters.drops || 0 ) };
}
console.log( "Max Height : ", maxHeight );
console.log( "Safe Height : ", secretHeight );
var passOneResults = passOne();
console.log( "First Pass Results : ", passOneResults );
var passTwoResults = passTwo(passOneResults);
console.log( "Second Pass Results: ", passTwoResults);
console.log( "Search Effeciency : ", ( ( maxHeight - passTwoResults.drops ) / maxHeight ) * 100 );
JavaScript
INFO