Implement Connect Four with bottom push-up

Implement a Connect Four variant with bottom push-up.

In standard Connect Four a dropped disc falls to the lowest empty cell of a column. In this variant the mechanic is different: when a player inserts a disc into a column, the disc is placed in the bottom cell of that column and pushes every existing disc in that column up by one row. If the column is already full, the disc currently in the top row is pushed off the board and ejected (removed permanently).

Design the board representation and the supporting APIs, then provide code for the core operations. Your design must satisfy the four parts below. For each part, specify the time and space complexity, the data structures used, and how you handle the relevant edge cases.

Constraints & Assumptions

• The board has $R$ rows and $C$ columns, configurable, with a default of $6 \times 7$ (6 rows, 7 columns).
• Two players alternate turns; a disc belongs to the player who dropped it.
• A win is four of one player's discs in a row — horizontally, vertically, or diagonally (either diagonal).
• A win must be detected after each move.
• Columns are indexed $0 \ldots C-1$. Assume the caller may pass an out-of-range column or play out of turn; both must be handled, not assumed away.

Clarifying Questions to Ask

• After the upward push (and a possible ejection), is the win check still "four in a row in any of the three directions," and is it evaluated immediately after every move?
• When a full column ejects its top disc, is that disc gone for good, or must it be restorable on undo?
• How many players, and must drop validate whose turn it is, or does the engine auto-assign the player?
• What exactly counts as a draw under this push mechanic, given that a "full" board can still accept moves (they just eject)? Is there a move cap?
• Do undo/redo need to follow standard editor semantics (a new move after an undo clears the redo history)?
• Are $R$ and $C$ guaranteed large enough for a win to be geometrically possible, or should init handle a board too small to ever win?

---

Part 1 — Initialization

Provide an API to initialize the board with $R$ rows and $C$ columns (default $6 \times 7$). Describe your board representation and any per-column or global bookkeeping you maintain.

Hint: Representation

Pick a fixed convention for which row index is the bottom (insertion) row vs. the top (ejection) row, and state it. One of the two choices makes "insert at bottom, shift up" read as a single consistent index direction — decide which and commit to it, because every later operation depends on it.

Hint: Bookkeeping

What auxiliary data would let you answer "is this column full (so a drop will eject)?" and "is the whole board full (for the draw test)?" without re-scanning the grid each time? Think about what you'd have to maintain on every drop to keep those answers cheap.

What This Part Should Cover

• A grid representation with an explicitly stated row-orientation convention (which index is the bottom/insertion row vs. the top/ejection row).
• Auxiliary bookkeeping (e.g. a per-column height and a global filled-cell count) chosen so the full/eject test and the draw test are $O(1)$ rather than grid re-scans.
• A note on whether init should validate or warn when the board is too small for a four-in-a-row to be geometrically possible.

Part 2 — Drop a disc

Implement drop(player, column): place the player's disc in the bottom cell of column, push existing discs up by one, and eject the top disc if the column was already full. Validate the column index and the player's turn. State the complexity.

Hint: Two cases

Branch on whether the column is already full. If full, what do you need to capture before you start shifting, so the move is reversible later? If not full, you only disturb the occupied part of the column. In both cases the new disc lands in the bottom slot.

Hint: Cost

Ask yourself how much of the board a single drop can touch — is it bounded by a row, a column, or the whole grid? State the shift's time and extra-space cost in terms of $R$ and $C$, and keep it separate from the cost of the win check that follows.

What This Part Should Cover

• Correct shift-up semantics with both branches handled: the non-full case (shift only the occupied prefix, increment height) and the full-column ejection case (capture the top disc, shift, height unchanged).
• Validation that the column index is in range and that it is the given player's turn, with no state mutation on a rejected move.
• A justified shift cost (bounded by one column) stated separately from the win check that follows.

Part 3 — Win detection

After each move, detect a win: four in a row horizontally, vertically, or diagonally. Explain why your approach is correct under the push mechanic, and give its complexity.

Hint: The trap

