[Google foobar] Level 3 Fuel Injection Perfection

Google foobar challenge level 3 - Fuel Injection Perfection

Description

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
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:

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

Idea

BFS로 각 연산(+1, -1, /2)이 가능하다면 해당 연산을 돌리면 된다.

Code

import java.math.BigInteger;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution {
    private static final BigInteger GOAL = BigInteger.ONE;
    public static int solution(String x) {
        if(x.equals("1")) return 0;
        int res = 1;
        Queue<BigInteger> q = new LinkedList<>();
        Set<BigInteger> visit = new HashSet<>();
        q.add(new BigInteger(x));
        visit.add(new BigInteger(x));
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-- != 0) {
                BigInteger bi = q.poll();
                BigInteger addOne = bi.add(BigInteger.ONE);
                BigInteger minusOne = bi.subtract(BigInteger.ONE);
                if(addOne.equals(GOAL) || minusOne.equals(GOAL)) return res;
                if(!visit.contains(addOne)) {
                    q.add(addOne);
                    visit.add(addOne);
                }
                if(!visit.contains(minusOne)) {
                    q.add(minusOne);
                    visit.add(minusOne);
                }
                if(bi.and(BigInteger.ONE).equals(BigInteger.ZERO)) {
                    BigInteger devideTwo = bi.shiftRight(1);
                    if(devideTwo.equals(GOAL)) return res;
                    if(!visit.contains(devideTwo)) {
                        q.add(devideTwo);
                        visit.add(devideTwo);
                    }
                }
            }
            res++;
        }
        return -1;
    }
}