Grid Robot Command Simulator

Problem Statement

In an automated fulfillment warehouse, mobile robots navigate a bounded 2D grid to transport inventory. You need to build a command simulator for one of these robots.

The grid has dimensions width by height, with coordinate (0, 0) at the bottom-left corner and (width - 1, height - 1) at the top-right corner. The robot starts at an initial position (x, y) facing one of four cardinal directions: 'N' (North, +y), 'E' (East, +x), 'S' (South, -y), or 'W' (West, -x).

The robot processes a string of single-character commands sequentially:

• 'L': Turn 90 degrees counter-clockwise (e.g., 'N' becomes 'W').
• 'R': Turn 90 degrees clockwise (e.g., 'N' becomes 'E').
• 'M': Move 1 unit forward in the direction currently faced.
• 'B': Move 1 unit backward (opposite to the direction currently faced) without changing orientation.

Movement Rules

• If a move ('M' or 'B') would cause the robot to move outside the grid boundaries (0 <= x < width, 0 <= y < height), the robot ignores that movement and remains in its current position before continuing to the next command.
• If a move would cause the robot to land on a coordinate occupied by an obstacle, the robot ignores that movement and remains in place before continuing to the next command.
• Turning commands ('L', 'R') are always executed successfully.

Implement the function simulate_robot that executes all commands and returns the robot's final state as a tuple (final_x, final_y, final_direction).

Function Interface

def simulate_robot(
    width: int,
    height: int,
    start: tuple[int, int, str],
    obstacles: list[tuple[int, int]],
    commands: str
) -> tuple[int, int, str]:
    pass

Constraints

• 1 <= width, height <= 10^4
• start is (x, y, dir) where 0 <= x < width, 0 <= y < height, and dir in {'N', 'E', 'S', 'W'}.
• 0 <= len(obstacles) <= 10^5
• All obstacle coordinates (ox, oy) satisfy 0 <= ox < width and 0 <= oy < height.
• The starting position is never an obstacle.
• 0 <= len(commands) <= 10^5
• commands consists only of characters 'L', 'R', 'M', and 'B'.

Examples

Example 1

width = 5
height = 5
start = (1, 1, 'N')
obstacles = [(1, 3)]
commands = "MMRMB"

# Step-by-step:
# Start: (1, 1, 'N')
# 'M' -> moves North to (1, 2, 'N')
# 'M' -> (1, 3) is an obstacle; move ignored, stays at (1, 2, 'N')
# 'R' -> turns East, now (1, 2, 'E')
# 'M' -> moves East to (2, 2, 'E')
# 'B' -> moves West to (1, 2, 'E')
# Output: (1, 2, 'E')

Example 2

width = 3
height = 3
start = (0, 0, 'S')
obstacles = []
commands = "MLM"

# Start: (0, 0, 'S')
# 'M' -> moves to (0, -1), out of bounds; ignored, stays at (0, 0, 'S')
# 'L' -> turns East, now (0, 0, 'E')
# 'M' -> moves East to (1, 0, 'E')
# Output: (1, 0, 'E')