Google Foobar: Level 3C

My friends at Google have chosen an explosive problem to close out level 3:

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.

Languages
=========

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Java cases --
Input:
Solution.solution('2', '1')
Output:
    1

Input:
Solution.solution('4', '7')
Output:
    4

-- Python cases --
Input:
solution.solution('4', '7')
Output:
    4

Input:
solution.solution('2', '1')
Output:
    1

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

The most difficult part of this problem, for me, ended up being the wording. I kept reading how the replication mechanisms worked over and over, but for whatever reason I just could not understand what it was trying to tell me. I did eventually figure it out. They’re saying that (m, f) will become one of (m + f, f) or (m, f + m). Each replication cycle one or the other must be chosen. Now their (4,7) example can be visualized:

But I quickly realized that with inputs of 10^50 this top-down thinking isn’t going to work. I generally find going bottom-up to be more tricky to picture, that’s why I went from the top. But it turned out that with this problem going from the bottom was much easier. One of the paths always has one of the bomb counts going negative and thus can be discarded. So going bottom-up results in a direct path through the graph:

If either bomb count goes zero, or if the two counts match each other without reaching (1,1), then the solution is impossible. But other than that edge case, this should now be as easy as a loop.

But it wasn’t quite. Some of the tests were failing. What I’d missed is that one of bomb types can be a multiple of the other type, in which case it is still very inefficient to take the direct path only one cycle at a time. If we have a multiple we can instantly jump the gap. With that enhancement in place my solution started passing all the tests:

# Author: Derek Moran, Level 3 Bunny Planet Saboteur
# Date: 04-DEC-2022

def solution(x, y):
    # Your code here
    return getNumReplicationCyclesToGenerateRequiredBombsAsString( x, y )

# Returns the number of replication cycles ( as a string ) it will take to generate the input number of Mach and Facula bombs
# This assumes we start with one of each bomb type. If the input targets are not possible, then 'impossible' will be returned.
#
# numRequiredMachBombsAsString and numRequiredFaculaBombsAsString must be postive integers ( passed as string ) with size no larger than 10^50
def getNumReplicationCyclesToGenerateRequiredBombsAsString( numRequiredMachBombsAsString, numRequiredFaculaBombsAsString ):

    validationError = "numRequiredMachBombsAsString and numRequiredFaculaBombsAsString must be postive integers ( passed as string ) with size no larger than 10^50"
    if not type(numRequiredMachBombsAsString) is str or not numRequiredMachBombsAsString.isdigit():
        raise Exception( validationError )

    if not type(numRequiredFaculaBombsAsString) is str or not numRequiredFaculaBombsAsString.isdigit():
        raise Exception( validationError )

    numRequiredMachBombs = int(numRequiredMachBombsAsString)
    numRequiredFaculaBombs = int(numRequiredFaculaBombsAsString)

    maxNumberOfInputBombs = 10 ** 50
    if numRequiredMachBombs < 1 or \
        numRequiredMachBombs > maxNumberOfInputBombs or \
        numRequiredFaculaBombs < 1 or \
        numRequiredFaculaBombs > maxNumberOfInputBombs:
        raise Exception( validationError )

    # Envision our starting point as having one of each bomb type: (1,1)
    # (1,1) can then replicate into one of (2,1) or (1,2)
    # (2,1) can then replicate into one of (3,1) or (2,3), and (1,2) into (3,2) or (1,3)
    # This tree structure could continue until each leaf exceeds or reaches the required number of bombs
    # If we reach the requirements, then the answer is the tree depth
    #
    # HOWEVER, starting from (1,1) would require traversing the entire tree
    # Instead, let's start with the target ( numRequiredMachBombsAsString, numRequiredFaculaBombsAsString )
    # Because we know that the parent node must be one of:
    #  ( numRequiredMachBombsAsString-numRequiredFaculaBombsAsString, numRequiredFaculaBombsAsString )
    #  ( numRequiredMachBombsAsString, numRequiredFaculaBombsAsString-numRequiredMachBombsAsString )
    # The number of bombs might be equal ( or one of them is zero ); if so we can tell immediately that this solution is impossible
    # Otherwise they are not equal, so one of these prior nodes would require a negative number of bombs, and thus can be safely discarded
    # Therefore a bottom up approach can give us a most direct path through our tree and avoid a full traversal
    #
    # Additionally note that if one bomb type has a count that is larger than multiples of the other type, that we would then be
    # taking that same branch multiple times. So in those cases we can jump up the tree by that multiple, thereby reducing
    # our traversal length even further
    numRequiredMachBombsRemaining = numRequiredMachBombs
    numRequiredFaculaBombsRemaining = numRequiredFaculaBombs
    numTotalReplicationCycles = 0

    while True:
        if numRequiredMachBombsRemaining == numRequiredFaculaBombsRemaining == 1:
            break

        if numRequiredMachBombsRemaining == numRequiredFaculaBombsRemaining or \
            numRequiredMachBombsRemaining == 0 or \
            numRequiredFaculaBombsRemaining == 0:
            return "impossible"

        numReplicationCycles = 1
        if numRequiredMachBombsRemaining > numRequiredFaculaBombsRemaining:
            if numRequiredFaculaBombsRemaining > 1:
                numReplicationCycles = int(numRequiredMachBombsRemaining / numRequiredFaculaBombsRemaining)
                numRequiredMachBombsRemaining -= numRequiredFaculaBombsRemaining * numReplicationCycles
            else:
                numReplicationCycles = numRequiredMachBombsRemaining - 1
                numRequiredMachBombsRemaining = 1
        else:
            if numRequiredMachBombsRemaining > 1:
                numReplicationCycles = int(numRequiredFaculaBombsRemaining / numRequiredMachBombsRemaining)
                numRequiredFaculaBombsRemaining -= numRequiredMachBombsRemaining * numReplicationCycles
            else:
                numReplicationCycles = numRequiredFaculaBombsRemaining - 1
                numRequiredFaculaBombsRemaining = 1

        numTotalReplicationCycles += numReplicationCycles

    return str(numTotalReplicationCycles)