Advent of Code 2024-Day 12: Garden Groups

from advent import parse, grid_to_hash

grid = grid_to_hash(parse(12, list))
dirs = (n, e, s, w) = (-1j, 1, 1j, -1)

def dfs(pos, plant, seen, fences, area=0):
    seen.add(pos)

    for dir in dirs:
        next_pos = pos + dir
        if grid.get(next_pos, None) == plant:
            if next_pos not in seen:
                area, fences = dfs(next_pos, plant, seen, fences, area)
        else:
            fences.append((pos, dir))

    return (area + 1, fences)

def sides(fences):
    sides      = 0
    horizontal = sorted([ (pos, dir) for pos, dir in fences if dir in (n, s) ],
                        key=lambda f: (str(f[1]), f[0].imag, f[0].real))
    vertical   = sorted([ (pos, dir) for pos, dir in fences if dir in (e, w) ],
                        key=lambda f: (str(f[1]), f[0].real, f[0].imag))

    prev_d, prev_x, prev_y = None, None, None

    for pos, dir in horizontal:
        x, y = pos.real, pos.imag
        if dir != prev_d or y != prev_y or x != prev_x + 1:
            sides += 1
        prev_d, prev_x, prev_y = dir, x, y

    prev_d, prev_x, prev_y = None, None, None

    for pos, dir in vertical:
        x, y = pos.real, pos.imag
        if dir != prev_d or x != prev_x or y != prev_y + 1:
            sides += 1
        prev_d, prev_x, prev_y = dir, x, y

    return sides

def solve(part):
    seen = set()
    return sum(area * part(fences) for area, fences in
               [ dfs(pos, grid[pos], seen, []) for pos in grid.keys() if pos not in seen ])

# ---------------------------------------------------------------------------------------------

assert solve(len)   == 1437300
assert solve(sides) == 849332

Parsing

We're given a grid of letters, and I'd like a dict with keys = position and values = letters:

grid = grid_to_hash(parse(12, list))

Solution

The two parts for today's puzzle are identical with the exception of the method of "scoring" the fence segments. Our first function is a depth first search to compute an entire garden plot. For each position in the plot, we look at all the (north, east, south, west) neighbors. If the neighbor does not have the same plant, we add a fence segment to a list. If it does have the same plant, we recurse if we haven't seen the neighbor before:

def dfs(pos, plant, seen, fences, area=0):
    seen.add(pos)

    for dir in dirs:
        next_pos = pos + dir
        if grid.get(next_pos, None) == plant:
            if next_pos not in seen:
                area, fences = dfs(next_pos, plant, seen, fences, area)
        else:
            fences.append((pos, dir))

    return (area + 1, fences)

The next function is a bit trickier. We need to compute the "sides" which are defined by contiguous sections of fences. To do this, we collect the fence segments into horizontal and vertical lists. Then, we sort each list by type (top, bottom, left or right), then x, y (or vice versa depending on horizontal or vertical). We process each list looking for changes that signify we have a new side:

def sides(fences):
    sides      = 0
    horizontal = sorted([ (pos, dir) for pos, dir in fences if dir in (n, s) ],
                        key=lambda f: (str(f[1]), f[0].imag, f[0].real))
    vertical   = sorted([ (pos, dir) for pos, dir in fences if dir in (e, w) ],
                        key=lambda f: (str(f[1]), f[0].real, f[0].imag))

    prev_d, prev_x, prev_y = None, None, None

    for pos, dir in horizontal:
        x, y = pos.real, pos.imag
        if dir != prev_d or y != prev_y or x != prev_x + 1:
            sides += 1
        prev_d, prev_x, prev_y = dir, x, y

    prev_d, prev_x, prev_y = None, None, None

    for pos, dir in vertical:
        x, y = pos.real, pos.imag
        if dir != prev_d or x != prev_x or y != prev_y + 1:
            sides += 1
        prev_d, prev_x, prev_y = dir, x, y

    return sides

Lastly, we have the solve() function. For every unseen position in the grid, call the dfs() function which returns a 2-tuple of area and fences. We parameterize solve() with the scoring function unique to each part. For Part 1, we just count the fence segments. For Part 2, we compute the sides from the fence segments:

def solve(part):
    seen = set()
    return sum(area * part(fences) for area, fences in
               [ dfs(pos, grid[pos], seen, []) for pos in grid.keys() if pos not in seen ])

solve(len)
solve(sides)

New Python Concepts

dict.get(key, default)

Conclusion

I feel my sides() function is clunky, and I expect there is a more elegant way to do this, but it works, and is reasonably understandable :) Although my methodology is clunky, Python made implementing it as painless as possible.