Race Car

Race Car is a deceptively tricky shortest-path problem. A car on an infinite number line obeys a tiny instruction set, and we want the fewest instructions to land exactly on a target. The key realization: this is a shortest-path search, and the right tool for "fewest steps" is BFS.

The slow way first

You might try to reason out the instruction string by hand, but the choices branch fast: at every position you can either keep accelerating or reverse, and there is no obvious greedy rule (sometimes you must overshoot and come back). Hand-tuning breaks down, and a naive recursion explores the same (pos, speed) situations over and over — exponential work.

The question to ask: what fully describes where the car is and what it can do next? Just two numbers: its position and its speed. Everything else is history.

The idea: BFS over (position, speed) states

Treat each (pos, speed) pair as a node in a graph. From any state, the two instructions lead to exactly two neighbor states. Because every instruction costs exactly one move, the number of instructions equals the BFS depth. So run BFS from (0, 1): the first time we pop a state whose pos equals the target, its depth is the shortest answer.

The key insight: speed can grow (1, 2, 4, …) and go negative, so the state space is large — but BFS explores it in order of instruction count, guaranteeing the first hit is optimal.

Walk through it

Step through the animation for target = 3. The car pointer marks the current position on the track; the labels show the popped state and the growing queue. We start at (0, 1). Applying 'A' reaches (1, 2); from there another 'A' lands exactly on 3. That is two instructions — "AA" — and BFS confirms nothing shorter exists.

Pseudocode

queue = [(pos=0, speed=1, steps=0)]
while queue is not empty:
    pop (pos, speed, steps) from the front
    if pos == target:
        return steps                       # shortest, because BFS
    # 'A' accelerate: move then double speed
    push (pos + speed, speed * 2, steps + 1)
    # 'R' reverse: flip the sign of speed
    new_speed = -1 if speed > 0 else 1
    push (pos, new_speed, steps + 1)

The Python solution

from collections import deque
 
def race_car(target):
    q = deque([(0, 1, 0)])      # pos, speed, steps
    while q:
        pos, speed, steps = q.popleft()
        if pos == target:
            return steps
        # 'A': accelerate
        q.append((pos + speed, speed * 2, steps + 1))
        # 'R': reverse direction
        new_speed = -1 if speed > 0 else 1
        q.append((pos, new_speed, steps + 1))

• The queue holds (pos, speed, steps) triples; steps is the BFS depth (instruction count so far).
• q.popleft() pulls states in FIFO order, which is what makes this BFS rather than DFS.
• Lines 7-8 are the heart: the first time we pop a state at the target, its steps is provably the minimum.
• 'A' adds the neighbor (pos + speed, speed * 2, steps + 1) — move first, then double.
• 'R' keeps pos and flips the speed sign, costing one instruction.

Complexity

In practice you bound the search (positions stay near the target and speeds stay below the smallest power of two past it), which keeps the reachable state count roughly O(T log T). The log T factor comes from speed doubling.

When this pattern shows up

Practice