[Binary Bomb – Phase 4

I hope it’s obvious that phase4 is checking that the first number is in the range 0..14 inclusive (see lines +44..+57) Then it invokes func4 with three arguments: the first number entered, 0 and 14 (lines +62..+85). Next it checks that the return value is 0x25 (37 decimal) on line +90 and that the second number entered is also 37 (line +95)

Let’s move on to func4. I’ll call the three arguments x, low and high. Initially you don’t know what they are of course. Lines +23..+34 calculate (high - low) / 2. The ugly mess is because the compiler generates code to handle negative numbers with truncation to zero. We won’t see any negative numbers though. Line +36 is just a fancy addition, so in ebx we now have low + (high - low) / 2 which is also known as the average of the two numbers. The code then compares this average to the number x that has been provided as first argument. Lines +43..+62 get executed if x < average and they invoke func4(x, low, average - 1) and add the returned value to the average. Similarly, lines +70..+89 get executed if x > average and calculate average + func4(x, average + 1, high). If x == average then just the average itself is returned.

It’s basically doing a binary search and summing up the guesses as it goes. Given that the interval has 15 elements, it will need at most 4 guesses. The first guess is going to be 7, so to get the required result of 37 we need 30 more. We have at most 3 more tries and all the guesses will be either less than 7 or more than 7. Since 7 * 3 = 21 and that can’t give us 30 it means the number has to be greater than 7. Second guess is thus going to be (8 + 14) / 2 = 11, making our sum 18 with 19 more to go. If the number was above 11 that would mean we overshoot the target, so the number must be more than 7 and less than 11. Third guess is thus (8 + 10) / 2 = 9 which brings the sum to 27 with 10 more to go and just a single guess, so that means the number is 10.

TL;DR: the correct input should be 10 and 37

Leave a Comment