Race Car

XXX. Race Car Shortest Instructions

BFS

Graph

Level Order

Problem Statement:

Find the minimum number of instructions needed for a car to reach a target position. Car can either accelerate (A) or reverse (R).

• Car starts at position 0 with speed 1
• 'A' doubles speed in current direction
• 'R' reverses direction with speed reset to 1
• Need to find shortest sequence of instructions

Key Points:

• **Level Order BFS**:
  • Track level explicitly for move count
  • Process all nodes at each level together
  • Return level when target found
• **State Management**:
  • Position and speed define state
  • Use visited set to avoid cycles
  • Bound position to (0, 2*target)

Implementation Notes:

• **Level Processing**:
  • Get size of current level
  • Process all nodes at that level
  • Increment level after finishing
• **Movement Rules**:
  • Accelerate: position += speed, speed *= 2
  • Reverse: Keep position, reverse speed to ±1
  • Check bounds after each move

Example:

For target = 3:

• Level 0: [0,1] (initial)
• Level 1: [1,2] (after A)
• Level 2: [3,4] (after A, target reached)
• Return 2 (minimum instructions: AA)

Java Implementation:

public int racecar(int target) {
    Deque queue = new LinkedList<>();
    queue.offerLast(new int[] {0, 1});         // [position, speed]
    
    Set visited = new HashSet<>();
    visited.add(0 + " " + 1);                  // Track visited states
    
    int level = 0;                             // Initialize level
    while (!queue.isEmpty()) {
        int size = queue.size();               // Size of current level
        while (size-- > 0) {
            int[] cur = queue.pollFirst();
            if (cur[0] == target) return level;
            
            // Try accelerate (A)
            int[] nxt = new int[] {cur[0] + cur[1], cur[1] << 1};
            String key = nxt[0] + " " + nxt[1];
            
            if (!visited.contains(key) && 
                0 < nxt[0] && nxt[0] < (target << 1)) {
                queue.offerLast(nxt);
                visited.add(key);
            }
            
            // Try reverse (R)
            nxt = new int[] {cur[0], cur[1] > 0 ? -1 : 1};
            key = nxt[0] + " " + nxt[1];
            
            if (!visited.contains(key) && 
                0 < nxt[0] && nxt[0] < (target << 1)) {
                queue.offerLast(nxt);
                visited.add(key);
            }
        }
        level++;                               // Move to next level
    }
    return -1;
}

Python Implementation:

def racecar(self, target: int) -> int:
    queue = collections.deque([(0, 1)])    # (position, speed)
    visited = {(0, 1)}                     # Track visited states
    
    level = 0
    while queue:
        size = len(queue)                  # Size of current level
        
        for _ in range(size):              # Process current level
            pos, speed = queue.popleft()
            if pos == target:
                return level
            
            # Try accelerate
            next_pos = pos + speed
            next_speed = speed * 2
            state = (next_pos, next_speed)
            
            if state not in visited and 0 < next_pos < target * 2:
                queue.append(state)
                visited.add(state)
            
            # Try reverse
            next_speed = -1 if speed > 0 else 1
            state = (pos, next_speed)
            
            if state not in visited and 0 < pos < target * 2:
                queue.append(state)
                visited.add(state)
                
        level += 1                         # Move to next level
    
    return -1

C++ Implementation:

int racecar(int target) {
    queue> q;              // {position, speed}
    q.push({0, 1});
    
    set> visited;          // Track visited states
    visited.insert({0, 1});
    
    int level = 0;
    while (!q.empty()) {
        int size = q.size();              // Size of current level
        
        while (size--) {                  // Process current level
            auto [pos, speed] = q.front();
            q.pop();
            
            if (pos == target) return level;
            
            // Try accelerate
            int next_pos = pos + speed;
            int next_speed = speed * 2;
            
            if (visited.find({next_pos, next_speed}) == visited.end() && 
                next_pos > 0 && next_pos < target * 2) {
                q.push({next_pos, next_speed});
                visited.insert({next_pos, next_speed});
            }
            
            // Try reverse
            next_speed = speed > 0 ? -1 : 1;
            if (visited.find({pos, next_speed}) == visited.end() && 
                pos > 0 && pos < target * 2) {
                q.push({pos, next_speed});
                visited.insert({pos, next_speed});
            }
        }
        level++;                          // Move to next level
    }
    return -1;
}

Complexity:

Time Complexity: O(t log t), where t is target position
Space Complexity: O(t log t) for queue and visited set