Background

The Egg Drop Problem - A Functional Javascript Solution

September 08, 2018

In the egg drop problem, we imagine that we are trying to see the highest floor from which an egg, when dropped, will not break. This problem is only interesting when we are given more than one (identical) egg. With one egg, the solution is simple; you have to try dropping it from ever floor, as you cannot reuse an egg once it has been dropped.

The problem as I've approached it deals with two identical eggs. Because we have two eggs, we can be a litle more careless with the first. In my solution, we drop the first egg once every ten floors, and once it breaks, go back to the last safe floor, and go up one at a time from there. This allows us to skip quite a lot of floors. 10 isn't always the ideal number of floors to increment for the first egg, but, I don't address that here. The information on that is available elsewhere.

My solution to this problem is recursive and functional, at least, to the extent that javascript is held to be functional. It does not mutate state.

const generateEggBreak = breakNumber => checkNumber =>
  checkNumber >= breakNumber

const getEggBreakFloor = (
    maxFloor,
    eggBreakFunction,
    lastFloor,
    stepSize,
    maxBreaks,
    breaks=0,
    attempts=1
) => {
    if (breaks >= maxBreaks) {
        return [lastFloor, false, attempts];
    }

    if (lastFloor >= maxFloor) {
        return [-1, false, attempts];
    }

    const thisFloor = lastFloor + stepSize

    if (eggBreakFunction(thisFloor)) {
        return stepSize === 1 ?
            [thisFloor, true, attempts] :
            getEggBreakFloor(
                maxFloor,
                eggBreakFunction,
                thisFloor - stepSize,
                1,
                maxBreaks,
                breaks + 1,
                attempts+1,
            )
    }

    return getEggBreakFloor(
        maxFloor,
        eggBreakFunction,
        thisFloor,
        stepSize,
        maxBreaks,
        breaks,
        attempts+1,
    )
}

const maxFloor = 100
const breakFloor = Math.ceil(Math.random() * maxFloor)
const eggBreak = generateEggBreak(breakFloor)
const initialFloor = 0
const maxBreaks = 5

const result = getEggBreakFloor(
    maxFloor,
    eggBreak,
    initialFloor,
    10,
    maxBreaks,
)

console.log(`
    The maximum floor for the egg is ${result[0]}.
    This is${result[1] ? '' : ' not'} an exact result.
    It was found in ${result[2]} attempts.
`)