The ol’ two light bulb, tall building problem

Question: You have two light bulbs and a 100-story building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops.

Hopefully your mind has immediately kicked into gear … and you start thinking of solutions and estimating the Big-O. Good for you these are the kinds of problems that I just can’t resist.

In this article I’ll take a look at several different solutions to this problem.

Linear Search:

Of course we are going to start with linear search, and why not it is the most obvious solution. Start at the first floor and just start dropping bulbs.

How does this algorithm perform? Well as you might expect pretty poorly. In the worst case you have to go all the way up to the top floor in order to find out that the bulbs break … however using this solution you can determine the breaking floor using only one bulb.

Additionally this algorithm has a pretty good travel time. Considering how much time you will spend traveling between floors, this algorithm is pretty good, in the sense that the number of trips up and down the stairs is equal to the number of floors in the building in the worst case.

public void getNumberOfDrops(DropScenerio dropManager) {<br /> for (int i = dropManager.getCurrentFloor();<br /> i <= dropManager.getNumFloors(); i++) {<br /> dropManager.setCurrentFloor(i);<br /> if (dropManager.dropTest()) {<br /> return;<br /> }<br /> }<br /> }

Worst Case # of Drops = n (where n = the height of the building) **

Average Case # of Drops = n/2 (where n = the height of the building)

Worst Case Travel Time = n (where n = the height of the building) **

Average Case Travel Time = n/2 (where n = the height of the building)

This is a pretty standard linear function and we can use this as a baseline for analyzing other searching methods.

Binary Search:

Another popular approach is the binary search, which can make a selection in ln(x) time. However there is an important constraint on this problem. You only have two light bulbs, this means that as soon as you break the first bulb, you are forced into a linear search pattern.

Consider a 100 story building and light bulb that breaks on the 24th floor. According to a pure binary search you start on the 5oth floor, drop the bulb and it breaks. Then you go to the 25th floor, drop the bulb and it break. Now you know that the bulb breaks somewhere on or below the 25th floor, but you are now out of light bulbs to test with.

Placing a limit on the number of failed probes places a significant limitation on effectiveness of the binary search method. Although that yields a significantly worse time than ln(x) it still yields a significant improvement over the linear search, because you can use the first light bulb to see if the break occurs in the lower or upper halves of the building and then use the second bulb to linear search that half to provide the answer.

<br /> public void getNumberOfDrops(DropScenerio dropManager) {

int left = 0;<br /> int right = dropManager.getNumFloors();

dropManager.setCurrentFloor(getHalf(left, right));

while (!dropManager.dropTest()) {<br /> left = dropManager.getCurrentFloor();<br /> dropManager.setCurrentFloor(left + getHalf(left, right));<br /> }

int cur = dropManager.getCurrentFloor();
for (int i = left + 1; i < cur; i++) {
dropManager.setCurrentFloor(i);
if (dropManager.dropTest()) {
return;
}
}

dropManager.setCurrentFloor(cur);
}

private int getHalf(int left, int right) {<br /> return (int) Math.ceil((right - left) / 2.0);<br /> }

We can see from the performance graphs that in the worst case this yields a 2x improvement over linear search time, and does even slightly better than that on average. However the travel distance is significantly worse than the linear search algorithm.

Fixed Block Search:

The binary search algorithm capitalized on a major optimization, using the first light bulb to identify a section of floors in which the we can use the second bulb to find the exact location, this is essentially generalizing and then improving on the worst case scenario we find in binary search.

By breaking the building up into equally sized blocks, and then testing the top floor of each block from the ground up we can prolong the use of the first light bulb, and fix the maximum cost of the second step where we linear search a specific block using the second bulb, to be the size of the block.

This should give us in the worst case a performance of (n / blockSize) + blockSize. Where (n/blockSize) is the performance of the first light bulb and (+ blockSize) is the performance of the second light bulb.

Now we have to choose an optimal block size. To do this we want to solve for the smallest n where the sum( n + n-1 + n-2 + … + 2 + 1) >= the buildingSize.

<br /> public void getNumberOfDrops(DropScenerio dropManager) {<br /> int stepSize = calculateStepSize(dropManager.getNumFloors());<br /> dropManager.setCurrentFloor(stepSize);<br /> while (!dropManager.dropTest()) {<br /> dropManager.setCurrentFloor(Math.min(dropManager.getCurrentFloor()<br />

• stepSize, dropManager.getNumFloors()));<br /> }</code>

int upperBnd = dropManager.getCurrentFloor() - 1;<br /> int lowerBnd = dropManager.getCurrentFloor() - stepSize + 1;<br /> if (dropManager.getLastFloor() + stepSize > dropManager.getNumFloors()) {<br /> lowerBnd = dropManager.getLastFloor() + 1;<br /> }<br /> for (int i = lowerBnd; i <= upperBnd; i++) {<br /> dropManager.setCurrentFloor(i);<br /> if (dropManager.dropTest()) {<br /> return;<br /> }<br /> }

dropManager.setCurrentFloor(upperBnd + 1);

}

private int calculateStepSize(int maxFloors) {
int value = maxFloors;
int steps = 0;

for (int i = 1; i < maxFloors; i++) {<br /> int k = maxFloors / i + i - 1;<br /> value = Math.min(value, k);<br /> if (k == value) {<br /> steps = i;<br /> }<br /> }<br /> return steps;<br /> }<br />

Constant N Search:

The ‘Fixed Block Search’ algorithm is pretty good in the sense that it combines the motion on doing the primary floor seek in the upward direction from the linear search solution and the floor segmentation from the binary search solution.

<br /> public void getNumberOfDrops(DropScenerio dropManager) {<br /> int initial = calculateInitialWindow(dropManager.getNumFloors()) ;<br /> solve(dropManager, initial, initial);<br /> }

private void solve(DropScenerio dropManager, int initial, int stepSize) {<br /> dropManager.setCurrentFloor(initial);

int iStep = stepSize;

while(!dropManager.dropTest()) {<br /> iStep = normalizeStepSize(dropManager, dropManager.getCurrentFloor(), iStep);<br /> dropManager.setCurrentFloor(dropManager.getCurrentFloor() + iStep - 1);<br /> iStep -= 1;

}

processMiniSteps(dropManager, iStep);

}

private void processMiniSteps(DropScenerio dropManager, int stepSize) {
int upperBnd = dropManager.getCurrentFloor() – 1;
int lowerBnd = dropManager.getCurrentFloor() – stepSize + 1;
if (dropManager.getLastFloor() + stepSize > dropManager.getNumFloors()) {
lowerBnd = dropManager.getLastFloor() + 1;
}
for (int i = lowerBnd; i <= upperBnd; i++) { dropManager.setCurrentFloor(i); if (dropManager.dropTest()) { return; } } dropManager.setCurrentFloor(upperBnd + 1); } private int normalizeStepSize(DropScenerio dropManager, int initial, int stepSize) { if(initial + stepSize -1 > dropManager.getNumFloors()) {
stepSize -= initial + stepSize -1 – dropManager.getNumFloors();
}

stepSize = Math.max(stepSize, 2);
return stepSize;
}

// min(1..N [sum(N)]);
private int calculateInitialWindow(int n) {
int minN = 0;
for(int i = n; i > 0; i–) {
int val = i * (i+1) / 2;
if(val >= n) {
minN = i;
}

}
return minN;
}

**
**