Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):


	When you get an instruction 'A', your car does the following:

	
		position += speed
		speed *= 2
	
	
	When you get an instruction 'R', your car does the following:
	
		If your speed is positive then speed = -1
		otherwise speed = 1
	
	Your position stays the same.


For example, after commands "AAR", your car goes to positions 0 --&gt; 1 --&gt; 3 --&gt; 3, and your speed goes to 1 --&gt; 2 --&gt; 4 --&gt; -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

&nbsp;
Example 1:

Input: target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0 --&gt; 1 --&gt; 3.


Example 2:

Input: target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0 --&gt; 1 --&gt; 3 --&gt; 7 --&gt; 7 --&gt; 6.


&nbsp;
Constraints:


	1 &lt;= target &lt;= 104


class Solution:
    def racecar(self, target: int) -> int:
        q = [(0, 1)]
        steps = 0

        while q:
            num = len(q)
            for i in range(num):
                pos, speed = q.pop(0)
                if pos == target:
                    return steps
                q.append((pos+speed, speed*2))
                rev_speed = -1 if speed > 0 else 1
                if (pos+speed) < target and speed < 0 or (pos+speed) > target and speed > 0:
                    q.append((pos, rev_speed))
            steps += 1
class Solution {
    public int racecar(int target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 1, 0});
        Set<String> visited = new HashSet<>();

        while(!queue.isEmpty()){
            int[] item = queue.poll();
            int currPos = item[0];
            int currSpeed = item[1];
            int distance = item[2];

            if(currPos == target)
                return distance;

            // Choosing A
            int nextPos = currPos + currSpeed;
            int nextSpeed = currSpeed * 2;
            String posSpeed = new StringBuilder().append(nextPos).append(",").append(nextSpeed).toString();

            // If the particular state (position & speed) is not encountered earlier then we explore that state
            // And we also check if the nextPos is not beyond twice the size of target, then there is no point in exploring that route
            if(!visited.contains(posSpeed) && Math.abs(nextPos) < 2 * target){
                visited.add(posSpeed);
                queue.add(new int[]{nextPos, nextSpeed, distance + 1});
            }

            // Choosing R
            // We go in reverse only when we are moving away from the target in the positive or in the negative direction
            if((currPos + currSpeed > target && currSpeed > 0) || (currPos + currSpeed < target && currSpeed < 0)) {
                nextSpeed = currSpeed > 0 ? -1 : 1;
                posSpeed = new StringBuilder().append(currPos).append(",").append(nextSpeed).toString();

                if(!visited.contains(posSpeed) && Math.abs(currPos) < 2 * target){
                    visited.add(posSpeed);
                    queue.add(new int[]{currPos, nextSpeed, distance + 1});
                }
            }
        }
        return -1;
    }
}
struct Position {
    long long int pos;
    long long int speed;
    long long int moves;

    Position(int pos, int speed, int moves) {
        this -> pos = pos;
        this -> speed = speed;
        this -> moves = moves;
    }
};

class Solution {
public:
    int racecar(int target) {
        queue<Position> q;
        Position p(0, 1, 0);
        q.push(p);

        set<pair<long long int, long long int>> s;

        while(!q.empty()) {
            Position u = q.front();
            q.pop();

            if(u.pos == target) return u.moves;

            if(s.find({u.pos, u.speed}) != s.end()) continue;
            else {
                s.insert({u.pos, u.speed});

                // only cases when you might need to move backwards
                if((u.pos + u.speed > target && u.speed > 0) ||
                   (u.pos + u.speed < target && u.speed < 0)) {
                    long long int speed = u.speed > 0 ? -1 : 1;
                    Position bkwd(u.pos, speed, u.moves + 1);
                    q.push(bkwd);
                }

                Position fwd(u.pos + u.speed, 2 * u.speed, u.moves + 1);
                q.push(fwd);
            }
        }

        return -1;
    }
};
var racecar = function(target) {
    let queue = [[0, 1, 0]];
    let visited = new Set(['0,1']);

    while(queue.length > 0) {
        const [pos, speed, distance] = queue.shift();

        if(pos === target) return distance;

        const posA = pos + speed;
        const speedA = speed * 2;
        const keyA = posA + ',' + speedA;

        const posR = pos;
        const speedR = speed > 0 ? -1 : 1;
        const keyR = posR + ',' + speedR;

        if(!visited.has(keyA) && posA >= 0 && posA <= 2*target) {
            visited.add(keyA);
            queue.push([posA, speedA, distance + 1]);
        }

        if(!visited.has(keyR) && posR >= 0 && posR <= 2*target) {
            visited.add(keyR);
            queue.push([posR, speedR, distance + 1]);
        }
    }
};
Race Car