Compare this to standard Connect Four, where you can inspect only the lines through the single just-placed cell. Here the insert shifts the whole column — so ask yourself: which discs changed row this move, and does the "look only around the placed cell" shortcut still see all of them?

Hint: What's actually safe

Reason about exactly which cells are guaranteed unchanged by a drop, and which are not. Any approach you propose must be correct for every cell that could have moved — let that requirement decide how much of the board your check has to cover, then state its complexity in terms of $R$ and $C$.

Hint: Scaling further

If pushed on a much larger board, think about which lines a drop in column $c$ can possibly change — they all have to pass through that column. Can you turn "must pass through column $c$" into a bound on how few columns the recheck has to revisit? Offer this as a follow-up, not the default.

What This Part Should Cover

• Explicit reasoning about why the standard "only check lines through the placed cell" shortcut is wrong here — the upward shift moves discs the shortcut never inspects.
• A correct detection strategy whose coverage spans every cell a drop can move (the bulletproof choice is a full-board scan), with its time/space complexity stated in terms of $R$ and $C$.
• Recognition that the column-windowed recheck (columns $[c-3, c+3]$) is an optimization to offer for large boards, not the default.

Part 4 — Undo and Redo

Support undo and redo of moves. An undo must exactly reverse a drop — including restoring an ejected disc to the top — and redo must replay it identically. State the complexity and the redo-invalidation rule.

Hint: Pattern

Treat each move as a command that stores whatever is needed to invert it. Work out the minimal set of facts about a drop you'd have to remember to undo it exactly — and don't forget the case where a disc left the board. Two stacks (undo / redo) of these records give you the history.

Hint: The hard part

The reverse of a drop is not uniform: a drop on a full column and a drop on a non-full column vacate and restore different things. Walk both branches — what gets shifted, what gets restored or cleared, and what bookkeeping (including whose turn it is) has to be rolled back.

Hint: Editor semantics

Making a new move after an undo must clear the redo stack, so a divergent future can't be replayed onto the current board.

What This Part Should Cover

• A command/record per move capturing the minimal facts to invert it — at least the column, the player, whether the column was full, and the ejected disc (if any).
• Both inverse branches handled correctly: restoring an ejected disc to the top for a full-column drop vs. clearing the vacated top slot and decrementing height/total for a non-full drop, plus rolling back whose turn it is.
• An exact undo→redo round-trip (the board, height, count, and turn return identically) and the redo-invalidation rule (a fresh move clears the redo stack).

---

What a Strong Answer Covers

These dimensions span all four parts:

• Stated time and space complexity per operation, with the data structures backing each, and the honest tradeoff of keeping the win check a full $O(RC)$ scan on the tiny default board.
• Coverage of every named edge case across the parts: ejected discs, invalid columns, alternating turns, and draw detection (including that a "full" board still accepts ejecting moves, so the terminal draw must be defined carefully).
• A short test plan exercising the tricky cases — most importantly a win created by the upward shift, and a full-column eject whose undo restores the ejected disc exactly.

Follow-up Questions

• How does win detection change if the board is much larger (say $100 \times 100$)? What's the first thing you'd optimize, and what's the worst-case cost of your optimized recheck?
• Can a single push simultaneously create one win and destroy another? How does your detection (and your "stop on win" logic) behave, and which player is credited?
• How would you extend the engine to $k$ players or to a "connect $N$" generalization without rewriting the win scan?
• What's the precise terminal condition for a draw here, given a full board still accepts ejecting moves — and how would a move cap change it?

Part 1: Initialize a Bottom Push-Up Connect Four Board

Create the initial state for a Connect Four variant where discs are inserted at the bottom of a column and push existing discs upward. Use row index 0 as the bottom/insertion row, and row index R-1 as the top/ejection row. For this standalone problem, return a textual snapshot of the initialized board and bookkeeping. Passing rows=0 and cols=0 requests the default 6 x 7 board. If dimensions are invalid, return ['INVALID_DIMENSIONS']. Also report whether a connect-four line is geometrically possible on the board.

