Generalized m x n Tic-Tac-Toe with a k-in-a-Row Win Check
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a tic-tac-toe game played on an `m x n` board between two players, where a player wins by placing `k` of their marks in a consecutive line. The interview version is a class:
- `TicTacToe(m, n, k)` initializes an empty `m x n` board with win condition `k`.
- `move(row, col, player)` places a mark for `player` (1 or 2) at `(row, col)`. The move is guaranteed to be valid. It returns `0` if no one wins, `1` if player 1 wins, and `2` if player 2 wins.
A player wins by placing `k` of their marks in a consecutive line: horizontally, vertically, or diagonally in either direction.
For this console version, implement a function that creates a fresh game, applies the moves in order, and returns the value `move` would return for each one.
### Function Signature
```python
def play_tic_tac_toe(m: int, n: int, k: int, moves: list[tuple[int, int, int]]) -> list[int]:
```
### Rules
- Rows and columns are 0-indexed, and each move is `(row, col, player)`.
- Every move is valid: the cell is on the board and empty, and `player` is 1 or 2. Players are not guaranteed to alternate.
- A move wins if, once it is placed, its player has at least `k` of their own marks in an unbroken run through the placed cell, along the row, the column, the main diagonal (top-left to bottom-right) or the anti-diagonal (top-right to bottom-left).
- The result for a move is the player's id if that move wins, and `0` otherwise.
- No move follows a winning move, so the list ends either with a win or with no winner.
- The output list has exactly one entry per move, in move order.
### Constraints
- `1 <= m, n <= 1000`
- `1 <= k <= max(m, n)`
- `1 <= len(moves) <= min(m * n, 10^5)`
- `0 <= row < m`, `0 <= col < n`, and `player` is 1 or 2.
- These numeric limits are practice bounds; the original report stated none.
### Examples
**Example 1**
```text
m = 3, n = 3, k = 3
moves = [(0, 0, 1), (0, 2, 2), (2, 2, 1), (1, 1, 2), (2, 0, 1), (1, 0, 2), (2, 1, 1)]
Output: [0, 0, 0, 0, 0, 0, 1]
```
The last move completes the bottom row `(2, 0)`, `(2, 1)`, `(2, 2)` for player 1.
**Example 2**
```text
m = 4, n = 5, k = 3
moves = [(0, 4, 2), (3, 0, 1), (1, 3, 2), (0, 0, 1), (2, 2, 2)]
Output: [0, 0, 0, 0, 2]
```
Player 2's marks at `(0, 4)`, `(1, 3)`, `(2, 2)` form three in a row on an anti-diagonal.
**Example 3**
```text
m = 2, n = 4, k = 4
moves = [(0, 0, 1), (1, 0, 2), (0, 1, 1), (1, 1, 2), (0, 2, 1), (1, 2, 2), (0, 3, 1)]
Output: [0, 0, 0, 0, 0, 0, 1]
```
With only two rows, only a horizontal line can reach length 4. Player 1 completes row 0 on the last move.
Overview: Implement tic-tac-toe on an m by n board where a player wins with k consecutive marks in a row, column or either diagonal, returning the winner after each move. Tests incremental win detection that avoids rescanning the board, plus careful handling of edges and both diagonal directions.
Two players play tic-tac-toe on an `m x n` board. A player wins by placing `k` of their own marks in a consecutive line: horizontally, vertically, or diagonally in either direction.
In the interview version this is a class: `TicTacToe(m, n, k)` creates an empty `m x n` board with win condition `k`, and `move(row, col, player)` places a mark for `player` (1 or 2) at `(row, col)`. The move is guaranteed to be valid. `move` returns `0` if no one wins, `1` if player 1 wins, and `2` if player 2 wins.
Implement `play_tic_tac_toe(m, n, k, moves)`, which creates a fresh game, applies the moves in order, and returns the value `move` would return for each one. `moves` is a single list of `[row, col, player]` triples.
**Rules**
- Rows and columns are 0-indexed, and each move is `[row, col, player]`.
- Every move is valid: the cell is on the board and empty, and `player` is 1 or 2. Players are not guaranteed to alternate.
- A move wins if, once it is placed, its player has at least `k` of their own marks in an unbroken run through the placed cell, along the row, the column, the main diagonal (top-left to bottom-right) or the anti-diagonal (top-right to bottom-left).
- The result for a move is the player's id if that move wins, and `0` otherwise.
- No move follows a winning move, so the list ends either with a win or with no winner.
- Return a list with exactly one entry per move, in move order.
**Example 1**
```
m = 3, n = 3, k = 3
moves = [[0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output: [0, 0, 0, 0, 0, 0, 1]
```
The last move completes the bottom row `(2, 0)`, `(2, 1)`, `(2, 2)` for player 1.
**Example 2**
```
m = 4, n = 5, k = 3
moves = [[0, 4, 2], [3, 0, 1], [1, 3, 2], [0, 0, 1], [2, 2, 2]]
Output: [0, 0, 0, 0, 2]
```
Player 2's marks at `(0, 4)`, `(1, 3)`, `(2, 2)` form three in a row on an anti-diagonal.
**Constraints**
- `1 <= m, n <= 1000`
- `1 <= k <= max(m, n)`
- `1 <= len(moves) <= min(m * n, 10^5)`
- `0 <= row < m`, `0 <= col < n`, and `player` is 1 or 2.
- No value exceeds 2^31 - 1: the largest derived quantity, `m * n <= 10^6`, fits in a 32-bit signed integer.
- These numeric limits are practice bounds; the original report stated none.
Constraints
- 1 <= m, n <= 1000
- 1 <= k <= max(m, n)
- 1 <= len(moves) <= min(m * n, 10^5)
- 0 <= row < m, 0 <= col < n, and player is 1 or 2
- Every move lands on an empty cell; players are not guaranteed to alternate
- No move follows a winning move
- All values, including m * n <= 10^6, fit in a 32-bit signed integer
Examples
Input: (3, 3, 3, [[0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]])
Expected Output: [0, 0, 0, 0, 0, 0, 1]
Explanation: Source example 1: player 1 fills the middle of the bottom row, so the marks on both sides of the new cell must be counted.
Input: (4, 5, 3, [[0, 4, 2], [3, 0, 1], [1, 3, 2], [0, 0, 1], [2, 2, 2]])
Expected Output: [0, 0, 0, 0, 2]
Explanation: Source example 2: player 2 completes the anti-diagonal (0, 4), (1, 3), (2, 2) at its lower-left end.
Hints
- A new win can only come from a line that passes through the cell that was just played.
- There are four line directions through a cell, and a run through it can extend on both sides; it ends at the board edge, an empty cell or the other player's mark.
- The rule is at least k, so a move that joins two shorter runs can make a run longer than k and still win.