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)