Constraints

• 0 <= rows, cols <= 200
• rows=0 and cols=0 means use the default 6 x 7 board
• After default handling, rows and cols must both be positive
• Internal row orientation must treat row 0 as the bottom insertion row

Examples

Example 1

Input: (0, 0)
Output: ['rows=6', 'cols=7', 'orientation=bottom_index_0_top_index_R-1', 'heights=0,0,0,0,0,0,0', 'filled=0', 'can_connect_four=true', '.......', '.......', '.......', '.......', '.......', '.......']

Explanation: The default 6 x 7 empty board is created.

Example 2

Input: (3, 3)
Output: ['rows=3', 'cols=3', 'orientation=bottom_index_0_top_index_R-1', 'heights=0,0,0', 'filled=0', 'can_connect_four=false', '...', '...', '...']

Explanation: A 3 x 3 board cannot contain four cells in any direction.

Hints

1. Pick one row-index convention and use it consistently. Row 0 as the bottom makes bottom insertion easy to reason about.
2. Store a height per column and a global filled count so later operations can answer fullness questions without scanning the whole grid.

Part 2: Drop a Disc with Bottom Push-Up Semantics

Simulate disc drops in the bottom push-up Connect Four variant. A valid drop inserts the player's disc into the bottom cell of the chosen column and shifts existing discs in that column upward by one row. If the column is full, the old top disc is ejected permanently. Player X always moves first, and valid moves must alternate X, O, X, O. Rejected moves must not mutate the board or advance the turn.

Constraints

• 1 <= rows, cols <= 200
• 0 <= len(moves) <= 1000
• Players are represented by 'X' and 'O'
• A rejected move performs no mutation and does not advance the turn
• This part does not perform win detection; it only simulates drops

Examples

Example 1

Input: (4, 3, ['X 1', 'O 1', 'X 1'])
Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=.', 'TURN:O', 'HEIGHTS:0,3,0', 'FILLED:3', '...', '.X.', '.O.', '.X.']

Explanation: All three discs are inserted at the bottom of column 1, pushing previous discs upward.

Example 2

Input: (2, 1, ['X 0', 'O 0', 'X 0'])
Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=X', 'TURN:O', 'HEIGHTS:2', 'FILLED:2', 'O', 'X']

Explanation: The third drop is into a full column and ejects the old top X.

Hints

1. Branch on whether heights[column] == rows. In the full case, save the top disc before shifting.
2. A single drop only touches one column, so the shift cost is proportional to R, not R*C.

Part 3: Detect Wins After Bottom Push-Up Drops

Simulate bottom push-up drops and report winners after each valid move. A win is four equal discs horizontally, vertically, or diagonally. Unlike standard Connect Four, checking only around the newly inserted bottom cell is not sufficient because every disc in the affected column may move upward. For this problem, use a full-board scan after each valid move.

Constraints

• 1 <= rows, cols <= 100
• 0 <= len(moves) <= 1000
• Players are 'X' and 'O'
• A rejected move performs no mutation and does not advance the turn
• A board with both rows < 4 and cols < 4 can never contain a connect-four line

Examples

Example 1

Input: (4, 5, ['X 0', 'O 4', 'X 1', 'O 4', 'X 2', 'O 4', 'X 3'])
Output: ['OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:X']

Explanation: X completes a horizontal bottom-row connect four.

Example 2

Input: (4, 6, ['X 1', 'O 4', 'X 1', 'O 5', 'X 2', 'O 2', 'X 3', 'O 4', 'X 3', 'O 5', 'X 0', 'O 0'])
Output: ['OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:-', 'OK:X']

Explanation: The final O drop in column 0 pushes an X upward, creating an X horizontal win that is not through the newly placed O.

Hints

1. The newly inserted disc is not the only changed cell; all occupied cells in the chosen column may shift upward.
2. A full-board scan is simple and correct for the default board size. Larger boards can optimize by rechecking lines that pass through the changed column.

