Two marbles and a 100-story building

Question

Classic question of job interviews...

You receive two marbles (marbles), you are told that they will break when they fall from a certain height (and presumably do not suffer damage if they fall below that height)and is asked to find the highest floor from which you can drop a ball without breaking it, as efficiently as possible.

Additional information:

• You must find the correct floor (not a possible interval).
• It is guaranteed that the two balls break in the same floor.
• Assume the delay to change floor is zero - only the number of ball drops counts.
• Assume the correct floor is randomly distributed in the building.

Source

Answer 1

I did a test here, on an idea similar to @Bacco’s. I got an average of 11 attempts, the best case being 2 pitches and the worst 20 pitches.

I implemented the @Bacco resolution, but the results were very bad. Average of 27 attempts, the best case being 2 pitches and the worst 52.

---

Before getting into the merits of the solution, I first made a solution tester, which I will explain here.

A game, in this case, is set up with the amount of balls you have to destroy, the amount of floors available and the floor response. I followed here a convention that the floor numbering starts at 1. So, to know what would be the best solution, I decided to test for all the possible combinations of the game.

So as my area of expertise is Java, I made the tester in Java anyway. The game is divided into 2 classes: one that configures the game and allows creating an instance, and the other with the real game, even keeping how many balls are left to play (makes an exception if you spend all the balls), how many releases you have made etc. The idea of having the separation is to be able to use the same "game scenario" in two different solvers.

So I have the class LancaBolinhas who cares about creating the polka dot throwing scenario:

public class LancaBolinhas {

    private int tentativas;
    private int andares;
    private int andarResposta;

    public LancaBolinhas(int tentativas, int andares, int andarResposta) {
        this.tentativas = tentativas;
        this.andares = andares;
        this.andarResposta = andarResposta;

        if (andarResposta <= 0) {
            throw new RuntimeException("Parâmetro 'andarResposta' precisa ser estritamente positivo");
        }

        if (andarResposta > andares) {
            throw new RuntimeException("Parâmetro 'andarResposta' precisa ser menor ou igual ao parâmetro 'andares'");
        }

        if (tentativas <= 0) {
            throw new RuntimeException("Parâmetro 'tentativas' precisa ser estritamente positivo");
        }
    }

    public JogoBolinhas criaJogo() {
        return new JogoBolinhas(tentativas, andares, andarResposta);
    }
}

And the class JogoBolinhas, which in turn has how many statistics have been made, if the solver has already tried to kick an answer, if it still has balls available to play etc:

public class JogoBolinhas {

    private int tentativasRestantes;
    private int andares;
    private int andarResposta;
    private boolean jahChutou = false;
    private boolean respostaCerta = false;
    private int lancamentosRealizados = 0;

    public JogoBolinhas(int tentativas, int andares, int andarResposta) {
        this.tentativasRestantes = tentativas;
        this.andares = andares;
        this.andarResposta = andarResposta;
    }

    public int getAndares() {
        return andares;
    }

    public int getTentativasRestantes() {
        return tentativasRestantes;
    }

    public int getLancamentosRealizados() {
        return lancamentosRealizados;
    }

    public boolean isRespostaCerta() {
        return respostaCerta;
    }

    /**
     * 
     * @param andarTeste
     * @return Se a bolinha continua intacta; ie, andar de teste menor do que o andar de resposta
     */
    public boolean testaAndar(int andarTeste) {
        if (tentativasRestantes <= 0) {
            throw new RuntimeException("Esgotou o número de tentativas");
        }
        lancamentosRealizados++;
        if (andarTeste > andares) {
            throw new RuntimeException("Você não pode jogar uma bolinha além do último andar");
        }
        if (andarTeste >= andarResposta) {
            tentativasRestantes--;
            return false;
        }
        return true;
    }

    public boolean tentaResposta(int andarTeste) {
        if (jahChutou) {
            throw new RuntimeException("Só pode fazer um único chute");
        }
        tentativasRestantes = 0;
        jahChutou = true;
        return respostaCerta = (andarTeste == andarResposta);
    }
}

I defined a solver as being a functional interface that extends from Consumer<JogoBolinhas> (since I don’t need more than that, the departure information I get after the JogoBolinhas) and allows you to define the name of the solver (for convenience):

public interface LancaBolinhasResolver extends Consumer<JogoBolinhas> {
    default String nomeResolvedor() {
        return "Novo resolvedor";
    }
}

On top of that, I created a little Main to generate all 100 possible games and, on top of a set of solvers, test the solvers and take some statistics from them:

public class Main {

    public static void main(String[] args) {
        int andares = 100;
        int tentativas = 2;
        
        List<LancaBolinhas> jogosPossiveis = IntStream.rangeClosed(1, 100)
                .mapToObj(r -> new LancaBolinhas(tentativas, andares, r))
                .collect(Collectors.toList());
        
        testaJogos(resolvedores(), jogosPossiveis);
    }

