818. Race Car

Problem Link

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:

  <ul>
  	<li><code>position += speed</code></li>
  	<li><code>speed *= 2</code></li>
  </ul>
  </li>
  <li>When you get an instruction <code>&#39;R&#39;</code>, your car does the following:
  <ul>
  	<li>If your speed is positive then <code>speed = -1</code></li>
  	<li>otherwise <code>speed = 1</code></li>
  </ul>
  Your position stays the same.</li>
  

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

---

Python3

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