Part 4: Undo and Redo Bottom Push-Up Drops

Support drop, undo, and redo operations for the bottom push-up Connect Four variant. Each successful drop must be recorded as a command containing enough information to invert it exactly, including whether the column was full and which disc, if any, was ejected. Undo reverses the most recent successful drop. Redo reapplies the most recently undone drop. A new successful drop after an undo clears the redo history.

Constraints

• 1 <= rows, cols <= 100
• 0 <= len(operations) <= 1000
• Players are 'X' and 'O', with X moving first
• Rejected drops do not mutate state, advance turn, or clear redo history
• A new successful drop after one or more undos clears the redo stack

Examples

Example 1

Input: (3, 2, ['drop X 0', 'drop O 1', 'undo', 'redo'])
Output: ['OK:ejected=.', 'OK:ejected=.', 'UNDO_OK', 'REDO_OK:ejected=.', 'TURN:X', 'HEIGHTS:1,1', 'FILLED:2', '..', '..', 'XO']

Explanation: Undo removes O from column 1; redo restores the same drop.

Example 2

Input: (2, 1, ['drop X 0', 'drop O 0', 'drop X 0', 'undo'])
Output: ['OK:ejected=.', 'OK:ejected=.', 'OK:ejected=X', 'UNDO_OK', 'TURN:X', 'HEIGHTS:2', 'FILLED:2', 'X', 'O']

Explanation: Undo of a full-column drop restores the ejected X to the top.

Hints

1. Use two stacks: one for executed commands and one for undone commands.
2. Undo has two branches: a full-column drop restores the ejected top disc, while a non-full drop clears the vacated top occupied slot and decreases the height.

Solution

Connect Four — Bottom-Push Variant

1. Restate the rules and pin down assumptions

The twist versus standard Connect Four is the insertion mechanic:

• A disc is inserted at the bottom cell of a column, not the lowest empty cell.
• Every existing disc in that column is pushed up by one row.
• If the column is already full, the disc currently in the top row is pushed off the board and ejected (removed permanently).

Decisions I confirm with the interviewer up front, because they materially change the design:

• Win condition: still four-in-a-row horizontally, vertically, or either diagonal — checked after every move.
• A single move can change the whole column. Because all discs shift up, the win check cannot be the cheap "look only around the cell I just placed." Cells far from the insertion point change row, so previously non-winning lines can become winning and vice versa (detail in §4).
• Turn order: players strictly alternate; drop takes an explicit player, and I validate it matches whose turn it is. I support 2 players ("X", "O") but keep the engine generic over the player list.
• Ejected disc fate: removed from the board, but for undo I remember what was ejected so I can restore it.
• Draw: every cell filled and no winner — with the subtlety that, under bottom-push, a "full" board still accepts moves (they just eject the top), so the terminal draw must be defined carefully (§6).
• Default size: $R = 6$ rows, $C = 7$ columns, both configurable. A win needs $R \geq 4$ or $C \geq 4$ to be geometrically possible.

---

2. Part 1 — Board representation and initialization

I use a 2D grid plus a small amount of bookkeeping.

Convention: row = 0 is the bottom row (the insertion row), row = R-1 is the top (the ejection row). This makes "insert at bottom, shift up" read naturally as "shift index up," and every later operation depends on it.

EMPTY = None
# grid[r][c]: r in [0, R-1] bottom..top, c in [0, C-1]
grid   = [[EMPTY] * C for _ in range(R)]
height = [0] * C   # number of discs currently in column c (0..R)
total  = 0         # filled cells, for an O(1) draw test

Why the auxiliary bookkeeping?

• height[c] gives an $O(1)$ check for whether a column is full (height[c] == R) — i.e. whether this drop will eject — instead of scanning the column.
• total gives an $O(1)$ draw check (total == R*C) instead of scanning the whole grid.

Data structures:

