Drop a Tetris piece and clear full rows

The piece enters from above the board and falls straight down in the columns
offset .. offset + w - 1. It never moves sideways, so it stops at the first
height where moving one row lower would put a filled cell on an occupied cell
or past the floor. Then we lock it into the board and clear any row that is
now full.

Brute force (say it first). Start the piece fully above the grid
(top = -h) and lower it one row at a time while it still fits. A "fit"
check looks only at the filled cells of the mask; cells above row 0 are open
air. This costs O(H * h * w) and is a good correctness oracle.

Column profiles (optimal). A straight drop can never get past the
highest occupied cell of any column it passes through. So only two numbers
per column matter:

• surface[c]: the first occupied background row in board column
  offset + c (or H if the column is empty).
• lowest[c]: the lowest filled row of the mask in local column c (skip
  columns of the mask that are all zero).

Column c lets the piece's top row go down to surface[c] - 1 - lowest[c].
The piece stops at the minimum over all filled mask columns. Holes under an
overhang in the background do not matter, because the piece cannot reach
them on a straight drop. Holes in the mask do not matter either: only the
lowest filled cell in each column can be the first to touch.

Game over. If at the resting position some filled cell is still above
row 0, the piece does not fit; return None. Note that the resting top
may be negative when the mask's top rows are empty, which is fine.

Lock and clear. Copy the board, set the piece's cells, keep the rows
that are not full, and add that many empty rows on top. Rows above a cleared
row shift down by the number of cleared rows below them, which the
"filter, then pad" step does in one pass.

Invariants: we never mutate the input; every filled cell of the result was
either a background cell or a piece cell; no two piece cells share a board
cell with the background before clearing.

from typing import List, Optional

Grid = List[List[int]]


def fits(background: Grid, block: Grid, top: int, offset: int) -> bool:
    """True if the filled cells, with the block's top-left at (top, offset), hit
    nothing. Rows above the grid (negative) are open air."""
    rows = len(background)
    for r, row in enumerate(block):
        for c, cell in enumerate(row):
            gr = top + r
            if cell and gr >= 0 and (gr >= rows or background[gr][offset + c]):
                return False
    return True


def first_filled_row(block: Grid) -> int:
    return next(r for r, row in enumerate(block) if any(row))


def drop_block_simulate(background: Grid, block: Grid, offset: int) -> Optional[int]:
    """Brute force: start fully above the grid, lower one row at a time.
    Returns the final top row (may be negative if the mask's top rows are empty),
    or None if a filled cell would rest above the grid."""
    top = -len(block)
    while fits(background, block, top + 1, offset):
        top += 1
    return top if top + first_filled_row(block) >= 0 else None


def landing_row(background: Grid, block: Grid, offset: int) -> Optional[int]:
    """Column profiles: the piece stops when some column's lowest filled cell sits
    just above that column's highest occupied background cell. O(H*W + h*w)."""
    rows = len(background)
    top = rows
    for c in range(len(block[0])):
        lowest = max((r for r in range(len(block)) if block[r][c]), default=-1)
        if lowest < 0:
            continue  # empty mask column never collides
        surface = next((r for r in range(rows) if background[r][offset + c]), rows)
        top = min(top, surface - 1 - lowest)
    return top if top + first_filled_row(block) >= 0 else None


def drop_block(background: Grid, block: Grid, offset: int) -> Optional[Grid]:
    """Drop `block` straight down at column `offset`, lock it, clear full rows.
    Returns a new grid, or None if the piece cannot fit inside the grid."""
    if not background or not block or not any(map(any, block)):
        raise ValueError("empty grid or empty block")
    width = len(background[0])
    if offset < 0 or offset + len(block[0]) > width:
        raise ValueError("block does not fit horizontally at this offset")

    top = landing_row(background, block, offset)
    if top is None:
        return None

    grid = [row[:] for row in background]
    for r, row in enumerate(block):
        for c, cell in enumerate(row):
            if cell:
                grid[top + r][offset + c] = 1

    kept = [row for row in grid if not all(row)]
    cleared = len(grid) - len(kept)
    return [[0] * width for _ in range(cleared)] + kept


