# Race Car

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`

https://leetcode.com/problems/race-car/

## 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)`