Structure	Type	Purpose	Space
grid	$R \times C$ array of player ids / None	the board	$O(RC)$
height[]	length-$C$ int array	discs per column, full/eject test	$O(C)$
total	int	filled-cell count for draw test	$O(1)$
undo_stack	list of Move records	undo history	$O(M)$ for $M$ moves
redo_stack	list of Move records	redo history	$O(M)$

A column behaves like a bottom-insert, top-eject fixed-capacity buffer. I keep it as a slice of one contiguous 2D grid (rather than C separate column lists) because the win scanner has to read across columns for horizontal and diagonal lines; a row-major grid makes that direct.

init validation: reject R < 1 or C < 1; optionally warn if R < 4 and C < 4, since then no four-in-a-row is ever possible and the game can only draw.

Complexity: init is $O(RC)$ time and $O(RC)$ space (allocating the grid).

---

3. Part 2 — The drop operation

Insert at the bottom and shift up, ejecting the top when the column is full. The two cases differ in what range shifts and whether height changes, so I branch on "was the column full?" and, for the full case, capture the ejected disc before shifting so the move is reversible.

drop(player, c):
    if game already won:        reject
    if c not in [0, C-1]:       raise / return error   # no mutation
    if player is not whose turn: raise / return error   # no mutation
    ejected = None
    if height[c] == R:              # column full -> top disc ejects
        ejected = grid[R-1][c]      # capture BEFORE shifting
        for r in range(R-1, 0, -1): # shift up; top falls off, bottom opens
            grid[r][c] = grid[r-1][c]
        # height stays R (one in, one out); total unchanged
    else:
        for r in range(height[c], 0, -1):  # shift only the occupied prefix
            grid[r][c] = grid[r-1][c]
        height[c] += 1
        total += 1
    grid[0][c] = player             # new disc lands at the bottom
    push Move(player, c, ejected, was_full) onto undo_stack
    clear redo_stack                # a fresh move invalidates redo
    advance turn
    winner = has_win()              # see §4
    return winner

Complexity of drop: the column shift is $O(R)$ time and $O(1)$ extra space, plus the $O(RC)$ win scan that follows. Net $O(RC)$ — but I keep the two costs separate because the shift itself is only $O(R)$.

A column could instead be a Python list with col.insert(0, player) + (if full) col.pop() — also $O(R)$. A deque with appendleft + pop is amortized $O(1)$ for the buffer, but then the win scanner has to reconstruct row-major access across columns, and the win check ($O(RC)$) dominates regardless. The explicit in-place shift avoids reallocation and keeps the grid directly scannable.

---

4. Part 3 — Win detection

The core subtlety. In standard Connect Four you may check only the four directions through the just-placed cell, because nothing else moved. Here the entire inserted column shifts up one row, so:

• Every disc in that column changed row — breaking or forming vertical runs within the column, and any horizontal or diagonal run passing through any of those cells.
• No cell outside the inserted column moved.

So the standard "only around the placed cell" shortcut is wrong here: it would never inspect the shifted discs above the insertion point. The correct, bulletproof choice is a full-board scan after each move — $O(RC)$, which for $6 \times 7$ is trivially fast.

DIRS = [(0, 1), (1, 0), (1, 1), (1, -1)]  # →, ↑, ↗, ↖ (the other half is the reverse)

def has_win():
    for r in range(R):
        for c in range(C):
            p = grid[r][c]
            if p is EMPTY:
                continue
            for dr, dc in DIRS:
                cnt, rr, cc = 1, r + dr, c + dc
                while 0 <= rr < R and 0 <= cc < C and grid[rr][cc] == p:
                    cnt += 1
                    if cnt == 4:
                        return p          # winner
                    rr += dr; cc += dc
    return None

• Time: $O(RC)$. Each of the $RC$ cells launches a scan in 4 fixed directions; each inner while stops as soon as the run breaks or cnt reaches 4, so it walks at most 3 further cells. That is $O(1)$ work per (cell, direction): $O(RC \cdot 4 \cdot 3) = O(RC)$. For $6 \times 7$ the worst case is $\le 6 \cdot 7 \cdot 4 \cdot 3 = 504$ reads, far fewer in practice.
• Space: $O(1)$ beyond the board.

