Grid Traversal

All seven patterns in this topic so far worked on one-dimensional data: an array, a stream, a successor chain. The last pattern handles data in two dimensions. A grid has filled cells, and the question is: how many sets of cells connected to one another are there.

A grid is not really a new structure. Every filled cell is a node, every pair of neighboring cells is an edge; what is asked is the number of connected components, and the procedure was established in the Data Structures course. Breadth-first and depth-first search themselves, why marking a visit is required, and the $O(V + E)$ cost were measured there; they are not repeated here, they are used directly.

What the pattern adds is the modeling, and that is where its precondition sits: what connectivity means. This lesson counts how many different answers two connectivity definitions produce on the same grid.

Problem, Oracle, and Pattern

The oracle does no traversal at all. It scans every pair of filled cells, groups adjacent ones together, and repeats until no merge remains. The pattern starts a breadth-first search from every unvisited filled cell, and every search counts as one component.

PP56. The corpus is 40 grids; each grid is 8×8, and every cell is filled with a probability of 30 in 100. Seed 20260218. PP57. Two connectivity definitions are measured: 4-connectivity (edge-adjacent cells only) and 8-connectivity (corner-adjacent cells included too). PP58. The oracle and the pattern are run separately with each connectivity definition; all four combinations are measured. This shows whether a divergence comes from the pattern or from a difference in definition. PP59. The visit is marked on enqueue; this is the rule established in the Breadth-First Search lesson and its rationale is not repeated here.

from collections import deque

SEED, SIZE, CORPUS_SIZE = 20260218, 8, 40


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def grid_corpus(seed=SEED, n=CORPUS_SIZE, size=SIZE):
    r = generator(seed)
    return [{"no": i + 1,
             "grid": [[1 if r(101) < 30 else 0 for _ in range(size)]
                      for _ in range(size)]}
            for i in range(n)]


class Counter:
    def __init__(self):
        self.step = 0

    def count(self):
        self.step += 1


def adjacent(a, b, connectivity):
    di, dj = abs(a[0] - b[0]), abs(a[1] - b[1])
    return di + dj == 1 if connectivity == 4 else max(di, dj) == 1 and (di or dj)


def oracle_component(grid, connectivity, s):
    """Scans every cell pair, groups adjacent ones, repeats until no change.
    Always correct, always expensive."""
    cell = [(i, j) for i, row in enumerate(grid)
            for j, v in enumerate(row) if v]
    group = {h: i for i, h in enumerate(cell)}
    changed = True
    while changed:
        changed = False
        for a in range(len(cell)):
            for b in range(a + 1, len(cell)):
                s.count()
                if adjacent(cell[a], cell[b], connectivity) and \
                        group[cell[a]] != group[cell[b]]:
                    old, new = group[cell[b]], group[cell[a]]
                    for h in cell:
                        if group[h] == old:
                            group[h] = new
                    changed = True
    return len(set(group.values()))


DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1))
DIR8 = DIR4 + ((-1, -1), (-1, 1), (1, -1), (1, 1))


def pattern_bfs(grid, connectivity, s):
    """The Data Structures course's breadth-first search is used directly: the
    visit is marked ON ENQUEUE."""
    direction = DIR4 if connectivity == 4 else DIR8
    n, m = len(grid), len(grid[0])
    visited, component, widest = set(), 0, 0
    for i in range(n):
        for j in range(m):
            if not grid[i][j] or (i, j) in visited:
                continue
            component += 1
            visited.add((i, j))
            queue = deque([(i, j)])
            while queue:
                widest = max(widest, len(queue))
                x, y = queue.popleft()
                s.count()
                for dx, dy in direction:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and grid[a][b] \
                            and (a, b) not in visited:
                        visited.add((a, b))
                        queue.append((a, b))
    return component, widest


K = grid_corpus()
filled = sum(sum(sum(row) for row in k["grid"]) for k in K)
print("corpus:", len(K), "grids x", SIZE, "x", SIZE, "| filled cells:", filled,
      "| average", round(filled / len(K), 2))
print("pattern connectivity  oracle connectivity  diverging/40  pattern   oracle    ratio")
for pc in (4, 8):
    for oc in (4, 8):
        diverging, pk, ok = 0, 0, 0
        for record in K:
            s1, s2 = Counter(), Counter()
            a, _ = pattern_bfs(record["grid"], pc, s1)
            b = oracle_component(record["grid"], oc, s2)
            pk, ok = pk + s1.step, ok + s2.step
            diverging += (a != b)
        print(f"{pc:19d}  {oc:19d}  {diverging:10d}  {pk:5d}  {ok:6d}"
              f"  {ok / pk:6.1f}")

corpus: 40 grids x 8 x 8 | filled cells: 723 | average 18.07
pattern connectivity  oracle connectivity  diverging/40  pattern   oracle    ratio
                  4                    4           0    723   12768    17.7
                  4                    8          38    723   12834    17.8
                  8                    4          38    723   12768    17.7
                  8                    8           0    723   12834    17.8

