Google FooBar Level 3 - Shortest path to 1

I recently found the Google Foobar challenges and am having a problem with level 3. The goal of the task is the find the minimum number of operations needed to transform a group of pellets down into 1, while following these rules:


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)

My code is as follows:

from math import log, ceil, floor
def answer(n):
    steps = 0
    steps_taken = " => {}"
    all_steps = "{}".format(n)
    n = int(n)
    if n  1:
        if n == 3:
            n -= 1
            all_steps += steps_taken.format(n)
            steps += 1
        elif n % 2 == 1:
            if n + 1 == 2**closest_power(n+1):
                n += 1
                all_steps += steps_taken.format(n)
            elif n - 1 == 2**closest_power(n-1):
                n -= 1
                all_steps += steps_taken.format(n)
            else:
                n -= 1
                all_steps += steps_taken.format(n)
            steps += 1
        else:
            n = n / 2
            all_steps += steps_taken.format(n)
            steps += 1

    print all_steps
    return steps

def closest_power(x):
    possible_results = floor(log(x, 2)), ceil(log(x, 2))
    return int(min(possible_results, key= lambda z: abs(x-2**z)))

This manages to perform the two test cases provided:

Inputs:

(string) n = "4"

Output:

(int) 2

Inputs:

(string) n = "15"

Output:

(int) 5

But it fails on others, that Google doesn't make available. Since I don't have access to the failing test cases, I'm looking for performance suggestions.

Right now the code is making the following assumptions:

• If the number is even, divide it by two. This should reduce the amount of space left to reach 1

• If a number i

Your intuition is correct. A blind subtraction is the root cause of the problem.

The odd number has the least significant bit equals to 1. An even number has it equal to 0. The more zeroes a number has at the tail, the more divisions you can perform (this is what makes powers of 2 so special - they have all bits but most significant equal to 0). So what you really want is to compute number of trailing 0 bits in n + 1 and n - 1 and pick one which has more:

tz0 = trailing_zero_bits(n + 1)
    tz1 = trailing_zero_bits(n - 1)
    if tz0 > tz1:
        n = n + 1
    else:
        n = n - 1

Notice how it eliminates computation of closest power of 2.

I leave the implementation of trailing_zero_bits for you. Hint: it is a one-line bit manipulation.

Edit. I am slow. It only took 6 years to realize that the suggested trailing_zero_bits is an overkill. All you need to do is to test second-to-LSB bit. Indeed, an odd number is either

****01

or

****11

In the first case an increment makes no sense. In the second so does decrement.

StackExchange Code Review Q#146044, answer score: 6