Optimization (a follow-up, not the default). Since only column c changed, you only need lines that intersect column c. A horizontal/diagonal four spans at most columns $[c-3, c+3]$, across any row. That bounds the recheck to $O(R \cdot \min(C, 7)) = O(R)$ for a fixed window — worthwhile on a large board. I'd implement the full scan first for correctness, then offer this. I would not attempt the standard "only around the placed cell" trick, which is incorrect here.

Whose win: I run has_win() after the move and report the returned player. Only one player just moved, and I maintain the invariant that the board had no winner before the move (the game stops on a win), so the mover is the winner.

---

5. Part 4 — Undo and Redo

I use the command pattern: each move stores everything needed to invert it. The non-trivial part is the ejected disc — undo must restore it to the top.

class Move:
    __slots__ = ("player", "col", "ejected", "was_full")
    # player:   who dropped
    # col:      column index
    # ejected:  the disc removed off the top (or None)
    # was_full: whether the column was full at drop time

These four facts are the minimal record: col/player identify the move, was_full selects the inverse branch, and ejected is the one piece that left the board.

Undo reverses the shift. The two cases shift back over different ranges, so I branch on was_full rather than fold them into one loop:

undo():
    if undo_stack empty: raise NothingToUndo
    m = undo_stack.pop(); c = m.col
    if m.was_full:
        # shift the whole column down by one, then put the ejected disc
        # back on top; height stays R
        for r in range(0, R-1):
            grid[r][c] = grid[r+1][c]
        grid[R-1][c] = m.ejected
    else:
        # shift the occupied prefix down by one, clear the vacated top slot
        for r in range(0, height[c]-1):
            grid[r][c] = grid[r+1][c]
        grid[height[c]-1][c] = EMPTY
        height[c] -= 1
        total -= 1
    retreat turn                      # it becomes the mover's turn again
    winner = None                     # reversing a move can only un-win
    redo_stack.append(m)

Redo replays the move. Because the inversion is exact, replaying reproduces the identical board, including re-ejecting the same disc:

redo():
    if redo_stack empty: raise NothingToRedo
    m = redo_stack.pop()
    apply_drop(m.player, m.col)       # board mutation ONLY; no stack changes
    undo_stack.append(m)              # redo re-pushes the same record
    advance turn
    winner = has_win()

Here apply_drop is the bare board mutation shared by drop and redo; it does not push onto undo_stack or clear redo_stack. drop and redo each own the stacks explicitly, which is why redo re-pushes the same Move object rather than fabricating a new one.

Redo invalidation rule: making a new move after an undo clears redo_stack (standard editor semantics), so a divergent future can't be replayed onto the current board.

Complexity: undo and redo are each $O(R)$ (one column shift), plus $O(RC)$ for redo's win check. Each Move is $O(1)$; history storage is $O(M)$ for $M$ moves.

---

6. Cross-cutting: edge cases (every one the prompt names)

Edge case	Handling
Invalid column	drop validates 0 <= c < C; otherwise raise ValueError / return an error result. Out-of-range never mutates state.
Ejected discs	Captured in Move.ejected so undo restores them; on a full column height stays $R$ and total is unchanged (one in, one out).
Alternating turns	drop(player) checks player == current_player; on success flip the turn; undo restores the previous turn; redo re-flips. A move by the wrong player is rejected with no mutation.
Draw detection	A true terminal draw is subtle: the board can be full yet still accept moves (they eject). I define a draw state as board full AND no winner (total == R*C, an $O(1)$ test) and surface it as a state rather than a forced end — the rules/UI decide whether to keep playing. If total moves are capped, draw = "no winner after the last allowed move."
Win short-circuits	After a winning drop, set the winner/game_over flag and reject further drops; undo is still allowed and clears the flag if it reverses the winning move.
Board too small for a win	If R < 4 and C < 4, no four-in-a-row is geometrically possible; validate/warn at init.
Eject creating/breaking a win	Handled automatically: ejection happens before the new bottom disc is placed, and the full-board scan runs on the resulting board, so a line formed (or destroyed) by the shift is detected correctly.

