Terminal-Controlled Grid Rover Simulator

Problem Statement

In an automated fulfillment warehouse, a fleet of robotic rovers navigates a bounded 2D grid floor. You are tasked with implementing a simulation engine that processes sequential navigation commands for multiple rovers.

The warehouse grid spans from coordinate (0, 0) (bottom-left corner) to (width - 1, height - 1) (top-right corner).

Each rover is initialized with a starting position (x, y) and a cardinal orientation ('N', 'E', 'S', or 'W'). Rovers are deployed sequentially: a rover processes its complete command sequence before the next rover begins. Once a rover completes its instructions, it parks at its final location and acts as an obstacle for subsequent rovers.

Rovers receive a string of instruction characters:

• 'L': Rotate 90 degrees counter-clockwise (e.g., 'N' becomes 'W').
• 'R': Rotate 90 degrees clockwise (e.g., 'N' becomes 'E').
• 'M': Move forward 1 grid unit in the current orientation.

Collision & Boundary Rules

• If a rover attempts to move into a cell that is outside the grid boundaries (x = width, y = height), the movement is ignored and the rover remains in its current cell.
• If a rover attempts to move into a cell occupied by a previously parked rover, the movement is ignored and the rover remains in its current cell.
• In both cases, the rover continues executing any remaining instructions.

Implement the function simulate_rovers.

Function Signature

def simulate_rovers(
    width: int,
    height: int,
    rovers: list[tuple[int, int, str, str]]
) -> list[tuple[int, int, str]]:
    pass

Input

• width: Integer representing grid width along the x-axis.
• height: Integer representing grid height along the y-axis.
• rovers: A list of tuples (x, y, orientation, commands) for each rover, in order of execution.

Output

• Return a list of tuples (final_x, final_y, final_orientation) for each rover in the order they were processed.

Constraints

• 1 <= width, height <= 1000
• 0 <= len(rovers) <= 500
• 0 <= len(commands) <= 10^4 per rover
• 0 <= x < width and 0 <= y < height for initial rover positions.
• Initial rover positions are guaranteed to not collide with previously parked rovers.

Example 1

width = 5
height = 5
rovers = [
    (1, 2, 'N', "LMLMLMLMM"),
    (3, 3, 'E', "MMRMMRMRRM")
]
output = simulate_rovers(width, height, rovers)
# Output: [(1, 3, 'N'), (5, 1, 'E')] -- wait, 5 is out of bounds!

Explanation for Example 1: Grid is 5x5 (0 <= x <= 4, 0 <= y <= 4).

• Rover 1 starts at (1, 2, 'N'). Executing "LMLMLMLMM" moves it to (1, 3, 'N').
• Rover 1 parks at (1, 3).
• Rover 2 starts at (3, 3, 'E'). It moves East: (4, 3), then tries to move East again to 5, but x=5 is out of bounds, so it stays at (4, 3). It turns South ('R'), moves to (4, 2), then (4, 1). Turns West ('R'), moves to (3, 1). Turns North ('R'), turns East ('R'), moves to (4, 1). Rover 2 ends at (4, 1, 'E').

Edge Cases

• Empty list of rovers returns [].
• Rover given commands that repeatedly hit boundary limits.
• Rover attempting to cross the position of an already parked rover.