Skip to content

818. Race Car

Difficulty Topics

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.

 

Example 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.

 

Constraints:

  • 1 <= target <= 104

Solution

race-car.py
class Solution:
    def racecar(self, target: int) -> int:
        queue = deque([(0, 1, 0)])
        visited = set([(0, 1)])

        while queue:
            x, speed, steps = queue.popleft()

            if x == target: return steps

            A = [(x + speed, speed * 2, steps + 1), (x, -1 if speed > 0 else 1, steps + 1)]

            for y, newSpeed, newSteps in A:
                if 0 < y < target * 2 and (y, newSpeed) not in visited:
                    queue.append((y, newSpeed, newSteps))
                    visited.add((y, newSpeed))

        return -1