The diagonal rows are zero, the other two are 38. When the pattern uses the same connectivity definition as the oracle, it gives the same answer on 40 of 40 grids; once the definitions diverge, 38 of 40 grids diverge.

This table makes one thing certain: the divergence does not come from the pattern. Breadth-first search works correctly with either definition; what is broken is not the pattern itself, it is the connectivity definition given to it. The pattern’s step count is 723 in both definitions, the oracle’s is 12,768 to 12,834; the ratio is 17.7. The step column is nearly identical across all four rows and gives no signal at all about the diverging-input column.

Connectivity Is Not a Data Property, It Is a Decision

In the previous seven patterns, the precondition was a property of the input: sorted or not, negative or not, duplicate or not. Here the precondition is not in the input; it is a decision made by whoever modeled the problem, and cannot be verified by looking at the data. The small grid below shows this in a glance.

PP60. The small example is built by hand; it comes from no generator and exists only to show the divergence between the two definitions. PP61. The second corpus comes from seed 20260219. What is measured is how many grids the two definitions give a different component count on.

from collections import deque


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def grid_corpus(seed, n=40, size=8):
    r = generator(seed)
    return [[[1 if r(101) < 30 else 0 for _ in range(size)] for _ in range(size)]
            for _ in range(n)]


DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1))
DIR8 = DIR4 + ((-1, -1), (-1, 1), (1, -1), (1, 1))


def component(grid, connectivity):
    """Component count by breadth-first search; the visit is marked on enqueue."""
    direction = DIR4 if connectivity == 4 else DIR8
    n, m = len(grid), len(grid[0])
    visited, count = set(), 0
    for i in range(n):
        for j in range(m):
            if not grid[i][j] or (i, j) in visited:
                continue
            count += 1
            visited.add((i, j))
            queue = deque([(i, j)])
            while queue:
                x, y = queue.popleft()
                for dx, dy in direction:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and grid[a][b] \
                            and (a, b) not in visited:
                        visited.add((a, b))
                        queue.append((a, b))
    return count


small = [[1, 0, 0, 0, 1],
         [0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0],
         [0, 1, 0, 1, 0],
         [1, 0, 0, 0, 1]]
for row in small:
    print("  ", "".join("#" if v else "." for v in row))
print("  4-connectivity:", component(small, 4), "components")
print("  8-connectivity:", component(small, 8), "components")
print()
print("seed       4-connectivity total  8-connectivity total  differing grid/40")
for seed in (20260218, 20260219):
    K = grid_corpus(seed)
    d4 = [component(g, 4) for g in K]
    d8 = [component(g, 8) for g in K]
    differing = sum(1 for a, b in zip(d4, d8) if a != b)
    print(f"{seed}  {sum(d4):17d}  {sum(d8):17d}  {differing:16d}")

   #...#
   .#.#.
   ..#..
   .#.#.
   #...#
  4-connectivity: 9 components
  8-connectivity: 1 components

seed       4-connectivity total  8-connectivity total  differing grid/40
20260218                387                233                38
20260219                377                227                38

The five-row grid has nine cells and none of them is edge-adjacent; all of them sit on a diagonal. With 4-connectivity there are 9 separate components; with 8-connectivity, a single component. Same data, same procedure, a ninefold difference.

In the forty-grid corpus, total component count drops from 387 to 233, and the two definitions give a different answer on 38 grids. In the second corpus the numbers are 377 and 227, differing grids again 38; the result does not depend on the corpus.

The practical conclusion of this measurement is this: the first question to ask when reading a grid problem is what connectivity means. If the definition is not written in the problem statement, the correctness of the pattern’s answer cannot be tested — not even the oracle can be built, because the oracle needs the same definition too. This is the topic’s only precondition that cannot be determined by looking at the data.

Marking and Traversal Change What Is Held, Not the Answer

Once connectivity is fixed, two implementation decisions remain: whether marking happens on enqueue or on dequeue, and whether the traversal is breadth-first or depth-first. Neither changes the component count. What they change is the number of cells held at once.

PP62. This measurement is done on a larger grid: 10 grids, each 20×20, cells filled with probability 60 in 100. In a small, sparse grid the difference between these three procedures falls below the resolution. PP63. What is measured is, for breadth-first search, the queue’s widest point, and for depth-first search, the largest value of recursion depth.

from collections import deque


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def grid_corpus(seed=20260218, n=10, size=20):
    r = generator(seed)
    return [[[1 if r(101) < 60 else 0 for _ in range(size)] for _ in range(size)]
            for _ in range(n)]


DIR4 = ((-1, 0), (1, 0), (0, -1), (0, 1))


