Terminal-Controlled Grid Rover Simulator
Company: Shopify
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Technical Screen
You are building a command-line simulator for autonomous rovers moving on a rectangular grid (think of a warehouse floor or a planetary plateau). Rovers receive movement instructions through a terminal, and the program must report where each rover ends up.
### The grid
Cells are addressed by integer coordinates $(x, y)$ with $0 \le x \le M_X$ and $0 \le y \le M_Y$. The cell $(0, 0)$ is the bottom-left corner: $x$ increases to the **east** (right) and $y$ increases to the **north** (up).
### A rover
Each rover has a position $(x, y)$ and a heading, one of:
- `N` — north (+y)
- `E` — east (+x)
- `S` — south (-y)
- `W` — west (-x)
### Commands
A rover is given a command string over the characters `L`, `R`, `M`:
- `L` — turn 90° to the left (counter-clockwise) in place; position is unchanged. Heading cycles `N → W → S → E → N`.
- `R` — turn 90° to the right (clockwise) in place; position is unchanged. Heading cycles `N → E → S → W → N`.
- `M` — move one cell forward in the rover's current heading.
### Multiple rovers share the grid
- **At most one rover may occupy a cell at any time.**
- Rovers are processed **sequentially in input order**: a rover executes its entire command string before the next rover begins moving.
- An `M` that would move a rover **off the grid** (outside $[0, M_X] \times [0, M_Y]$) is **ignored** — the rover stays in its current cell, keeps its heading, and proceeds to the next command.
- An `M` that would move a rover into a cell **currently occupied by another rover** is also **ignored** (same behavior: stay in place, continue).
- `L` and `R` always succeed.
### Input (read from standard input)
```
Line 1: M_X M_Y (two integers: the maximum x and y coordinates, inclusive)
Line 2: R (an integer: the number of rovers, R >= 0)
Then, for each of the R rovers, two lines:
Line A: x y D (starting cell and heading D in {N, E, S, W})
Line B: <commands> (a string over {L, R, M}; may be empty)
```
You may assume every starting cell lies within the grid and that the starting cells are initially distinct.
### Output (write to standard output)
For each rover, in input order, print one line:
```
x y D
```
its final cell and heading.
If `R = 0`, print nothing.
### Example
Input:
```
5 5
2
1 2 N
LMLMLMLMM
3 3 E
MMRMMRMRRM
```
Output:
```
1 3 N
5 1 E
```
Explanation: Rover 1 starts at $(1, 2)$ facing `N`, traces a small loop, and finishes at $(1, 3)$ still facing `N`. Rover 2 starts at $(3, 3)$ facing `E` and finishes at $(5, 1)$ facing `E`. In this case neither rover leaves the grid or collides, so every command is applied.
Quick Answer: This question evaluates a candidate's ability to model stateful simulation logic, translating grid coordinates, heading rotations, and sequential command processing into correct program state. It tests simulation and state-machine design skills within coding interviews, including handling boundary conditions and collisions between multiple entities. The scenario represents a practical application of simulation reasoning rather than pure algorithmic theory.
Simulate autonomous rovers on a rectangular grid.
Cells are integer coordinates (x, y) with 0 <= x <= mx and 0 <= y <= my. (0, 0) is the bottom-left corner: x increases to the east (right), y increases to the north (up). Each rover has a position and a heading in {N, E, S, W}.
Each rover is given a command string over {L, R, M}:
- `L` turns 90 degrees left (counter-clockwise) in place: N -> W -> S -> E -> N.
- `R` turns 90 degrees right (clockwise) in place: N -> E -> S -> W -> N.
- `M` moves one cell forward in the current heading (N: +y, E: +x, S: -y, W: -x).
Rules for multiple rovers:
- At most one rover may occupy a cell at any time. All starting cells are distinct.
- Rovers are processed sequentially in input order: a rover runs its entire command string before the next rover begins. While a rover moves, every other rover occupies its current cell (rovers not yet processed sit on their starting cells; finished rovers sit on their final cells).
- An `M` that would move a rover off the grid is ignored (the rover keeps its cell and heading and continues with the next command).
- An `M` that would move a rover into a cell currently occupied by another rover is also ignored.
- `L` and `R` always succeed.
Write `solution(mx, my, rovers)`:
- `mx`, `my`: the inclusive maximum x and y coordinates.
- `rovers`: a list of strings, one per rover, formatted `"x y D commands"` where `x y` is the starting cell, `D` is the starting heading, and `commands` is the command string (which may be empty, in which case the string is just `"x y D"`).
Return a list of strings, one per rover in input order, each formatted `"x y D"` giving that rover's final cell and heading. If `rovers` is empty, return an empty list.
Constraints
- 0 <= x <= mx and 0 <= y <= my for every cell; the grid has (mx+1)*(my+1) cells.
- R >= 0 rovers; if R = 0 the result is an empty list.
- Every starting cell lies within the grid and all starting cells are distinct.
- Each heading D is one of N, E, S, W; each command char is one of L, R, M.
- A command string may be empty (the rover then stays put).
Examples
Input: (5, 5, ['1 2 N LMLMLMLMM', '3 3 E MMRMMRMRRM'])
Expected Output: ['1 3 N', '5 1 E']
Explanation: The worked example. Rover 1 traces a small loop back near its start and finishes at (1,3) facing N; rover 2 zig-zags to the corner and finishes at (5,1) facing E. Neither leaves the grid nor collides, so every command applies.
Input: (2, 2, ['0 0 E M', '1 0 E M'])
Expected Output: ['0 0 E', '2 0 E']
Explanation: Collision: rover 1 at (0,0) facing E tries to step into (1,0), which is occupied by the not-yet-moved rover 2, so the M is ignored and it stays at (0,0). Rover 2 then moves freely from (1,0) to (2,0).
Input: (3, 3, ['0 0 S M'])
Expected Output: ['0 0 S']
Explanation: Off-grid: facing S at (0,0), an M would go to y = -1, outside the grid, so the command is ignored and the rover keeps its cell and heading.
Input: (5, 5, ['2 2 N LLLL'])
Expected Output: ['2 2 N']
Explanation: Four left turns cycle the heading N -> W -> S -> E -> N, returning to N; no M means the position never changes.
Input: (5, 5, ['2 3 W'])
Expected Output: ['2 3 W']
Explanation: Empty command string: the rover stays at its starting cell and heading.
Input: (5, 5, [])
Expected Output: []
Explanation: R = 0: no rovers, so the output is empty.
Input: (5, 5, ['1 1 N MMMMM'])
Expected Output: ['1 5 N']
Explanation: Boundary clamp: the rover moves north from (1,1) to (1,5); the fifth M would reach y = 6 (off grid) and is ignored, leaving it at (1,5).
Input: (5, 5, ['2 2 N', '2 1 N MMR'])
Expected Output: ['2 2 N', '2 1 E']
Explanation: Blocking + turn: rover 1 has no commands and stays at (2,2). Rover 2 at (2,1) facing N tries M twice into (2,2), both ignored because rover 1 sits there; the final R turns it to E, so it finishes at (2,1) facing E.
Hints
- Model each 90-degree turn as a lookup on the current heading rather than an angle: precompute left/right maps and a heading -> (dx, dy) map.
- Keep a single set of every rover's current cell. Because rovers run one at a time, this set already reflects finished rovers (at their final cells) and not-yet-started rovers (at their start cells).
- For an `M`, first reject moves that leave [0, mx] x [0, my], then reject moves into an occupied cell; otherwise update the set (remove old cell, add new) and advance. A forward move never lands on the rover's own cell, so no self-collision check is needed.