---

7. Full reference implementation

from typing import Optional, List, Tuple

EMPTY = None

class Move:
    __slots__ = ("player", "col", "ejected", "was_full")
    def __init__(self, player, col, ejected, was_full):
        self.player = player
        self.col = col
        self.ejected = ejected
        self.was_full = was_full

class ConnectFourBottomPush:
    DIRS = [(0, 1), (1, 0), (1, 1), (1, -1)]

    def __init__(self, rows: int = 6, cols: int = 7, players=("X", "O")):
        if rows < 1 or cols < 1:
            raise ValueError("rows and cols must be >= 1")
        self.R, self.C = rows, cols
        self.players = players
        self.grid = [[EMPTY] * cols for _ in range(rows)]  # row 0 = bottom
        self.height = [0] * cols
        self.total = 0
        self.turn_idx = 0                  # index into players
        self.undo_stack: List[Move] = []
        self.redo_stack: List[Move] = []
        self.winner = None

    # ---- helpers -------------------------------------------------------
    @property
    def current_player(self):
        return self.players[self.turn_idx]

    def _advance_turn(self):
        self.turn_idx = (self.turn_idx + 1) % len(self.players)

    def _retreat_turn(self):
        self.turn_idx = (self.turn_idx - 1) % len(self.players)

    def _apply_drop(self, player, c) -> Tuple[Optional[str], bool]:
        """Mutate the board for one drop. Does NOT touch undo/redo stacks
        or the turn — the caller owns those. Returns (ejected, was_full):
        the disc pushed off the top (or None), and whether the column was
        already full at drop time."""
        full = self.height[c] == self.R
        ejected = None
        if full:
            ejected = self.grid[self.R - 1][c]
            for r in range(self.R - 1, 0, -1):
                self.grid[r][c] = self.grid[r - 1][c]
        else:
            for r in range(self.height[c], 0, -1):
                self.grid[r][c] = self.grid[r - 1][c]
            self.height[c] += 1
            self.total += 1
        self.grid[0][c] = player
        return ejected, full

    # ---- public API ----------------------------------------------------
    def drop(self, player, c: int) -> Optional[str]:
        if self.winner is not None:
            raise RuntimeError("game already won")
        if not (0 <= c < self.C):
            raise ValueError(f"column {c} out of range [0,{self.C-1}]")
        if player != self.current_player:
            raise ValueError(f"not {player}'s turn (expected {self.current_player})")

        ejected, full = self._apply_drop(player, c)
        self.undo_stack.append(Move(player, c, ejected, full))
        self.redo_stack.clear()           # new move invalidates redo
        self._advance_turn()
        self.winner = self.has_win()      # O(R*C)
        return self.winner

    def has_win(self) -> Optional[str]:
        R, C, g = self.R, self.C, self.grid
        for r in range(R):
            for c in range(C):
                p = g[r][c]
                if p is EMPTY:
                    continue
                for dr, dc in self.DIRS:
                    cnt, rr, cc = 1, r + dr, c + dc
                    while 0 <= rr < R and 0 <= cc < C and g[rr][cc] == p:
                        cnt += 1
                        if cnt == 4:
                            return p
                        rr += dr; cc += dc
        return None

    def is_draw(self) -> bool:
        return self.winner is None and self.total == self.R * self.C

    def undo(self):
        if not self.undo_stack:
            raise RuntimeError("nothing to undo")
        m = self.undo_stack.pop()
        c = m.col
        if m.was_full:
            # shift down by one, then restore the ejected disc on top
            for r in range(0, self.R - 1):
                self.grid[r][c] = self.grid[r + 1][c]
            self.grid[self.R - 1][c] = m.ejected
        else:
            for r in range(0, self.height[c] - 1):
                self.grid[r][c] = self.grid[r + 1][c]
            self.grid[self.height[c] - 1][c] = EMPTY
            self.height[c] -= 1
            self.total -= 1
        self._retreat_turn()
        self.winner = None                # reversing a move can only un-win
        self.redo_stack.append(m)

    def redo(self):
        if not self.redo_stack:
            raise RuntimeError("nothing to redo")
        m = self.redo_stack.pop()
        self._apply_drop(m.player, m.col)  # board mutation only
        self.undo_stack.append(m)          # redo re-pushes the same record
        self._advance_turn()
        self.winner = self.has_win()

    def render(self) -> str:
        # print top row first for human readability
        return "\n".join(
            " ".join(cell if cell else "." for cell in self.grid[r])
            for r in range(self.R - 1, -1, -1)
        )

