Google Foobar: Level 3B

I was ready for the next Foobar challenge, and Google responded with an energizing problem:

Fuel Injection Perfection
=========================

Commander Lambda has asked for your help to refine the automatic quantum antimatter fuel injection system for the LAMBCHOP doomsday device. It's a great chance for you to get a closer look at the LAMBCHOP -- and maybe sneak in a bit of sabotage while you're at it -- so you took the job gladly. 

Quantum antimatter fuel comes in small pellets, which is convenient since the many moving parts of the LAMBCHOP each need to be fed fuel one pellet at a time. However, minions dump pellets in bulk into the fuel intake. You need to figure out the most efficient way to sort and shift the pellets down to a single pellet at a time. 

The fuel control mechanisms have three operations: 

1) Add one fuel pellet
2) Remove one fuel pellet
3) Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)

Write a function called solution(n) which takes a positive integer as a string and returns the minimum number of operations needed to transform the number of pellets to 1. The fuel intake control panel can only display a number up to 309 digits long, so there won't ever be more pellets than you can express in that many digits.

For example:
solution(4) returns 2: 4 -> 2 -> 1
solution(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

Languages
=========

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

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('15')
Output:
    5

Input:
solution.solution('4')
Output:
    2

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

Input:
Solution.solution('15')
Output:
    5

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.

While the prior problem was very difficult to visualize, at least for me, this one I found straight forward to picture:

The issue was that the input was so large, it would certainly overflow the call stack. A bottom-up iterative approach might be preferable, that would give better memory complexity. But I find it harder to visualize things in that direction, so I decided to start by just taking over the call stack. If Google’s test passed the solution, then I’d stick with it. I think the enhanced readability is worth the tradeoff of the memory optimization. If the tests failed, then I’d assume that Google considered the memory optimization more important, and would switch my approach.

But it turned out that Google was indeed accepting of this solution:

# Author: Derek Moran, Level 3, Commander Lambda's Personal Assistant @ Commander Lambda Space Station
# Date: 01-DEC-2022

def solution(n):
    # Your code here
    return getMinNumberOfFuelControlOperationsRequiredToReduceToOnePellet( n )

# Returns the minimum number of fuel control operations ( ie add pellet, remove pellet, divide pellets in half )
# required to transform the input number of pellets to one
#
# The provided numInitialFuelPelletsAsString must be a postive integer ( passed as string ) with length no more than 309
def getMinNumberOfFuelControlOperationsRequiredToReduceToOnePellet( numInitialFuelPelletsAsString ):

    validationError = "numInitialFuelPelletsAsString must be a postive integer ( passed as string ) with length no more than 309"
    if not type(numInitialFuelPelletsAsString) is str or len(numInitialFuelPelletsAsString) > 309 or not numInitialFuelPelletsAsString.isdigit():
        raise Exception( validationError )

    numInitialFuelPellets = int(numInitialFuelPelletsAsString)

    if numInitialFuelPellets < 0:
        raise Exception( validationError )

    # If we have 1 pellet then there are zero operations
    # If we have 2 pellets then we can finish in a single division
    # For larger numbers, we can compare adding and removing a pellet before dividing, which makes a recursive approach seem ideal
    # BUT, inputs can be up to 309 digits in length!!!
    # Even though Python's arbitrary-precision arithmetic can handle that, we would still overflow the call stack with straight recursion
    # So let's use our own custom ( in an effort to reduce memory and increase performance ) stacks to ensure that doesn't happen.
    # We'll also use a cache to minimize duplicate work, and bitwise operators in an additional effort to speed up the divisions
    callStack, numOperationsStack = Stack(), Stack()

    class CallHandlers:
        Controller = 0 # For the main logic - this handler will setup the stack for other handlers
        AddOrRemovePellet = 1
        DividePelletsByHalf = 2

    callStack.push( ( CallHandlers.Controller, numInitialFuelPellets ) )

    # Note cache is pre-populated with 1 pellet ( 0 operations since we are done ) and 2 pellets ( 1 division operation will complete the job )
    cache = { 1: 0, 2: 1 }

    while True:

        nextCall = callStack.pop()
        if nextCall == None: break

        nextCallType, nextNumFuelPellets = nextCall

        if nextCallType == CallHandlers.Controller:
            if nextNumFuelPellets in cache:
                numOperationsStack.push( cache[nextNumFuelPellets] )
            elif nextNumFuelPellets & 1 != 0: # Fuel cannot be safely divided, so setup a call stack for comparing the adding/removing of a pellet
                callStack.push( ( CallHandlers.AddOrRemovePellet, nextNumFuelPellets ) )
                callStack.push( ( CallHandlers.Controller, nextNumFuelPellets + 1 ) )
                callStack.push( ( CallHandlers.Controller, nextNumFuelPellets - 1 ) )
            else: # We can safely divide the pellets, so setup a call stack for the division
                callStack.push( ( CallHandlers.DividePelletsByHalf, nextNumFuelPellets ) )
                callStack.push( ( CallHandlers.Controller, nextNumFuelPellets >> 1 )  )
        elif nextCallType == CallHandlers.DividePelletsByHalf:
            numOperationsAfterDividingPellets = 1 + numOperationsStack.pop()
            numOperationsStack.push( numOperationsAfterDividingPellets )
            cache[nextNumFuelPellets] = numOperationsAfterDividingPellets
        elif nextCallType == CallHandlers.AddOrRemovePellet:
            numOperationsAfterRemovingPellet = numOperationsStack.pop()
            numOperationsAfterAddingPellet = numOperationsStack.pop()
            numOperationsAfterAddingOrRemovingPellets = 1 + min( numOperationsAfterRemovingPellet, numOperationsAfterAddingPellet )
            numOperationsStack.push( numOperationsAfterAddingOrRemovingPellets )
            cache[nextNumFuelPellets] = numOperationsAfterAddingOrRemovingPellets

    return numOperationsStack.pop()

class StackElement:
       def __init__( self, object ):
           self.object = object
           self.next = None

class Stack:
    def __init__( self ):
        self.top = None

    def push( self, object ):
        newStackElement = StackElement( object )
        newStackElement.next = self.top
        self.top = newStackElement

    def pop( self ):
        if self.top is None: return None
        poppedElement = self.top
        self.top = self.top.next
        return poppedElement.object