Quick actions

cmd+k|ctrl+k

Navigation

Languages

Nth Egg Drop

Snippet info

Language

JavaScript

Visibility

public

Author

horngyih

Created

2018-01-11T01:39:46Z

Updated

2018-01-11T01:39:46Z

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