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))
                    
                    
                

Last updated

Was this helpful?