Find the Winner of a Connect Four Game from Its Move Sequence
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Two players play Connect Four on a grid with `rows` rows and `cols` columns. They take turns dropping a piece into a column, and the piece falls to the lowest empty cell of that column. Given the sequence of columns played, return the player who first gets four pieces in a line.
### Function Signature
```python
def connect_four_winner(rows: int, cols: int, moves: list[int]) -> int:
```
### Rules
- The grid starts empty. Player 1 moves first and the players alternate, so `moves[i]` is played by player 1 when `i` is even and by player 2 when `i` is odd.
- `moves[i]` is a column index from `0` to `cols - 1`. The piece occupies the lowest empty cell of that column.
- A player wins as soon as four of their pieces occupy four consecutive cells along a row, a column or either diagonal. A line longer than four also counts.
- Return `1` or `2` for the first player to win; any moves after the winning move are ignored. Return `0` if nobody has won after all the moves.
### Constraints
- `1 <= rows <= 100` and `1 <= cols <= 100`
- `0 <= len(moves) <= rows * cols`
- `0 <= moves[i] <= cols - 1`, and no column receives more than `rows` pieces over the whole list.
### Examples
In the picture, `X` is player 1, `O` is player 2, and the last line is the bottom row of the grid.
**Example 1**
```text
Input: rows = 6, cols = 7, moves = [0, 1, 1, 2, 2, 3, 2, 3, 3, 0, 3]
Output: 1
. . . . . . .
. . . . . . .
. . . X . . .
. . X X . . .
O X X O . . .
X O O O . . .
```
The last move, by player 1, completes the diagonal that rises from the bottom-left corner. Player 2 has three in a row along the bottom but never gets the fourth.
**Example 2**
```text
Input: rows = 6, cols = 7, moves = [0, 1, 0, 2, 0, 0, 6, 3, 5, 4, 6]
Output: 2
```
Player 1 stacks three pieces in column 0, and player 2 blocks the fourth. Player 2's move at index 9 fills the bottom row from column 1 to column 4 and wins; the move at index 10 is ignored.
**Example 3**
```text
Input: rows = 6, cols = 7, moves = [3, 3, 3, 3, 2, 4]
Output: 0
```
No player has four pieces in a line.
Overview: Given a board size and the sequence of columns two players drop pieces into, return which player first lines up four pieces horizontally, vertically or diagonally, or 0 if nobody does. It tests grid simulation, gravity placement and careful line counting in all four directions.
Two players play Connect Four on a grid with `rows` rows and `cols` columns. They take turns dropping a piece into a column, and the piece falls to the lowest empty cell of that column. Given the sequence of columns played, return the player who first gets four pieces in a line.
Implement `connect_four_winner(rows, cols, moves)`.
### Rules
- The grid starts empty. Player 1 moves first and the players alternate, so `moves[i]` is played by player 1 when `i` is even and by player 2 when `i` is odd.
- `moves[i]` is a column index from `0` to `cols - 1`. The piece occupies the lowest empty cell of that column.
- A player wins as soon as four of their pieces occupy four consecutive cells along a row, a column or either diagonal. A line longer than four also counts.
- Return `1` or `2` for the first player to win; any moves after the winning move are ignored. Return `0` if nobody has won after all the moves.
The answer is always `0`, `1` or `2`, so no value exceeds 2^31-1.
### Constraints
- `1 <= rows <= 100` and `1 <= cols <= 100`
- `0 <= len(moves) <= rows * cols`
- `0 <= moves[i] <= cols - 1`, and no column receives more than `rows` pieces over the whole list.
### Examples
In the picture, `X` is player 1, `O` is player 2, and the last line is the bottom row of the grid.
**Example 1**
```text
Input: rows = 6, cols = 7, moves = [0, 1, 1, 2, 2, 3, 2, 3, 3, 0, 3]
Output: 1
. . . . . . .
. . . . . . .
. . . X . . .
. . X X . . .
O X X O . . .
X O O O . . .
```
The last move, by player 1, completes the diagonal that rises from the bottom-left corner. Player 2 has three in a row along the bottom but never gets the fourth.
**Example 2**
```text
Input: rows = 6, cols = 7, moves = [0, 1, 0, 2, 0, 0, 6, 3, 5, 4, 6]
Output: 2
```
Player 1 stacks three pieces in column 0, and player 2 blocks the fourth. Player 2's move at index 9 fills the bottom row from column 1 to column 4 and wins; the move at index 10 is ignored.
Constraints
- 1 <= rows <= 100 and 1 <= cols <= 100
- 0 <= len(moves) <= rows * cols
- 0 <= moves[i] <= cols - 1, and no column receives more than rows pieces over the whole list
Examples
Input: (6, 7, [])
Expected Output: 0
Explanation: Empty move list (length 0) on a 6x7 grid: nobody has played, so the result is 0.
Input: (1, 1, [0])
Expected Output: 0
Explanation: Smallest grid, 1x1, with its only possible move (length 1): a single piece cannot form a line, so 0.
Hints
- Keep track of how many pieces each column already holds, so you always know which cell a move lands in.
- Pieces are never removed, so a line of four can only appear at the moment a piece is dropped, and it must include that piece.
- The newest piece need not be at the end of its line: it can fill a gap in the middle, and a line longer than four still counts.