Dynamic programming to reach a threshold?

Question

Say you're working on a resilient laptop. Let's also say you have a hydraulic press that has power i, with a setting m (max power) that breaks the laptop. If the laptop breaks at power i, then it will also break for anything i to m. If it doesn't break at power i, this will not break for anything 0 to i.

---

I figure the best way to minimize the number of times we need to use the press in order to figure out what i is, is to divide in half and keep repeating. Go higher if it doesn't break, go lower if it does break. I figure the complexity for this is O(n/2), is that right?

---

Now say that we only have n laptops available, and if all n break before we reach the threshold, then we've failed. How would I get a dynamic programming algorithm so that we can get the minimum number of times the press has to run in the worst case, if we have n laptops and the press has m settings?

Would I be able to use the answer to the non-constricted way? What would the subproblems be?

Answer 1

The first problem can indeed be solved by first trying at m/2, and depending on the result try m/4 or 3m/4, ...etc. This makes the problem O(log(m)), not O(m/2) (I suppose the n was a typo).

The second version is also known as the egg dropping problem.

A recursive function can help to find the number of attempts. To avoid recalculation of the same configuration twice, you can indeed use dynamic programming. And where you have enough laptops to perform the binary search (take the middle pressure and depending on the result take the middle of the remaining pressures, ...etc), stop the recursion and just return the logarithm (base 2) (not half!) of the remaining number of pressures.

Here is an implementation in basic JavaScript:

function getLeastAttempts(numPressures, numLaptops) {
    var memo = {}; // Storage for known results (dynamic programming)

    function best(numPressures, numLaptops) {
        var result, numMinAttempts, numAttempts, pressure;
        // If no pressures available, we need no more attempts
        if (numPressures <= 0 || numLaptops <= 0) return { numAttempts: 0 };
        // We ccould apply each pressure from low to high to minimise damage;
        //   this represents an upper limit to the minimum number of attempts we need:
        result = {
            numAttempts: numPressures,
            firstAttemptAtPressure: 1
        };
        // If we cannot to afford losing another laptop without finding out the
        //    answer, then that is what we will have to do: from low to high:
        if (numLaptops == 1) return result;
        // Otherwise check if we have calculated this before
        if (memo[numLaptops] && memo[numLaptops][numPressures])
            return memo[numLaptops][numPressures];
        // Otherwise if we have enough laptops for doing a binary search:
        if (2**numLaptops > numPressures) return {
            numAttempts: Math.floor(Math.log2(numPressures)) + 1,
            firstAttemptAtPressure: Math.floor(numPressures / 2)
        };
        // Otherwise, apply recursion to find out the least number of attempts
        for (pressure = 0; pressure < numPressures; pressure++) {
            // Applying this pressure to the laptop can have 2 results, take the worst
            //    of the two and add one for representing this attempt:
            numAttempts = 1 + Math.max(
                // 1. It breaks the laptop: try lower pressures with one less laptop
                best(pressure, numLaptops-1).numAttempts,
                // 2. The laptop is OK: try higher pressures with same laptops
                best(numPressures - (pressure+1), numLaptops).numAttempts
            );
            // If applying this pressure resulted in fewer attempts to find out the 
            //    truth, then remember this:
            if (numAttempts <= result.numAttempts) {
                result.numAttempts = numAttempts;
                result.firstAttemptAtPressure = pressure;
            }
        }
        // Store result in memory (dynamic programming)
        if (!memo[numLaptops]) memo[numLaptops] = [];
        memo[numLaptops][numPressures] = result;
        // ...and return it
        return result;
    }
    // Outermost call of recursive function
    return best(numPressures, numLaptops);
}

// I/O handling

function processIO() {
    var result = getLeastAttempts(+inpPressures.value, +inpLaptops.value);
    outAttempts.textContent = result.numAttempts;
    outPressure.textContent = result.firstAttemptAtPressure;
}

inpPressures.oninput = processIO;
inpLaptops.oninput = processIO;
processIO(); // invoke calculation on page load

Highest pressure (m): <input type="number" id="inpPressures" value=100><br>
Number of laptops (n): <input type="number" id="inpLaptops" value=3><br>
Number of attempts: <span id="outAttempts"></span><br>
First pressure to attempt: <span id="outPressure"></span><br>

Change the inputs in the snippet to experiment.

This algorithm does not include the final optimisation mentioned in the Wikipedia article.

Answer 2

This is not an answer, but it is too long for a comment.

• If you have just one laptop, you can't do better than linearly search the entire range, which yields O(m) complexity.

• With 2 laptops, you can do better.

  Make a first try at sqrt(2m). If the laptop breaks, you need sqrt(2m) - 1 tries with the second one. If it doesn't, use the first one at 2*sqrt(2m) - 1. Generally, as long the first laptop stays intact, pick the p(k+1) setting as p(k) + sqrt(2m) - k. That guarantees that if it breaks, you still have sqrt(2m) - k tries to inspect the unknown rang, and finish the job with total of sqrt(2m) tries, no matter where does it break.

  If the first laptop never breaks, you'd reach m with again sqrt(2m) tries (I don't want to do math because SO doesn't support LaTeX, but it is pretty simple, just try).

  So, in case of 2 laptops the complexity is O(sqrt(m)).

More laptops you have, the more difficult the analysis becomes. Still the idea remains: pick such setting that both outcomes will require the same amount of tries to complete. It could be shown that as long as n is much less than log(m), the complexity is O(m ** (1/n)).