disk defragmentation

approach

this day reuses the knot hash from day 10 through the shared knot-hash module. each of the 128 rows is the knot hash of the key plus -i, expanded by binary into a list of 0/1 bits.

part 1 sums all the bits. part 2 scans the grid and, at every used cell that hasn't been visited, runs a recursive dfs that marks its whole 4-connected region as -1; the number of dfs starts is the number of regions.

the trick

overwrite visited cells in the grid itself, so counting regions is just counting how many floods you start.

def dfs(grid, r, c):
    for nr, nc in neighbors(grid, r, c):
        if grid[nr][nc] == 1:
            grid[nr][nc] = -1
            dfs(grid, nr, nc)