yokolet's notelets

  1. Sorting and Searching
  2. Race Car

Sorting and Searching

Race Car

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)
Hard
Breadth-First Search