---

8. Complexity summary

Operation	Time	Space (extra)
init(R, C)	$O(RC)$	$O(RC)$
drop (incl. win check)	$O(R)$ shift $+\ O(RC)$ scan $= O(RC)$	$O(1)$ per move record
has_win	$O(RC)$	$O(1)$
is_draw	$O(1)$	$O(1)$
undo	$O(R)$	$O(1)$ amortized
redo	$O(R)$ shift $+\ O(RC)$ win check	$O(1)$ amortized
History storage	—	$O(M)$ for $M$ moves

For the default $6 \times 7$ board these are all microsecond-scale. The honest engineering tradeoff: keep the win check a full $O(RC)$ scan for correctness and simplicity (the board is tiny), and only switch to the column-windowed $O(R)$ recheck if a much larger board is in scope.

---

9. Testing checklist I'd state aloud

• Vertical, horizontal, and both diagonal wins — including a win created by the upward shift (stack three of a colour, then a bottom insert lifts them into a column-of-four).
• A win destroyed by a later shift in the same column (then re-formed) — confirms the full scan rather than an incremental hack.
• Full-column eject: drop $R+1$ discs in one column, verify the first is ejected and undo restores it exactly, leaving the board identical to its pre-drop state (grid and height).
• Undo→redo round-trip equals identity on the grid, height, total, and turn.
• A new move after undo clears the redo stack.
• Invalid-column and wrong-player drops raise and do not mutate state.
• Draw on a fully-filled board with no four-in-a-row.

---

Answers to the follow-up questions

• Much larger board ($100 \times 100$). The first thing I'd optimize is the win check: replace the full $O(RC)$ scan with the column-windowed recheck. Only column c changed, and any four-in-a-row touching it lives in columns $[c-3, c+3]$ across any of the $R$ rows. That makes the recheck $O(R \cdot \min(C, 7)) = O(R)$ worst case (a fixed 7-column window), down from $O(RC)$. The drop's shift is still $O(R)$, so a move becomes $O(R)$ overall.
• One push creating and destroying wins simultaneously. Yes — the shift can lift one player's three into a four while pulling another player's four apart. But I maintain the invariant that the board had no winner before the move (the game halts on a win), so at most a new win can appear, and only the mover's discs were added. A win the opponent might "form" via the shift is irrelevant because the game would already have ended when it was four; the only credited winner is the player who just dropped. If the rules instead allowed play to continue past a win, I'd scan and, by convention, credit the mover (or report all detected lines and let the caller decide).
• $k$ players or connect-$N$. Neither requires rewriting the win scan. For $k$ players, generalize the player list and the turn modulo (already done via players and turn_idx % len(players)); the scan compares disc identities, so it is player-count agnostic. For connect-$N$, parameterize the target run length and compare cnt == N instead of 4; DIRS and the scan structure are unchanged.
• Precise draw condition. Because a full board still accepts ejecting moves, "board full" alone is not terminal. Without a move cap there is no forced draw — play can continue indefinitely, so a draw is at best a state (total == R*C and no winner), reported for the caller to act on, and at worst the game is non-terminating. With a move cap $K$, the clean terminal rule is: draw iff no player has four-in-a-row after $K$ moves (or after the agreed-upon stalemate detection, e.g. a repeated board position).