Find the Winner of a Connect Four Game from Its Move Sequence

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

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

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

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

Input: rows = 6, cols = 7, moves = [3, 3, 3, 3, 2, 4]
Output: 0

No player has four pieces in a line.