39. Find a Wake-Word Pattern in a Feature Grid

Problem

A streaming audio pipeline quantizes incoming audio into a 2D grid of integer feature codes — rows are consecutive time frames, columns are feature-bank channels. A wake-word detector holds a small template grid of feature codes for the target phrase.

Find the top-left (row, col) position where the template appears as an exact, contiguous submatrix of the streamed grid, scanning in row-major order so the earliest occurrence wins. Return None if the template never appears.

Source: src/39_wake_word_grid_search.py

def find_wake_word_pattern(grid: list[list[int]], pattern: list[list[int]]) -> tuple[int, int] | None:
    ...

Examples:
>>> grid = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]]
>>> find_wake_word_pattern(grid, [[6, 7], [1, 2]])
(1, 1)

>>> find_wake_word_pattern(grid, [[9, 9]])
# None

Step-by-Step Approach

1. Recognize this as 2D pattern search: find every valid top-left corner such that the pattern's dimensions fit within the grid from that corner, then verify an exact match cell by cell (or row by row).
2. First check the trivial rejection: if the pattern has more rows or more columns than the grid, no placement can possibly fit, so return None immediately.
3. Iterate candidate top-left corners (r, c) in row-major order — r from 0 up to rows - pattern_rows, c from 0 up to cols - pattern_cols — so the first match found is guaranteed to be the earliest.
4. For each candidate corner, compare the grid's rows against the pattern's rows using slice equality (grid_row[c:c+pcols] == pattern_row) rather than a manual cell-by-cell loop, which is both simpler and faster in practice.
5. Short-circuit as soon as one pattern row fails to match — there's no reason to check the remaining rows for a corner that's already ruled out.
6. Return the first corner that fully matches every pattern row; if the loop finishes with no match, return None.

The key insight is that comparing whole row slices instead of individual cells turns an inner double-loop into a single list-equality check per pattern row — still the same worst-case complexity, but each comparison runs at C speed instead of interpreted Python speed, which matters a lot once the grid gets large.

Reference solution

def find_wake_word_pattern(grid: list[list[int]], pattern: list[list[int]]) -> tuple[int, int] | None:
    rows, cols = len(grid), len(grid[0]) if grid else 0
    prows, pcols = len(pattern), len(pattern[0]) if pattern else 0
    if prows == 0 or pcols == 0 or prows > rows or pcols > cols:
        return None

    # brute-force top-left corners, but compare each candidate row via slice equality
    # (a fast C-level comparison), so this is effectively O(rows * cols * prows) in practice
    for r in range(rows - prows + 1):
        for c in range(cols - pcols + 1):
            if _matches_at(grid, pattern, r, c, pcols):
                return (r, c)
    return None


def _matches_at(grid: list[list[int]], pattern: list[list[int]], r: int, c: int, pcols: int) -> bool:
    for pr, pattern_row in enumerate(pattern):
        if grid[r + pr][c:c + pcols] != pattern_row:
            return False
    return True


TEST_CASES = [
    {
        "input": {
            "grid": [[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]],
            "pattern": [[6, 7], [1, 2]],
        },
        "expected": (1, 1),
    },
    {
        "input": {
            "grid": [[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]],
            "pattern": [[9, 9]],
        },
        "expected": None,
    },
    {
        "input": {"grid": [[1, 2], [3, 4]], "pattern": [[1, 2], [3, 4]]},
        "expected": (0, 0),
    },
    {
        "input": {"grid": [[1, 2], [3, 4]], "pattern": [[1, 2, 3], [3, 4, 5]]},
        "expected": None,
    },
    {
        "input": {"grid": [[1, 1], [1, 1], [1, 1]], "pattern": [[1, 1]]},
        "expected": (0, 0),
    },
    {
        "input": {"grid": [[5]], "pattern": [[5]]},
        "expected": (0, 0),
    },
]


def main():
    for i, case in enumerate(TEST_CASES):
        grid = case["input"]["grid"]
        pattern = case["input"]["pattern"]
        expected = case["expected"]
        print(f"Test {i}: find_wake_word_pattern(grid={grid}, pattern={pattern})")
        rows, cols = len(grid), len(grid[0]) if grid else 0
        prows, pcols = len(pattern), len(pattern[0]) if pattern else 0
        if prows > rows or pcols > cols:
            print(f"  pattern ({prows}x{pcols}) can't fit in grid ({rows}x{cols}) -> None")
        else:
            for r in range(rows - prows + 1):
                for c in range(cols - pcols + 1):
                    ok = _matches_at(grid, pattern, r, c, pcols)
                    print(f"  checking corner ({r},{c}) -> {'match' if ok else 'no match'}")
                    if ok:
                        break
                else:
                    continue
                break
        result = find_wake_word_pattern(grid=grid, pattern=pattern)
        assert result == expected
        print(f"PASSED: {result}")
    print(f"All {len(TEST_CASES)} test cases passed.")


if __name__ == "__main__":
    main()

Key Functions & Tricks

• rows - prows + 1 — the last valid row offset a pattern can start at without running off the grid
• grid[r + pr][c:c + pcols] — slices out exactly the window being compared to one pattern row
• _matches_at(grid, pattern, r, c, pcols) — checks every pattern row against the corresponding grid slice for one candidate corner
• prows > rows or pcols > cols — fast rejection before any scanning starts

How to Recognize This Pattern