818. Race Card

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.

Now for some target position, say 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.

Note:

• 1 <= target <= 10000.

Thoughts:

1. Dijistra + prunning: TLE

2. Since A is always moving faster: we can first always A until reaching the target (detecting whether passed the target), and then turn back (Original Post)

Code:

1. Dijkstra:

   class Solution:
       def racecar(self, target: int) -> int:
           hq = [(0, 0, 1)]  #   seq_len, pos, speed,
           pos_record = set()
           
           while True:
               seq_len, pos, speed = heapq.heappop(hq)
               if pos == target:
                   return seq_len
               
               # Pruning
               if (pos, speed) in pos_record: 
                   continue
               pos_record.add((pos, speed))
               
               # A
               heapq.heappush(hq, (seq_len + 1, pos + speed, speed * 2 ))
               
               # R 
               rev_speed = -1 if speed > 0 else 1
               heapq.heappush(hq, (seq_len + 1, pos, rev_speed))