Published: Dec 15, 2022

## Problem Description

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`

.Given a target position

`target`

, return the length of the shortest sequence of instructions to get there.Constraints:

`1 <= target <= 10**4`

## Examples

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

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

## How to Solve

For this problem, a couple of approaches are there: dynamic programming, breadth-first search, or priority queue (heap). Among those, the solution here took the breadth-first search approach. It is a relatively simple solution. In the queue, the solution saves position and speed pairs. When the race car goes forward, (position + speed, speed * 2) will be added to the queue as a next state. The race car is allowed to go back. When the speed is negative and position + speed is less than the target, or the speed is positive and position + speed is greater than the target, the backward move has an effect. As the problem describes, the position stays the same. So, (position, backward speed of -1 or 1) will be added to the queue as a next state.

## Solution

```
class RaceCar {
public:
int racecar(int target) {
queue<pair<long long int, long long int>> q; // position, speed
q.push({0, 1});
int steps = 0;
while (!q.empty()) {
int q_len = q.size();
for (auto i = 0; i < q_len; ++i) {
auto [p, s] = q.front();
q.pop();
if (p == target) { return steps; }
q.push({p + s, s * 2});
int back = s > 0 ? -1 : 1;
if (((p + s) < target && s < 0) || ((p + s) > target && s > 0)) {
q.push({p, back});
}
}
++steps;
}
return -1;
}
};
```

```
```

```
```

```
class RaceCar:
def racecar(self, target: int) -> int:
q = [(0, 1)] # position, speed
steps = 0
while q:
q_len = len(q)
for i in range(q_len):
p, s = q.pop(0)
if p == target:
return steps
q.append((p + s, s * 2))
back = -1 if s > 0 else 1
if ((p + s) < target and s < 0) or\
((p + s) > target and s > 0):
q.append((p, back))
steps += 1
```

```
```

## Complexities

- Time:
`O(t)`

– t: target - Space:
`O(t)`