Dropping marbles from the building until they break.

marble_puzzle.js

// Minimize the number of drops required in the worst case and return [floor, drops] -
// the floor we should choose and the number of drops we'll have to make in the
// worst case.
function minMaxDrops(buildingHeight, marbles, cache) {
    if (marbles == 0) {
        return [0, Infinity];
    }

    if (marbles == 1) {
        // If we have just 1 marble, the only option is to start at the bottom floor
        // and go upwards. In the worst case we'll have to visit all floors.
        return [1, buildingHeight];
    }

    if (buildingHeight < 2) {
        // 0-story building: 0 drop required
        // 1-story building: 1 drop required
        return [buildingHeight, buildingHeight];
    }

    cache = cache || [];
    cache[marbles] = cache[marbles] || [];
    if (cache[marbles][buildingHeight]) {
        return cache[marbles][buildingHeight];
    }

    // Compute the worst-case scenario for each floor, and select the floor with the
    // best worst-case scenario.
    var bestFloor = null;
    var minDropsRequired = Infinity;
    for (var floor = 1; floor <= buildingHeight; floor++) {
        // Is it worse if the marble breaks, or if it doesn't?
        // Find the biggest number of drops required in each case.
        var dropsRequired = 1 + Math.max(
            minMaxDrops(floor - 1, marbles - 1, cache)[1], // if it breaks
            minMaxDrops(buildingHeight - floor, marbles, cache)[1] // if it doesn't
        );

        if (dropsRequired < minDropsRequired) {
            bestFloor = floor;
            minDropsRequired = dropsRequired;
        }
    }

    cache[marbles][buildingHeight] = [bestFloor, minDropsRequired];
    return cache[marbles][buildingHeight];
}