    private static void testaJogos(List<LancaBolinhasResolver> resolvedores, List<LancaBolinhas> jogosPossiveis) {
        for (LancaBolinhasResolver resolvedor: resolvedores) {
            IntSummaryStatistics st = jogosPossiveis.stream()
                    .map(LancaBolinhas::criaJogo)
                    .peek(resolvedor)
                    .filter(JogoBolinhas::isRespostaCerta)
                    .mapToInt(JogoBolinhas::getLancamentosRealizados)
                    .summaryStatistics();
            int soma = (int) st.getSum();
            int count = (int) st.getCount();
            int maior = st.getMax();
            int menor = st.getMin();
            double avg = st.getAverage();
            
            System.out.println(String.format("[RESULTADO] [%s] foram encontrados %d resultados de %d testes, num total de %d lançamentos; média de lançamentos: %f; maior quantidade de lançamentos: %d; menor quantidade de lançamentos: %d", resolvedor.nomeResolvedor(), count, jogosPossiveis.size(), soma, avg, maior, menor));
        }
    }

    // retorna os resolvedores que estão sendo testados
    private static List<LancaBolinhasResolver> resolvedores() {
        return ...;
    }
}

---

The @Bacco solution is basically to try 2-in-2 until you find the answer. My similar solution was to divide into blocks of equal size and then try 1 to 1 in this block which would be the appropriate floor, so that the amount of blocks equals that of attempts 1 to 1 within that block. From there, I arrived in blocks of 10.

If they were k balls in a universe of p^k levels, the logic is very similar to the one presented, but recursive.

I would divide into blocks of size p^(k-1) for the first ball, so that I guarantee a number 0 <= n < p such that the ball flips from n*p^(k-1) not break, but break when thrown from (n+1)*p^(k-1). Then inside that block of size p^(k-1), the second ball is used to search in which size block p^(k-2) break, finding a 0 <= m < p such that m*p^(k-2) + n*p^(k-1) do not break and that (m+1)*p^(k-2) + n*p^(k-1) break. Do this recursive until I have blocks of size p in k-1-the hundredth ball, and the k-nth ball I try 1 in 1 the p remaining options.

By my estimation, that solution would have a total of p*k attempts in the worst case, and k attempts at best.

Taking away by defining the sizes of the blocks, the algorithm roughly is the same. I called this common algorithm of LinearResolver and he is (for incrementoTentativa and startPoint defined as the block size and the first test floor respectively) basically like this:

public void accept(JogoBolinhas jogo) {
    OptionalInt ultimaCasaTestadaComSucesso = OptionalInt.empty();
    int casaTeste = startPoint;
    int casaLimite;
    OptionalInt casaResposta = OptionalInt.empty();

    while (true) {
        boolean bolinhaIntacta = jogo.testaAndar(casaTeste);

        depuracao(String.format("[%s] jogou a bolinha do %d andar, e ela %s", nomeResolvedor(), casaTeste, bolinhaIntacta? "continua intacta": "quebrou"));

        if (bolinhaIntacta) {
            ultimaCasaTestadaComSucesso = OptionalInt.of(casaTeste);
            casaTeste += incrementoTentativa;
        } else {
            casaLimite = casaTeste;
            break;
        }
        
        if (casaTeste > jogo.getAndares()) {
            casaLimite = jogo.getAndares();
            break;
        }
    }
    
    for (int i = ultimaCasaTestadaComSucesso.orElse(0) + 1; i <= casaLimite; i++) {
        boolean bolinhaIntacta = jogo.testaAndar(i);

        depuracao(String.format("[%s] jogou a bolinha do %d andar, e ela %s", nomeResolvedor(), i, bolinhaIntacta? "continua intacta": "quebrou"));
        
        if (!bolinhaIntacta) {
            casaResposta = OptionalInt.of(i);
            break;
        }
    }
    
    casaResposta.ifPresent(jogo::tentaResposta);
}

In this case, I have defined the classes JeffResolver, BaccoResolver and BaccoResolver2 (because I was in doubt whether I started at floor 1 or floor 2 by the @Bacco algorithm) extending from LinearResolver, passing the incrementoTentativa (and the startPoint where applicable) in the construction of the super-object.

The class LinearResolver is that, in its full version:

public class LinearResolver implements LancaBolinhasResolver {

    public static boolean printDepuracao = false;

    private final int incrementoTentativa;
    private final int startPoint;

    public LinearResolver(int incrementoPrimeiraTentativa) {
        this.incrementoTentativa = incrementoPrimeiraTentativa;
        startPoint = incrementoPrimeiraTentativa;
    }

    public LinearResolver(int incrementoPrimeiraTentativa, int startPoint) {
        this.incrementoTentativa = incrementoPrimeiraTentativa;
        this.startPoint = startPoint;
    }

    @Override
    public String nomeResolvedor() {
        return String.format("Resolvedor linear, começando de %d e saltando %d andares", startPoint, incrementoTentativa);
    }

