[Google Question][LeetCode] Race Car

Problem: 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->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example:

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

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

Approach: If you see its kind of a graph. Where a node is connected to another node using A and R instructions. The value at node is position and speed. Now given this connected graph, we need to find the shortest path from a node (0, 1) to a node with (target, any_speed).

Given we need to find shortest path, we can apply BFS here. That's all!

Implementation in C#:

    public int Racecar(int target) 

    {

        return MinInstructionsBFS(target);

    }

    

    private int MinInstructionsBFS(int target)

    {

        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();

        HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>();

        Tuple<int, int> initialPosition = new Tuple<int, int>(0, 1);

        queue.Enqueue(initialPosition);

        visited.Add(initialPosition);

        int numOfInstructions = 0;

        

        while (queue.Count > 0)

        {

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                Tuple<int, int> currNode = queue.Dequeue();

                int currPos = currNode.Item1;

                int currSpeed = currNode.Item2;

                if (currPos == target)

                {

                    return numOfInstructions;

                }

                // Accelerate 

                if (currPos + currSpeed < 2 * target && currPos + currSpeed >= 0)

                {

                    Tuple<int, int> newNode = new Tuple<int, int>(currPos + currSpeed, currSpeed * 2);

                    if (!visited.Contains(newNode))

                    {

                        visited.Add(newNode);

                        queue.Enqueue(newNode);

                    }

                }

                // Reverse

                if (currSpeed > 0 && currPos + currSpeed > target)

                {

                    Tuple<int, int> newNode = new Tuple<int, int>(currPos, -1);

                    if (!visited.Contains(newNode))

                    {

                        visited.Add(newNode);

                        queue.Enqueue(newNode);

                    }

                }

                else if (currSpeed <= 0 && currPos + currSpeed < target)

                {

                    Tuple<int, int> newNode = new Tuple<int, int>(currPos, 1);

                    if (!visited.Contains(newNode))

                    {

                        visited.Add(newNode);

                        queue.Enqueue(newNode);

                    }

                }

            }        

            ++numOfInstructions;    

        }

        return -1;

    }

Complexity: O(2^n)