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.