About a few days ago, I read this post, Java Challenge: Dropping Balloons in Java having an interesting question.
It's a question to find an algorithm that gives the highest floor where you can drop a water balloon without breaking it at a 100 story building. You have only two balloons. I had actually seen this problem before and solved it already. It was not balloons but eggs. The solution is simple. Since if you miss two chances then have no balloons available, you need to try from the lowest safe level which means throw it from the first floor then if it does not pop, pick it up and go up to the level 2 and repeat it until the balloon pops. When you get the level from which the balloon bursts after dropping it, one level below this level is the highest safe level. (e.g. If the balloon first breaks on the 20th floor, the highest safe floor is the 19th).
It's easy isn't it? Yet the post above has one more condition to make it a little bit more difficult which is that you can try only 15 times. This means if I try the solution I've just described, I can test up to only the 15th floor. If the breaking point is the 40th floor or even the 16th floor, I'll never know it. When I first saw it, I tried to solve it for about five minutes yet couldn't solve it. That time, I was too busy to think about it further thus couldn't be bothered to do it. So I saved the URI of the post and forgot about it. Last night, no actually today morning, at approximately 6 am, I went to bed (yeah, am I a vampire or what? 🙂). Although I didn't even try to think about the problem yet all of sudden I came up with the answer of that question. It was just like the 'Eureka' story of Archimedes. Just like he figured out how to assess the purity of a golden crown when he stepped into a bath. OK, stop flattering myself 😞 I figured it out as the question was easy to solve.
Well, an important point here is that I in fact often find solutions to some difficult problems when I am not struggling to solve it yet am doing something irrelevant to the problem such as working out at the gym, washing dishes after a meal, lying on the bed to sleep or even when I'm dreaming. 🙂 So if you can't solve some problem then why don't you try something else rather than thinking about the solution all the time. Your brain may need to relax or when you use the other parts of the brain by doing something else, it might figure it out.
Anyway, here is what my brain told me that time.
Since I have only two balloons, if I choose a wrong floor twice, I lose all the chances. Then what if I check every second level as I have two balloons. So first, if I drop it from the second level and it breaks then I still have one more balloon so that I can try it from the first level and I can find if the highest safe level is the first or there is no safe level. If the balloon is fine after dropping it from the second level then I can pick it up and try it from the fourth level and so on. However, with this solution I can check at most until the 30th floor which is better than checking up to the 15th one but still not enough to check the 100 stories. This means that it is not sufficient to check ever second level in order to find the floor and I should focus on not only the two balloons but also the 15 times of attempts. From the first solution above, I know that I can definitely have 15 times if I try from the lowest safe floor and move up. It means if the number of floors between the already known highest safe level and the breaking point level found is the same as or fewer than the number of attempts I still have, I can find the very first level where the balloon bursts after dropping it (In order to reduce the number of attempts, of course, I have to make it the same as the number of attempts still left). Therefore I can tell the highest safe level that is one level below the breaking point level found. This should be easier to understand with an example.
Let's assume that the breaking point is the 17th floor.
At first, I have 15 tries to drop one balloon from the 15th floor. The balloon's still OK and I now have 14 times of attempts. Since the number of attempts I still have is 14 time, I can't try it from the 30th floor which is 15 + 15 yet I have to try it from the 29th floor (15 + 14). Because the breaking point is the 17th floor, the balloon breaks on the 29th floor. Now I have 13 times of attempts and 1 balloon left. From the first try, I know the 14th floor is fine so I try from the next floor that is floor 15 to see if floor 14 is the highest safe floor. It turns out the 15th one is fine and now I have 12 times left. 16th -> OK / 11 times left, 17th -> it breaks! / 10 times left So I can tell the 16th floor is the highest safe floor and I didn't even use all the 15 times of attempts.
The post that has the question specifies the floor starts from 0 so let's make the first floor is floor 0 and see have it works. I made a table which shows the number of attempts required to find the highest safe floor.
====================================================
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 tries
====================================================
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 - 1
15 16 17 18 19 20 21 22 23 24 25 26 27 28 - 2
29 30 31 32 33 34 35 36 37 38 39 40 41 - 3
42 43 44 45 46 47 48 49 50 51 52 53 - 4
54 55 56 57 58 59 60 61 62 63 64 - 5
65 66 67 68 69 70 71 72 73 74 - 6
75 76 77 78 79 80 81 82 83 - 7
84 85 86 87 88 89 90 91 - 8
92 93 94 95 96 97 98 - 9
99 - 10
So if the highest safe floor is 73. The first balloon breaks on the floor 74 after 6 times of attempts. After that try from the floor 65 (attempts: 7) through 66 (8), 67 (9), 68 (10), 69 (11), 70 (12), 71 (13), 72 (14) to 73 (15) and the second balloon hasn't broken so I can tell the highest safe floor is the floor 73.
====================================================
1 2 3 4 5 6 7 8[ 9]10 11 12 13 14 15
====================================================
65 66 67 68 69 70 71 72[73]74 -[6]
attempts: 6 times to get the floor 74 + 9 times to check until the floor 73 = 15 times.
Once I found the solution writing code is a piece of cake. I roughly wrote the main part of the code like this.
private static final int MAX_ATTEMPTS = 15;
private int theFloor = (int) (Math.random() * 100);
private int numberOfBalloons = 2;
private int numberOfAttempts = 0;
// ...
public void findHighestSafeFloor() {
int previousFloorIndex = -1;
int floorIndex = MAX_ATTEMPTS - 1;
int highestSafeFloor = 0;
while (MAX_ATTEMPTS > numberOfAttempts) {
numberOfAttempts++;
if (theFloor <= floorIndex) {
numberOfBalloons--;
highestSafeFloor = findHighestSafeFloor(previousFloorIndex + 1, floorIndex);
break;
}
previousFloorIndex = floorIndex; floorIndex += (MAX_ATTEMPTS - numberOfAttempts);
if (99 < floorIndex) {
floorIndex = 99;
}
}
/* print the result. */
}
private int findHighestSafeFloor(final int start, final int end) {
for (int i = start; i < end; i++) {
numberOfAttempts++;
if (theFloor == i) {
numberOfBalloons--;
return (i - 1);
}
}
return (end - 1);
}
I am sure that the findHighestSafeFloor() method above works but I decided to make it recursion. Why? No special reasons. I just like recursion 🙂 as I haven't used it for approximately four years since I last programmed in a functional programming language like Haskell in my math class thus miss it. :D
Although the code can be very simple as the following code with recursion, it has to increase the number of attempts and to decrease the number of balloons left, so it would be a bit more verbose as the second code.
private int findHighestSafeFloor(final int start, final int end) {
return (start < end ?
(theFloor == start ?
(start - 1) :
findHighestSafeFloor((start + 1), end)) :
(end - 1)
);
}
private int findHighestSafeFloor(final int start, final int end) {
if (start < end) {
numberOfAttempts++;
if (theFloor == start) {
numberOfBalloons--;
return (start - 1);
} else {
return findHighestSafeFloor((start + 1), end);
}
} else {
return (end - 1);
}
}
Now it's time to code the complete programme and test it. Well, since it's a very small programme, I didn't do object-oriented programming. 🙂
package com.lckymn.kevin.findingfloor;
public final class HighestSafeFloorFinder {
private static final int TOP_LEVEL = 99;
private static final int MAX_ATTEMPTS = 15;
private int theBreakingPointFloor;
private int numberOfBalloons;
private int numberOfAttemptsMade;
public void init(final int theBreakingPointFloor) {
this.theBreakingPointFloor = theBreakingPointFloor;
System.out.println("The breaking point: " + theBreakingPointFloor);
numberOfBalloons = 2;
numberOfAttemptsMade = 0;
}
public void findHighestSafeFloor() {
int previousFloorIndex = -1;
int floorIndex = MAX_ATTEMPTS - 1;
int highestSafeFloor = 0;
while (MAX_ATTEMPTS > numberOfAttemptsMade) {
dropBalloon();
if (theBreakingPointFloor <= floorIndex) {
breakBalloon();
highestSafeFloor = findHighestSafeFloor(previousFloorIndex + 1, floorIndex);
break;
}
previousFloorIndex = floorIndex;
floorIndex += (MAX_ATTEMPTS - numberOfAttemptsMade);
if (TOP_LEVEL < floorIndex) {
floorIndex = TOP_LEVEL;
}
}
if (0 > highestSafeFloor) {
System.out.println("There is no floor that you can drop a balloon without breaking it. Even the first floor (floor 0) is not safe.");
} else {
System.out.println("The highest safe floor: " + highestSafeFloor);
}
System.out.println("The number of attempts made: " + numberOfAttemptsMade);
}
private int findHighestSafeFloor(final int start, final int end) {
if (start < end) {
dropBalloon();
if (theBreakingPointFloor == start) {
breakBalloon();
return (start - 1);
} else {
return findHighestSafeFloor((start + 1), end);
}
} else {
return (end - 1);
}
}
private void dropBalloon() {
if (MAX_ATTEMPTS == numberOfAttemptsMade) {
throw new IllegalStateException("You've already tried 15 times.");
}
numberOfAttemptsMade++;
}
private void breakBalloon() {
if (0 == numberOfBalloons) {
throw new IllegalStateException("You've already broken all the balloons available.");
}
numberOfBalloons--;
}
public static void main(String[] args) {
HighestSafeFloorFinder highestSafeFloorFinder = new HighestSafeFloorFinder();
for (int i = 0; i < 100; i++) {
System.out.println("[Test Number: " + i + "]");
highestSafeFloorFinder.init(i);
highestSafeFloorFinder.findHighestSafeFloor();
System.out.println("=======================================");
}
System.exit(0);
}
}
Well, the code looks a bit ugly but in my defence, I'd just like to see the result and am busy so had no stomach for making it pretty. :D (Oh! such a poor excuse / but really busy 😞)
The dropBalloon() and the breakBalloon() are added to increase the number of attempts made and to decrease the number of balloons left respectively. The dropBalloon() method also checks if the number of attempts already made is 15 and it tries to make another one than throws an exception telling that all the chances have been used. Similarly the breakBalloon() method checks if all the available balloons have broken if so, it also throws an exception saying there are no available balloons left. Thus I can see if the programme can find the highest safe floor with 15 times or fewer times of attempts and only two water balloons. If it cannot, it immediately throws an exception and stop the programme so I can see my programme fails to prove my algorithm.
The init() method is to initialise all the variables so that I can test it many times. It checks all the floors from the first one (floor 0) to the last one (floor 99) so if the programme works fine without any exception thrown then it might prove my answer is correct.
Let's check out the result!
[Test Number: 0]
The breaking point: 0
There is no floor that you can drop a balloon without breaking it. Even the first floor (floor 0) is not safe.
The number of attempts made: 2
=======================================
[Test Number: 1]
The breaking point: 1
The highest safe floor: 0
The number of attempts made: 3
=======================================
[Test Number: 2]
The breaking point: 2
The highest safe floor: 1
The number of attempts made: 4
=======================================
[Test Number: 3]
The breaking point: 3
The highest safe floor: 2
The number of attempts made: 5
=======================================
[Test Number: 4]
The breaking point: 4
The highest safe floor: 3
The number of attempts made: 6
=======================================
[Test Number: 5]
The breaking point: 5
The highest safe floor: 4
The number of attempts made: 7
=======================================
[Test Number: 6]
The breaking point: 6
The highest safe floor: 5
The number of attempts made: 8
=======================================
[Test Number: 7]
The breaking point: 7
The highest safe floor: 6
The number of attempts made: 9
=======================================
[Test Number: 8]
The breaking point: 8
The highest safe floor: 7
The number of attempts made: 10
=======================================
[Test Number: 9]
The breaking point: 9
The highest safe floor: 8
The number of attempts made: 11
=======================================
[Test Number: 10]
The breaking point: 10
The highest safe floor: 9
The number of attempts made: 12
=======================================
[Test Number: 11]
The breaking point: 11
The highest safe floor: 10
The number of attempts made: 13
=======================================
[Test Number: 12]
The breaking point: 12
The highest safe floor: 11
The number of attempts made: 14
=======================================
[Test Number: 13]
The breaking point: 13
The highest safe floor: 12
The number of attempts made: 15
=======================================
[Test Number: 14]
The breaking point: 14
The highest safe floor: 13
The number of attempts made: 15
=======================================
[Test Number: 15]
The breaking point: 15
The highest safe floor: 14
The number of attempts made: 3
=======================================
[Test Number: 16]
The breaking point: 16
The highest safe floor: 15
The number of attempts made: 4
=======================================
[Test Number: 17]
The breaking point: 17
The highest safe floor: 16
The number of attempts made: 5
=======================================
[Test Number: 18]
The breaking point: 18
The highest safe floor: 17
The number of attempts made: 6
=======================================
[Test Number: 19]
The breaking point: 19
The highest safe floor: 18
The number of attempts made: 7
=======================================
[Test Number: 20]
The breaking point: 20
The highest safe floor: 19
The number of attempts made: 8
=======================================
[Test Number: 21]
The breaking point: 21
The highest safe floor: 20
The number of attempts made: 9
=======================================
[Test Number: 22]
The breaking point: 22
The highest safe floor: 21
The number of attempts made: 10
=======================================
[Test Number: 23]
The breaking point: 23
The highest safe floor: 22
The number of attempts made: 11
=======================================
[Test Number: 24]
The breaking point: 24
The highest safe floor: 23
The number of attempts made: 12
=======================================
[Test Number: 25]
The breaking point: 25
The highest safe floor: 24
The number of attempts made: 13
=======================================
[Test Number: 26]
The breaking point: 26
The highest safe floor: 25
The number of attempts made: 14
=======================================
[Test Number: 27]
The breaking point: 27
The highest safe floor: 26
The number of attempts made: 15
=======================================
[Test Number: 28]
The breaking point: 28
The highest safe floor: 27
The number of attempts made: 15
=======================================
[Test Number: 29]
The breaking point: 29
The highest safe floor: 28
The number of attempts made: 4
=======================================
[Test Number: 30]
The breaking point: 30
The highest safe floor: 29
The number of attempts made: 5
=======================================
[Test Number: 31]
The breaking point: 31
The highest safe floor: 30
The number of attempts made: 6
=======================================
[Test Number: 32]
The breaking point: 32
The highest safe floor: 31
The number of attempts made: 7
=======================================
[Test Number: 33]
The breaking point: 33
The highest safe floor: 32
The number of attempts made: 8
=======================================
[Test Number: 34]
The breaking point: 34
The highest safe floor: 33
The number of attempts made: 9
=======================================
[Test Number: 35]
The breaking point: 35
The highest safe floor: 34
The number of attempts made: 10
=======================================
[Test Number: 36]
The breaking point: 36
The highest safe floor: 35
The number of attempts made: 11
=======================================
[Test Number: 37]
The breaking point: 37
The highest safe floor: 36
The number of attempts made: 12
=======================================
[Test Number: 38]
The breaking point: 38
The highest safe floor: 37
The number of attempts made: 13
=======================================
[Test Number: 39]
The breaking point: 39
The highest safe floor: 38
The number of attempts made: 14
=======================================
[Test Number: 40]
The breaking point: 40
The highest safe floor: 39
The number of attempts made: 15
=======================================
[Test Number: 41]
The breaking point: 41
The highest safe floor: 40
The number of attempts made: 15
=======================================
[Test Number: 42]
The breaking point: 42
The highest safe floor: 41
The number of attempts made: 5
=======================================
[Test Number: 43]
The breaking point: 43
The highest safe floor: 42
The number of attempts made: 6
=======================================
[Test Number: 44]
The breaking point: 44
The highest safe floor: 43
The number of attempts made: 7
=======================================
[Test Number: 45]
The breaking point: 45
The highest safe floor: 44
The number of attempts made: 8
=======================================
[Test Number: 46]
The breaking point: 46
The highest safe floor: 45
The number of attempts made: 9
=======================================
[Test Number: 47]
The breaking point: 47
The highest safe floor: 46
The number of attempts made: 10
=======================================
[Test Number: 48]
The breaking point: 48
The highest safe floor: 47
The number of attempts made: 11
=======================================
[Test Number: 49]
The breaking point: 49
The highest safe floor: 48
The number of attempts made: 12
=======================================
[Test Number: 50]
The breaking point: 50
The highest safe floor: 49
The number of attempts made: 13
=======================================
[Test Number: 51]
The breaking point: 51
The highest safe floor: 50
The number of attempts made: 14
=======================================
[Test Number: 52]
The breaking point: 52
The highest safe floor: 51
The number of attempts made: 15
=======================================
[Test Number: 53]
The breaking point: 53
The highest safe floor: 52
The number of attempts made: 15
=======================================
[Test Number: 54]
The breaking point: 54
The highest safe floor: 53
The number of attempts made: 6
=======================================
[Test Number: 55]
The breaking point: 55
The highest safe floor: 54
The number of attempts made: 7
=======================================
[Test Number: 56]
The breaking point: 56
The highest safe floor: 55
The number of attempts made: 8
=======================================
[Test Number: 57]
The breaking point: 57
The highest safe floor: 56
The number of attempts made: 9
=======================================
[Test Number: 58]
The breaking point: 58
The highest safe floor: 57
The number of attempts made: 10
=======================================
[Test Number: 59]
The breaking point: 59
The highest safe floor: 58
The number of attempts made: 11
=======================================
[Test Number: 60]
The breaking point: 60
The highest safe floor: 59
The number of attempts made: 12
=======================================
[Test Number: 61]
The breaking point: 61
The highest safe floor: 60
The number of attempts made: 13
=======================================
[Test Number: 62]
The breaking point: 62
The highest safe floor: 61
The number of attempts made: 14
=======================================
[Test Number: 63]
The breaking point: 63
The highest safe floor: 62
The number of attempts made: 15
=======================================
[Test Number: 64]
The breaking point: 64
The highest safe floor: 63
The number of attempts made: 15
=======================================
[Test Number: 65]
The breaking point: 65
The highest safe floor: 64
The number of attempts made: 7
=======================================
[Test Number: 66]
The breaking point: 66
The highest safe floor: 65
The number of attempts made: 8
=======================================
[Test Number: 67]
The breaking point: 67
The highest safe floor: 66
The number of attempts made: 9
=======================================
[Test Number: 68]
The breaking point: 68
The highest safe floor: 67
The number of attempts made: 10
=======================================
[Test Number: 69]
The breaking point: 69
The highest safe floor: 68
The number of attempts made: 11
=======================================
[Test Number: 70]
The breaking point: 70
The highest safe floor: 69
The number of attempts made: 12
=======================================
[Test Number: 71]
The breaking point: 71
The highest safe floor: 70
The number of attempts made: 13
=======================================
[Test Number: 72]
The breaking point: 72
The highest safe floor: 71
The number of attempts made: 14
=======================================
[Test Number: 73]
The breaking point: 73
The highest safe floor: 72
The number of attempts made: 15
=======================================
[Test Number: 74]
The breaking point: 74
The highest safe floor: 73
The number of attempts made: 15
=======================================
[Test Number: 75]
The breaking point: 75
The highest safe floor: 74
The number of attempts made: 8
=======================================
[Test Number: 76]
The breaking point: 76
The highest safe floor: 75
The number of attempts made: 9
=======================================
[Test Number: 77]
The breaking point: 77
The highest safe floor: 76
The number of attempts made: 10
=======================================
[Test Number: 78]
The breaking point: 78
The highest safe floor: 77
The number of attempts made: 11
=======================================
[Test Number: 79]
The breaking point: 79
The highest safe floor: 78
The number of attempts made: 12
=======================================
[Test Number: 80]
The breaking point: 80
The highest safe floor: 79
The number of attempts made: 13
=======================================
[Test Number: 81]
The breaking point: 81
The highest safe floor: 80
The number of attempts made: 14
=======================================
[Test Number: 82]
The breaking point: 82
The highest safe floor: 81
The number of attempts made: 15
=======================================
[Test Number: 83]
The breaking point: 83
The highest safe floor: 82
The number of attempts made: 15
=======================================
[Test Number: 84]
The breaking point: 84
The highest safe floor: 83
The number of attempts made: 9
=======================================
[Test Number: 85]
The breaking point: 85
The highest safe floor: 84
The number of attempts made: 10
=======================================
[Test Number: 86]
The breaking point: 86
The highest safe floor: 85
The number of attempts made: 11
=======================================
[Test Number: 87]
The breaking point: 87
The highest safe floor: 86
The number of attempts made: 12
=======================================
[Test Number: 88]
The breaking point: 88
The highest safe floor: 87
The number of attempts made: 13
=======================================
[Test Number: 89]
The breaking point: 89
The highest safe floor: 88
The number of attempts made: 14
=======================================
[Test Number: 90]
The breaking point: 90
The highest safe floor: 89
The number of attempts made: 15
=======================================
[Test Number: 91]
The breaking point: 91
The highest safe floor: 90
The number of attempts made: 15
=======================================
[Test Number: 92]
The breaking point: 92
The highest safe floor: 91
The number of attempts made: 10
=======================================
[Test Number: 93]
The breaking point: 93
The highest safe floor: 92
The number of attempts made: 11
=======================================
[Test Number: 94]
The breaking point: 94
The highest safe floor: 93
The number of attempts made: 12
=======================================
[Test Number: 95]
The breaking point: 95
The highest safe floor: 94
The number of attempts made: 13
=======================================
[Test Number: 96]
The breaking point: 96
The highest safe floor: 95
The number of attempts made: 14
=======================================
[Test Number: 97]
The breaking point: 97
The highest safe floor: 96
The number of attempts made: 15
=======================================
[Test Number: 98]
The breaking point: 98
The highest safe floor: 97
The number of attempts made: 15
=======================================
[Test Number: 99]
The breaking point: 99
The highest safe floor: 98
The number of attempts made: 10
=======================================
It works! 😃