Candy Crush Grid Matching and Gravity

Problem Overview

You are given an m x n grid of non-negative integers. A positive value represents a candy type, and 0 represents an empty cell. A match is any horizontal or vertical run of at least three adjacent cells with the same positive value.

Part 1: Find Matching Runs

Problem Statement

Return every horizontal and vertical run of length at least 3. This implementation returns all vertical matches first, then all horizontal matches, because several reports mention a direction priority requirement. Within each direction group, scan start cells from the top-left of the board to the bottom-right.

from typing import List, Tuple

Match = Tuple[int, int, str, int]  # row, col, "V" or "H", length

def find_matches(board: List[List[int]]) -> List[Match]:
    pass

Example

board = [
    [1, 2, 2, 2],
    [1, 3, 4, 5],
    [1, 3, 3, 3],
    [6, 7, 8, 9],
]

find_matches(board)
# [
#   (0, 0, "V", 3),
#   (0, 1, "H", 3),
#   (2, 1, "H", 3),
# ]

The first column has three 1s vertically. Row 0 has three 2s horizontally, and row 2 has three 3s horizontally.

Part 2: Crush Matches and Apply Gravity

Problem Statement

Remove every cell that belongs to at least one match, then apply gravity independently in each column. Non-zero values fall downward while preserving their relative order within the column. Empty cells at the top become 0.

from typing import List

def crush_once(board: List[List[int]]) -> List[List[int]]:
    pass

Example

board = [
    [1, 2, 2, 2],
    [1, 3, 4, 5],
    [1, 3, 3, 3],
    [6, 7, 8, 9],
]

crush_once(board)
# [
#   [0, 0, 0, 0],
#   [0, 0, 0, 0],
#   [0, 3, 4, 5],
#   [6, 7, 8, 9],
# ]

The matched 1s, 2s, and 3s are removed. The remaining values in each column fall to the bottom.