    @Override
    public void accept(JogoBolinhas jogo) {
        OptionalInt ultimaCasaTestadaComSucesso = OptionalInt.empty();
        int casaTeste = startPoint;
        int casaLimite;
        OptionalInt casaResposta = OptionalInt.empty();

        while (true) {
            boolean bolinhaIntacta = jogo.testaAndar(casaTeste);

            depuracao(String.format("[%s] jogou a bolinha do %d andar, e ela %s", nomeResolvedor(), casaTeste, bolinhaIntacta? "continua intacta": "quebrou"));

            if (bolinhaIntacta) {
                ultimaCasaTestadaComSucesso = OptionalInt.of(casaTeste);
                casaTeste += incrementoTentativa;
            } else {
                casaLimite = casaTeste;
                break;
            }
            
            if (casaTeste > jogo.getAndares()) {
                casaLimite = jogo.getAndares();
                break;
            }
        }
        
        for (int i = ultimaCasaTestadaComSucesso.orElse(0) + 1; i <= casaLimite; i++) {
            boolean bolinhaIntacta = jogo.testaAndar(i);

            depuracao(String.format("[%s] jogou a bolinha do %d andar, e ela %s", nomeResolvedor(), i, bolinhaIntacta? "continua intacta": "quebrou"));
            
            if (!bolinhaIntacta) {
                casaResposta = OptionalInt.of(i);
                break;
            }
        }
        
        casaResposta.ifPresent(i -> tentaResposta(i, jogo));
    }
    
    private void tentaResposta(int andarChute, JogoBolinhas jogo) {
        boolean resultadoChute = jogo.tentaResposta(andarChute);
        
        depuracao(String.format("[%s] chutando do %d andar, em um total de %d lançamentos, resultado? %s", nomeResolvedor(), andarChute, jogo.getLancamentosRealizados(), resultadoChute? "acertou": "errou"));
    }

    private static void depuracao(String str) {
        if (printDepuracao) {
            System.out.println(str);
        }
    }
}

The class JeffResolver, so that’s just it:

public class JeffResolver extends LinearResolver {

    public JeffResolver() {
        super(10);
    }

    @Override
    public String nomeResolvedor() {
        return "Jeff resolver";
    }
}

The class BaccoResolver:

public class BaccoResolver extends LinearResolver {

    public BaccoResolver() {
        super(2);
    }

    @Override
    public String nomeResolvedor() {
        return "Bacco resolver (começando no 2)";
    }
}

And finally, the BaccoResolver2:

public class BaccoResolver2 extends LinearResolver {

    public BaccoResolver2() {
        super(2, 1);
    }

    @Override
    public String nomeResolvedor() {
        return "Bacco resolver (começando no 1)";
    }
}

In the test to compare the 3 implementations of LancaBolinhasResolver, I wrote the following in the static method resolvedores:

private static List<LancaBolinhasResolver> resolvedores() {
    return Arrays.asList(new JeffResolver(), new BaccoResolver(), new BaccoResolver2());
}

The result obtained was:

[RESULTADO] [Jeff resolver] foram encontrados 100 resultados de 100 testes, num total de 1100 lançamentos; média de lançamentos: 11,000000; maior quantidade de lançamentos: 20; menor quantidade de lançamentos: 2
[RESULTADO] [Bacco resolver (começando no 2)] foram encontrados 100 resultados de 100 testes, num total de 2700 lançamentos; média de lançamentos: 27,000000; maior quantidade de lançamentos: 52; menor quantidade de lançamentos: 2
[RESULTADO] [Bacco resolver (começando no 1)] foram encontrados 100 resultados de 100 testes, num total de 2748 lançamentos; média de lançamentos: 27,480000; maior quantidade de lançamentos: 52; menor quantidade de lançamentos: 2

---

Not satisfied in finding an answer with good average (11), I decided to test in brute force which would be the best LinearResolver for a problem limited to 100 floors. So I created all the options of incrementoTentativa from 1 to 100. Thus, the method resolvedores was like this:

private static List<LancaBolinhasResolver> resolvedoresBruteForce() {
    return IntStream.rangeClosed(1, 100).mapToObj(LinearResolver::new).collect(Collectors.toList());
}

The answer with the best average was with the incrementoTentativa == 12, averaging 10.98, the best case being 2 pitches and the worst 20 pitches. With incrementoTentativa == 11 also gave a better result than the solution dividing into groups of 10, with the average of 10.99 (and the same amount of pitches in the best/worst case).

It was interesting to note that considering i*k == 100, the result obtained for incrementoTentativa == i is exactly the same as the incrementoTentativa == k, reinforcing the thesis that the square root of the number of floors is close to the optimal solution when it has only 2 balls.

---

I have not tested for other behaviors (such as searching for the power of 2 closest to the correct floor that the ball does not break, as suggested in my first comment)but I believe that the solution of groups equal to the square root of the number of floors has a better average of all sorts. In this search for the potentials of 2, the worst possible case would be when the answer was 64, because 7 launches would be made to determine that the answer is in the interval (32, 64] and then 31 more launches to find the answer, totaling 38 launches. The worst case is worse than the worst case for LinearResolver with increment of 10, the average also looks like (not computei, only estimate even) be significantly worse.