Match-3 Grid: Find Horizontal and Vertical Runs, Then Clear and Drop Cells

You are given an m × n grid of positive integers representing a Match-3 game board. A match is a run of 3 or more equal values side by side in one row (a horizontal match) or in one column (a vertical match).

Do two things:

1. Find the matches. Report every match as its value and its length.
2. Clear and drop. Set every cell that belongs to any match to 0. Then, in each column, let the non-zero values fall to the bottom, keeping their original top-to-bottom order, so that all the zeros end up at the top of the column.

Return the list of matches and the resulting grid.

Function Signature

def match_three(grid: list[list[int]]) -> tuple[list[list[int]], list[list[int]]]:

Return a pair (matches, result). Each element of matches is a two-element list [value, length]. result is the grid after clearing and dropping, as a list of m rows of n integers, top row first.

Rules

• A run is a maximal sequence of equal values in consecutive cells of one row or one column. A run is a match when its length is at least 3, and it counts once at its full length: four 7s side by side are the single match [7, 4], not two matches of length 3.
• Two runs of the same value that are separated by a different value are separate matches.
• Order of matches: first all horizontal matches, scanning rows top to bottom and each row left to right; then all vertical matches, scanning columns left to right and each column top to bottom. Each match takes its place from the first cell of its run in this scan.
• A cell can belong to both a horizontal and a vertical match. Report both matches; the cell is cleared like any other matched cell.
• Matches are found once, in the input grid. Clear and drop exactly once, and do not look for new matches in the dropped grid.
• If there are no matches, matches is empty and result equals the input grid.

Constraints

• 1 <= m, n <= 100, and every row has exactly n values
• 1 <= grid[i][j] <= 10^9

Examples

Example 1

Input: grid = [[1, 2, 3, 4], [7, 7, 7, 7], [5, 2, 7, 1], [6, 2, 7, 3]]
Output: ([[7, 4], [7, 3]], [[0, 0, 0, 0], [1, 2, 0, 4], [5, 2, 0, 1], [6, 2, 3, 3]])

Rows and columns are numbered from 0. Row 1 is four 7s, a horizontal match of length 4. Column 2 holds 7, 7, 7 in rows 1 to 3, a vertical match of length 3. Column 1 is 2, 7, 2, 2: the 2s are not three in a row, so it has no match. Clearing gives [[1, 2, 3, 4], [0, 0, 0, 0], [5, 2, 0, 1], [6, 2, 0, 3]], and dropping moves each column's non-zero values to the bottom: for example, column 0 becomes 0, 1, 5, 6 and column 2 becomes 0, 0, 0, 3.

Example 2

Input: grid = [[2, 3, 4], [1, 1, 1], [5, 1, 6], [7, 1, 8]]
Output: ([[1, 3], [1, 3]], [[0, 0, 0], [2, 0, 4], [5, 0, 6], [7, 3, 8]])

Row 1 is a horizontal match of three 1s, and column 1 has a vertical match of three 1s in rows 1 to 3. Cell (1, 1) belongs to both, so both matches are reported. After clearing, the 3 at the top of column 1 falls to the bottom row.

Example 3

Input: grid = [[3, 3, 3, 4, 3, 3, 3]]
Output: ([[3, 3], [3, 3]], [[0, 0, 0, 4, 0, 0, 0]])

The 4 separates two runs of three 3s, so they are two matches, listed left to right. Every column has a single cell, so nothing falls.