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 = " =&gt; {}"
    all_steps = "{}".format(n)
    n = int(n)
    if n &lt; 1:
        return 0
    while n &gt; 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 is odd, check if the next and previous numbers are a power of 2. If so, add or subtract one to get to that number. Since powers of 2 can be divided repeatedly, there will be no more adding/subtracting of pellets
If neither neighbor is a power of two, subtract one. I am betting this is the assumption that is causing problems. I don't have the mathematical background to provide it, but my thought was that moving closer to 1 is better. 
If the number is 3, subtract 1. Since both of its neighbors are a power of two, this is a special case. Additionally, moving from 3-&gt;2-&gt;1 is shorter than 3-&gt;4-&gt;2-&gt;1.
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 &gt; 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.