Implement Connect Four game

Question

Design and implement the Connect Four game board, player moves, and winner-detection logic. Discuss time/space complexity and possible follow-ups such as AI opponent or scalable multiplayer service.

Implement Connect Four Game

Implement the core logic of a standard Connect Four game. The board has 6 rows and 7 columns. Players alternate turns, with Red ('R') moving first and Yellow ('Y') moving second. Each move is a column index, and the piece falls to the lowest available cell in that column.

Process the moves in order and stop immediately if a player wins. A player wins if their newly placed piece creates 4 consecutive pieces horizontally, vertically, or diagonally.

Return:

• 'R' if Red wins
• 'Y' if Yellow wins
• 'Draw' if the board becomes full with no winner
• 'Pending' if all moves are processed and no winner exists but the board is not full
• 'Invalid' if a move uses a column outside 0 to 6, or tries to place a piece into a full column before the game has ended

Constraints

• The board size is fixed at 6 rows by 7 columns.
• 0 <= len(moves) <= 100
• A valid column index is an integer from 0 to 6.

Examples

Example 1

Input: ([],)
Output: 'Pending'

Explanation: No moves have been played, so nobody has won and the board is not full.

Example 2

Input: ([3, 3, 2, 2, 1, 1, 0],)
Output: 'R'

Explanation: Red forms a horizontal line on the bottom row across columns 0, 1, 2, and 3.

Hints

1. Keep track of the next open row in each column so you can place a piece in O(1) time.
2. After placing a piece, only check lines that pass through that new piece: horizontal, vertical, and the two diagonals.