if __name__ == "__main__":
    board = [
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [1, 0, 0, 0],
        [1, 1, 0, 1],
    ]
    piece = [[1, 1], [0, 1]]
    assert drop_block(board, piece, 1) == [
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [1, 1, 1, 0],
    ]
    assert drop_block([[1, 0], [1, 0]], [[1]], 0) is None
    assert landing_row(board, piece, 1) == drop_block_simulate(board, piece, 1) == 2

Let the board be H x W and the mask h x w.

• landing_row: O(h * w) for the mask's lowest cells plus O(H * w) to find
  the surface of the w columns it covers. Space O(1) beyond the input.
• drop_block: O(H * W) to copy the board and clear rows, which dominates.
  Space O(H * W) for the new board.
• drop_block_simulate (brute force): O((H + h) * h * w).
• If the board keeps a heights array that is updated after each lock, the
  landing row is O(h * w) and the whole drop is O(h * w + cleared * W).

• Board [[0,0,0,0],[0,0,0,0],[1,0,0,0],[1,1,0,1]], piece [[1,1],[0,1]],
  offset 1: the piece rests with its top at row 2, row 3 becomes full and is
  cleared, result [[0,0,0,0],[0,0,0,0],[0,0,0,0],[1,1,1,0]].
• T piece [[1,1,1],[0,1,0]] on [[0,0,0],[0,0,0],[0,0,0],[1,0,1]], offset 0:
  the stem fills the gap, rows 2 and 3 both clear, result is all zeros.
• Empty 2 x 2 board, piece [[1]], offset 1: lands on the floor,
  [[0,0],[0,1]].
• Column already full to the top: [[1,0],[1,0]], piece [[1]], offset 0:
  returns None.
• Overhang: [[0,0],[1,0],[0,0]], piece [[1]], offset 0: the piece stops on
  row 1 and the hole at row 2 stays empty, [[1,0],[1,0],[0,0]].
• Mask with an empty column: [[0,1],[0,0]] on an empty 2 x 2 board,
  offset 0: only column 1 counts, result [[0,0],[0,1]].
• Mask with an empty top row: [[0],[1]] on [[0,0],[0,1]], offset 1:
  resting top is -1 and the piece still fits, result [[0,1],[0,1]].
• Piece taller than the free space: [[1],[1]] on [[0],[1]]: returns None.
• offset + w > W, negative offset, or an all-zero mask: ValueError.
• Randomized: landing_row equals drop_block_simulate on thousands of random
  boards and masks.

• Pick the best offset. Try every offset 0 .. W - w and score each
  result (most rows cleared, then lowest max height, then fewest holes).
  O(W * (h * w + H * W)); keep a heights array to make each trial cheap.
• Rotations. Precompute the up-to-four distinct rotations of the mask
  (rotate with zip(*mask[::-1]), deduplicate) and search rotation x offset.
  Everything else is unchanged.
• A stream of pieces. Keep the board as state in a class with
  drop(piece, offset). Maintain heights[col] and a per-row fill count so
  you find the landing row in O(h * w) and detect full rows without
  rescanning. Report score and game over.
• Sliding after landing / soft drop with moves. If the piece can move
  sideways while falling, the reachable resting positions form a graph over
  (row, offset, rotation); run BFS from the spawn state using fits as the
  edge test. The column-profile shortcut no longer applies because the piece
  can slide under overhangs.
• Very wide boards. Store each row as an integer bitmask. A fit test is
  row_bits & (piece_bits << offset) == 0, and a full row is
  row_bits == (1 << W) - 1.

Mid-level (L4)

• Clarifies where the piece starts, what happens at the floor, whether rows
  clear, and what to return when the piece does not fit.
• Writes a correct row-by-row simulation that ignores the mask's zero cells.
• Clears full rows correctly, including several at once, without mutating the input.

Senior (L5)

• Moves from simulation to the column-profile landing rule and explains why
  holes under overhangs and holes in the mask do not change the answer.
• Handles edge cases: empty mask rows or columns, negative resting top,
  bad offsets, pieces taller than the space left.
• Tests the fast path against the simulation; extends cleanly to best offset
  and rotations.

Staff (L6+)

• Designs the multi-piece version as a stateful class with incremental
  heights and row counts, and states the cost of each operation.
• Says clearly when the profile shortcut breaks (sideways moves, rotation in
  flight) and switches to BFS over piece states.
• Talks about representation trade-offs (bitmask rows, immutable vs in-place
  boards) and how to make the AI placement search fast.