Sunday, 10 February 2013

100-story building and two water balloons.

Recently I found an article about teaser algorithm questions including “100-story building and two water balloons.”  so I thought it’s my turn to develop a solution for it.
The task is
There are two water balloons and a building which is 100 stories high. Write a program finding highest floor where a water balloon can be dropped without breaking it. Balloons can be dropped maximum 15 times.
The question is a bit tricky, as there are  at most two balloons, binarysearch can’t be used. Solution contains two parts, first one is finding upper floor boundary where a balloon breaks, second part is about trying to find the highest floor up to the upper floor boundary, starting from previous upper floor boundary.
Another trick is that each time a new upper floor is tested, number of attempts should be updated. Upper floor boundary then calculated by adding number of tries to the previous upper floor boundary and subtracting number of attempts.

When a high floor is picked (>92), then upper floor boundaries are calculated as below.

Trying next floor 15
Trying next floor 29
Trying next floor 42
Trying next floor 54
Trying next floor 65
Trying next floor 75
Trying next floor 84
Trying next floor 92

Java implementation


package ikm;

public class DropBalloons {
    int story = 99;
    int maxTry = 15;
    int balloons = 2;
    int attempts = 0;
    int floor = (int) (Math.random() * story);
    int lastTried;

    public int findHighestSafeFloor() {
        System.out.println("The floor is " + floor);
        int safeFloor = 0;
        while (maxTry > attempts) {
            int nextFloor = lastTried + maxTry - attempts;
            attempts++;
            System.out.println("Trying next floor " + nextFloor);
            if (nextFloor > floor) {
                balloons--;
                System.out.println("Next floor bigger then " + floor);
                System.out.println("Jump up from last tried floor " + lastTried);
                safeFloor = findSafePosition(lastTried);
                break;
            }
            lastTried = nextFloor;
        }
        System.out.println("Found safe floor at " + attempts + " attempts");
        return safeFloor;
    }

    private int findSafePosition(int lastTried) {
        while (balloons > 0) {
            System.out.println("Checking floor " + lastTried);
            if (lastTried >= floor) {
                balloons--;
                break;
            }
            attempts++;
            lastTried++;
        }
        int safeFloor = lastTried - 1;
        System.out.println("Found safe floor " + safeFloor);
        return safeFloor;
    }

    public int getFloor() {
        return floor;
    }
}


package ikm;

import junit.framework.Assert;
import org.junit.Test;

public class DropBalloonsTest {

    @Test
    public void testSafeFloor() {
        DropBalloons dropBalloons = new DropBalloons();
        int result = dropBalloons.findHighestSafeFloor();
        Assert.assertEquals(dropBalloons.getFloor()-1, result);
    }
}


Progam output is
The floor is 30
Trying next floor 15
Trying next floor 29
Trying next floor 42
Next floor bigger then 30
Jump up from last tried floor 29
Checking floor 29
Checking floor 30
Found safe floor 29
Found safe floor at 4 attempts






No comments:

Post a Comment