def bfs(grid, on_enqueue):
    """Is marking done ON ENQUEUE or ON DEQUEUE."""
    n, m = len(grid), len(grid[0])
    visited, component, step, widest = set(), 0, 0, 0
    for i in range(n):
        for j in range(m):
            if not grid[i][j] or (i, j) in visited:
                continue
            component += 1
            queue = deque([(i, j)])
            if on_enqueue:
                visited.add((i, j))
            while queue:
                widest = max(widest, len(queue))
                x, y = queue.popleft()
                step += 1
                if not on_enqueue:
                    if (x, y) in visited:
                        continue
                    visited.add((x, y))
                for dx, dy in DIR4:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and grid[a][b] \
                            and (a, b) not in visited:
                        if on_enqueue:
                            visited.add((a, b))
                        queue.append((a, b))
    return component, step, widest


def dfs(grid):
    """Recursive depth-first search; the deepest stack size is measured."""
    n, m = len(grid), len(grid[0])
    visited, component, step, deepest = set(), 0, 0, 0

    def visit(x, y, depth):
        nonlocal step, deepest
        step += 1
        deepest = max(deepest, depth)
        visited.add((x, y))
        for dx, dy in DIR4:
            a, b = x + dx, y + dy
            if 0 <= a < n and 0 <= b < m and grid[a][b] \
                    and (a, b) not in visited:
                visit(a, b, depth + 1)

    for i in range(n):
        for j in range(m):
            if grid[i][j] and (i, j) not in visited:
                component += 1
                visit(i, j, 1)
    return component, step, deepest


K = grid_corpus()
base = [bfs(g, True) for g in K]
print("corpus: 10 grids x 20 x 20 | filled cells:",
      sum(sum(sum(row) for row in g) for g in K))
print("traversal                    same component  steps  most held cells")
for ad, result in (("bfs, mark on enqueue     ", base),
                  ("bfs, mark on dequeue     ", [bfs(g, False) for g in K]),
                  ("dfs (recursive)          ", [dfs(g) for g in K])):
    same = sum(1 for a, b in zip(result, base) if a[0] == b[0])
    print(f"{ad}  {same:12d}  {sum(x[1] for x in result):4d}"
          f"  {max(x[2] for x in result):20d}")

corpus: 10 grids x 20 x 20 | filled cells: 2378
traversal                    same component  steps  most held cells
bfs, mark on enqueue                 10  2378                    18
bfs, mark on dequeue                 10  2887                    24
dfs (recursive)                      10  2378                   103

All three rows give the same component count: 10 of 10 grids match. Diverging inputs are zero, and these rows are not a correctness measurement.

The difference measured sits in two columns instead. Marking on dequeue raises steps from 2378 to 2887 and the widest queue from 18 to 24: the same cell enters the queue more than once before being visited. Depth-first search’s step count is identical to breadth- first search’s (2378), but its deepest stack holds 103 cells — roughly five and a half times breadth-first search’s widest queue.

This last number is a practical limit. On a dense, large grid, recursive depth-first search demands a stack depth proportional to the grid’s size; breadth-first search demands a queue proportional to the widest layer. Which is cheaper depends on the grid’s shape, and this distinction was already established in the Data Structures course’s comparison table; here the same distinction is confirmed numerically.

Three Numbers

Metric	Oracle	Pattern	Diverging input
4-connectivity, 4-connectivity	12,768 steps	723 steps	0/40
8-connectivity, 4-connectivity	12,768 steps	723 steps	38/40
Breadth-first search, 20×20 grid	—	2378 steps / 18 cells	0/10
Depth-first search, 20×20 grid	—	2378 steps / 103 cells	0/10

In the first two rows the pattern’s step count is identical, and diverging inputs range from 0 to 38; in the last two rows diverging inputs are identical and held cell count changes by five and a half times. Two kinds of decision show up in two separate columns — and neither leaves a trace in the other’s column.

Summary

• A grid is a graph: filled cells are nodes, adjacent cell pairs are edges; connected- component counting is done with the Data Structures course’s breadth-first and depth-first search.
• When the pattern uses the same connectivity definition as the oracle, it is correct on 40 of 40 grids; once the definitions diverge, it diverges on 38 grids, and the pattern’s step count is 723 in both cases.
• Connectivity is a decision made by whoever models the problem, not a property of the data; it cannot be determined by looking at the data, and the oracle cannot even be built without it.
• A nine-cell diagonal grid gives 9 components under 4-connectivity and 1 under 8-connectivity; the total over the 40-grid corpus drops from 387 to 233.
• Marking on dequeue does not change the answer but raises steps from 2378 to 2887 and the queue from 18 to 24; depth-first search holds a stack of 103 cells at the same step count.

Next Step

This topic measured eight patterns under the same frame: an oracle, a pattern, and the number of inputs where the two diverge. In all eight lessons, the source of divergence was not a bug in the pattern — it was an accepted but unchecked precondition: order, sign, single successor, sort key, value range, balance, the question’s definition, and connectivity. The next topic moves from patterns to named problems: the knapsack, the traveling salesman, the longest path, the n-queens placement. The question asked there changes — not whether a pattern’s precondition has broken, but why a problem is hard; and the oracle remains the tool by which that hardness is measured.