2
\$\begingroup\$

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:
        return 0
    while 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 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->2->1 is shorter than 3->4->2->1.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This was very helpful. Thank you for the pointer about trailing zeros. Implementing the trailing_zero_bits check (and removing the closest power of 2 check I was doing) now passes 8 out of 10 of the cases! I'll see if I can figure out these last two cases on my own. It's difficult without actually seeing the data they are testing though. \$\endgroup\$ – Confused in the East Nov 3 '16 at 18:32
  • \$\begingroup\$ @ConfusedintheEast Are they fail with WA or TLE or something else? \$\endgroup\$ – vnp Nov 3 '16 at 18:56
  • \$\begingroup\$ Unfortunately, all it tells me is that the test failed: i.imgur.com/jMFBwXU.png \$\endgroup\$ – Confused in the East Nov 3 '16 at 19:31
  • \$\begingroup\$ This algorithm would seem to be incorrect for n = 3. But it might be correct for n > 3. \$\endgroup\$ – JS1 Nov 5 '16 at 12:12
  • \$\begingroup\$ Can we have a solution in java as well? can we simplify the same using bit manipulation when doing in Java? Just curious \$\endgroup\$ – AKIWEB May 4 '17 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.