Simulate toppling board game outcome
Company: Chime
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a function that, given the board size N (3–9 inclusive) and a list of move strings, returns one of: "in progress", "player 1 is the winner", or "player 2 is the winner". The board is N×N. Players alternate turns and the active player changes on each Place move: all Topple moves between two Place moves belong to the player who executed the preceding Place. Move formats:
(
1) Place: "pXY" places one piece at row X, col Y. You may place only on an empty cell or a cell already owned by the current player. Placing on an empty cell claims it for the current player; otherwise increase the stack height.
(
2) Topple: "tXYD" topples all pieces from (X,Y) in direction D ∈ {u,r,d,l}. You may topple only from a cell you own with stack height ≥2. Pick up all pieces from (X,Y) and drop them one-by-one into adjacent cells starting from the next cell along D; pieces that go off-board are lost. Captures: if a dropped piece lands on a cell owned by the opponent, that piece is captured by the opponent and added to that cell’s stack (ownership of a cell is the owner of the stack on that cell). Game end: as soon as one player has zero pieces anywhere on the board, return the other player as the winner. Assume all moves are valid and well formed. Examples: ["p10", "p12", "p10", "t10r"] → "player 1 is the winner"; ["p00", "p22", "p02", "p22", "t22u", "t02l"] → "player 2 is the winner".
Quick Answer: This question evaluates a candidate's ability to implement a discrete board-game simulation, including state management, turn-based ownership semantics, stack-based piece handling, capture mechanics, and game termination detection.
Implement a function `solution(n, moves)` that simulates a two-player stacking game on an `n x n` board and returns one of:
- `"in progress"`
- `"player 1 is the winner"`
- `"player 2 is the winner"`
Rules:
1. The board starts empty.
2. Rows and columns are zero-indexed.
3. The first `Place` move is made by player 1, the second `Place` move by player 2, the third by player 1, and so on.
4. `Topple` moves do not switch turns. Every `Topple` belongs to the same player as the most recent `Place` move.
5. Each cell stores an owner and a stack height.
Move formats:
- `"pXY"` — Place one piece at row `X`, column `Y`.
- You may place only on an empty cell or a cell already owned by the current player.
- If the cell is empty, it becomes owned by the current player with height 1.
- Otherwise, increase that stack height by 1.
- `"tXYD"` — Topple the entire stack from row `X`, column `Y` in direction `D`, where `D` is one of `u`, `r`, `d`, `l`.
- You may topple only from a cell owned by the current player with stack height at least 2.
- Pick up all pieces from `(X, Y)`, making that cell empty.
- Drop the pieces one by one into consecutive cells starting from the next cell in direction `D`.
- If a piece would land off the board, it is lost.
- If a dropped piece lands on:
- an empty cell: that cell becomes owned by the current player
- the current player's cell: add the piece to that stack
- the opponent's cell: the current player captures that entire stack, so ownership flips to the current player and the dropped piece is added to the stack
Winning rule:
- Start checking for elimination only after both players have made at least one `Place` move.
- After each move, if one player has zero pieces anywhere on the board, the other player wins immediately.
- If no one has won after all moves, return `"in progress"`.
Assume all moves are valid and well formed.
Constraints
- 3 <= n <= 9
- 0 <= len(moves) <= 100000
- Each move is either `pXY` or `tXYD`
- X and Y are digits in the range [0, n - 1]
- D is one of `u`, `r`, `d`, `l`
- All moves are valid and well formed
Examples
Input: (3, ["p10", "p12", "p10", "t10r"])
Expected Output: "player 1 is the winner"
Explanation: Player 1 builds a stack of 2 at (1,0), then topples right. One piece lands on (1,1), and the next lands on player 2's cell (1,2), capturing it. Player 2 is left with zero pieces.
Input: (3, ["p00", "p22", "p02", "p22", "t22u", "t02l"])
Expected Output: "player 2 is the winner"
Explanation: After `p22`, both `t22u` and `t02l` belong to player 2 because no new Place move occurs. Player 2 first captures (0,2), then topples it left to capture (0,0), eliminating player 1.
Hints
- Store each board cell as two pieces of information: owner and stack height. Also keep total piece counts for each player so you can detect a winner in O(1) after every move.
- During a topple, only the cells from the source to the board edge can receive pieces. Since `n <= 9`, at most `n - 1` dropped pieces stay on the board; the rest are immediately lost.