Comment on the Two Crystal Balls problem

The Two Crystal Balls problem, as mentioned in e.g. this course, is the following problem:

“You are given two identical crystal balls that will break if dropped from high enough. You are allowed to repeatedly drop them from different (integer) heights. Find the lowest distance (less than a given maximum) from which the balls will break. What is the optimal time complexity?”

The breaking condition is significant and rules out binary search, as once the first ball breaks, you are forced to linearly search through the heights in sequence. This would make it seem as the complexity is $𝑂(𝑛)$, but it is actually $𝑂\left(\sqrt{𝑛}\right)$.

The optimal algorithm is to first linearly search with jumps of size $𝑆=𝑂\left(\sqrt{𝑛}\right)$ until the first ball breaks. If it doesn’t break, then we have finished by making $𝑁=𝑂\left(\sqrt{𝑛}\right)$ jumps. Otherwise, take the previous known safe position and progressively increment the height by 1 until it breaks; in the worst case, this causes us to check an additional S balls. The final complexity is $𝑆+𝑁=𝑂\left(\sqrt{𝑛}\right)$.

This much was in the course. There are two comments I’d like to make.

Optimality

Firstly, it is possible to show that this is the optimum. From Tanya Khovanova’s page:

Suppose we have a strategy which always terminates in at most $𝑁$ throws. Then the floor is defined by two numbers: the number of throws before first ball breaks, and similarly for the the second ball. The sum of these two numbers should be less than or equal to $𝑁$. Hence, the number of floors we can distinguish is the number of different pairs of such numbers, which is equal to $\frac{1}{2}𝑁(𝑁+1)$.

Generalisation

Secondly, this can be generalised to the case of any finite number $𝐾$ of balls: the time complexity is $𝑂\left({𝑛}^{\frac{1}{𝐾}}\right)$. The required modification is simply to take the first jump length to be ${𝑆}_1=𝑂\left({𝑛}^{1-\frac{1}{𝐾}}\right)$, which results in $𝑁=𝑂\left({𝑛}^{\frac{1}{𝐾}}\right)$ jumps. With the second ball, take ${𝑆}_2=𝑂\left({𝑛}^{1-\frac{2}{𝐾}}\right)$ jumps. it again takes $𝑁$ jumps to cover a distance of length ${𝑆}_1$. With the third ball, take ${𝑆}_3=𝑂\left({𝑛}^{1-\frac{3}{𝐾}}\right)$, and so on, until with the $𝐾$th ball, you linearly search (i.e. ${𝑆}_{𝐾}=𝑂(1)=𝑂\left({𝑛}^{1-\frac{𝐾}{𝐾}}\right)$.) We use each ball to make $𝑁$ jumps, so the total number of jumps is $𝐾𝑁=𝑂\left({𝑛}^{1-\frac{1}{𝐾}}\right)$.

The fact that this algorithm is optimal up to constants is also by a similar argument: the number of $𝐾$ tuples is a polynomial of order $𝐾$.

It is amusing that in the limit of infinite balls $𝐾\to \infty$, we formally obtain $𝑂(1)$ which is off by a log (binary search). This “${𝑛}^0=log𝑛$” appears in many places in mathematics. The simplest instance of this that I know of is the fact that the integral of ${𝑥}^{𝑘}$ is ${𝑥}^{𝑘+1}$ (times a constant) unless $𝑘=-1$, in which case it is $log𝑥$. Some other occurences can be found in this Math.SE post.

Implementation

This is the code given in the course:

export default function two_crystal_balls(breaks: boolean[]): number {
    const jmpAmount = Math.floor(Math.sqrt(breaks.length));
    let i = jmpAmount;
    for (; i < breaks.length; i += jmpAmount) {
        if (breaks[i]) {
            break;
        }
    }
    i -= jmpAmount;
    for (let j = 0; j < jmpAmount && i < breaks.length; ++j, ++i) {
        if (breaks[i]) {
            return i;
        }
    }
    return -1;
}

As noted in this PR, this code doesn’t work in some edge cases. The fix proposed is to replace the last return with

    return i < breaks.length ? i : -1;

It’s simpler to just remove the j index check completely though:

export default function two_crystal_balls(breaks: boolean[]): number {
    const jmpAmount = Math.floor(Math.sqrt(breaks.length));
    let i = jmpAmount;
    for (; i < breaks.length; i += jmpAmount) {
        if (breaks[i]) {
            break;
        }
    }
    i -= jmpAmount;
    for (; i < breaks.length; ++i) {
        if (breaks[i]) {
            return i;
        }
    }
    return -1;
}

Conclusion

The problem is a little contrived, as there are no tests that guarantee we only break two balls. Nor are there any tests for speed, so a linear search would pass all the tests of the course. For the first issue, we could replace breaks by a custom array type that keeps logs of the number of breaks. But some questions remain: is there an algorithm with worst case exactly $\frac{𝑁(𝑁+1)}{2}$? And is there a variant problem with complexity $𝑂({𝑛}^{𝑞})$ for any rational $𝑞$?