TL, DR
Google Foobar is a hidden coding challenge by Google, and Bomb, Baby! is the challenge I solved using Python in order to move forward in level 3.
This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.
Controlled explosion
The fourth task I got for Foobar was to figure out whether the self-replicating bombs I brought with me could blow Commander Lambda’s base without causing harm to the galaxy. The full description of the challenge is the following:
Bomb, Baby!
===========You're so close to destroying the LAMBCHOP doomsday device you can taste it! But in order to do so, you need to deploy special self-replicating bombs designed for you by the brightest scientists on Bunny Planet. There are two types: Mach bombs (M) and Facula bombs (F). The bombs, once released into the LAMBCHOP's inner workings, will automatically deploy to all the strategic points you've identified and destroy them at the same time.But there's a few catches. First, the bombs self-replicate via one of two distinct processes:
Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb, a Facula bomb is created;
Every Facula bomb spontaneously creates a Mach bomb.For example, if you had 3 Mach bombs and 2 Facula bombs, they could either produce 3 Mach bombs and 5 Facula bombs, or 5 Mach bombs and 2 Facula bombs. The replication process can be changed each cycle.
Second, you need to ensure that you have exactly the right number of Mach and Facula bombs to destroy the LAMBCHOP device. Too few, and the device might survive. Too many, and you might overload the mass capacitors and create a singularity at the heart of the space station - not good!
And finally, you were only able to smuggle one of each type of bomb - one Mach, one Facula - aboard the ship when you arrived, so that's all you have to start with. (Thus it may be impossible to deploy the bombs to destroy the LAMBCHOP, but that's not going to stop you from trying!)
You need to know how many replication cycles (generations) it will take to generate the correct amount of bombs to destroy the LAMBCHOP. Write a function solution(M, F) where M and F are the number of Mach and Facula bombs needed. Return the fewest number of generations (as a string) that need to pass before you'll have the exact number of bombs necessary to destroy the LAMBCHOP, or the string "impossible" if this can't be done! M and F will be string representations of positive integers no larger than 10^50. For example, if M = "2" and F = "1", one generation would need to pass, so the solution would be "1". However, if M = "2" and F = "4", it would not be possible.
Tests
The challenge also list a couple of test cases you will need to pass. However, it also indicates that there will be additional hidden tests that you need to pass. But you may not know what those test are about. Nice, uh?
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.-- Python cases --
Input:
solution.solution('4', '7')
Output:
4
Input:
solution.solution('2', '1')
Output:1
Constraints
You also need to keep in mid a few constraints. They are divided between Java and Python ones.
Python
======
Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.Input/output operations are not allowed.Your solution must be under 32000 characters in length including new lines and and other non-printing characters.
There are two important caveats to consider:
- Even if in the Python section there is no mention, execution time is limited. They say so in the Java section, but somehow they do not repeat it in the Python one.
- There are additional blacklisted libraries. For instance, I got a “BLACKLISTED CODE” exception when I tried to import the
syslibrary
Putting a solution together
Spoiler alert: you can find a complete working solution below. However I think that just copy-pasting a solution will not do you any good. But maybe looking at the flow and understanding the thinking behind the code may put you in the right direction to solve the challenge and learn something in the doing!
Coming to our challenge, the task is basically to check if the replication process described in the text can transform our initial bomb stock (1 Mach and 1 Facula) in the target mix of bombs we need blow out the LAMBCHOP device. In case it’s possible, we also need to return the number of generations needed to get there.
The replication process is quite simple, at each step the number of Mach (M) grows by an amount equal to the number of Facula (F) bombs. Or the other way around. Since we are going in reversal, as the function arguments are the desired number of M and F bombs, we have an easy way to decide which process to use.
In fact, the only way we could get in a M=4 and F=7 situation at step n is if step n-1 was M=4 and F=3. Similarly, step n-2 had to be M=1 and F=3. Hence, we can get two basic principles:
- We always need to subtract the lesser number between M and F from the larger one.
- If M = F and they are not equal to 1, we may not be able to generate the required mix of bombs.
That last point would require some mathematical demonstration, which you are free to implement by yourself (or just take my word for it).
A simple inefficient solution
A simple implementation of the inverse replication process described is the following:
def solution(x, y):
# Convert strings into integers
m = int(x)
f = int(y)
# Set the number of generations
gens = 0
# Start inverse replication loop
while True:
# If M and F are equal to 1
# return the number of generation passed
if m == 1 and f == 1:
return str(gens)
# If either M or F is less than 1
# or they are equal (but not 1, it'd be
# captured above) return "impossible"
elif m<1 or f<1 or m==f:
return "impossible"
# Check which one is larger, perform
# the inverse replication and increment
# the generation counter
else:
if m > f:
m-=f
gens += 1
else:
f-=m
gens += 1Comments in the code explain step by step what the algorithm is doing to reverse the replication process. If you submit this as a solution, however, you will find out that it solves each test EXCEPT test 3.
Unfortunately, you have no Idea what test 3 is about, because it is one of the hidden tests. That’s not a good start for debugging.
Getting to the point
Multiple session of head-scratching and Google searching about the issue lead me to a simple truth. My algorithm was working but was way too inefficient in case the difference between M and F was large. In fact, for a target of M= 10.000 and F = 1, my function would circle 10 thousand times before getting to the solution.
This was probably leading to execution timeout in test 3 (again, we don’t know what that test is about…so we need to apply some imagination).
The simplest way I found to accelerate the calculations was to introduce a new item, the multiplication factor. First I checked if the difference between M and F was more than an arbitrary multiple (in this case, 10x). If that was the case, I would divide the larger number by the smallest one and take the integer fraction (you could use the // operator as well). Then I used that number to decrease the larger one (multiplying by the smallest) and to increase the generation counter. It’s easier explained in code than in words, as you can see below:
def solution(x, y):
# Convert strings into integers
m = int(x)
f = int(y)
# Set the number of generations
gens = 0
# Start inverse replication loop
while True:
# If M and F are equal to 1
# return the number of generation passed
if m == 1 and f == 1:
return str(gens)
# If either M or F is less than 1
# or they are equal (but not 1, it'd be
# captured above) return "impossible"
elif m<1 or f<1 or m==f:
return "impossible"
# Check which one is larger, perform
# the inverse replication and increment
# the generation counter
else:
if m > f:
# If the difference is more
# than 10x, calculate a
# multiplication factor and
# increase gens accordingly
if m > 10*f:
multi = (int(m/f) -1)
gens += multi
m = m - (multi*f)
else:
m-=f
gens += 1
else:
if f > 10*m:
multi = (int(f/m) -1)
gens += multi
f = f - (multi*m)
else:
f-=m
gens += 1This approach increased the speed and efficiency of the inverse replication algorithm, fixing the infamous and unknown test 3 issue!
Once you are ready, you can check your work by typing:
verify solution.pyIf you completed your work correctly, a happy green message like this one will greet you:
You can then submit the solution as indicated. And that’s it for Google Foobar Challenge level 3 – Bomb, Baby!
I will write about each individual challenge in a dedicated post. You will find the post series via the link at the end of this post, stay tuned for updates!
Related links
Do you like our content? Check more of our posts in our blog!
