Day 12: Garden Groups

with open('input/12.txt', 'r') as f:
    lines = f.read().splitlines()

grid = {}
for y, line in enumerate(lines):
    for x, c in enumerate(line):
        grid[x + y * 1j] = c

def flood_fill(grid, start):
    region = set([start])
    symbol = grid[start]
    queue = [start]
    while queue:
        pos = queue.pop()
        for d in [1, -1, 1j, -1j]:
            new_pos = pos + d
            if new_pos in grid and new_pos not in region and grid[new_pos] == symbol:
                region.add(new_pos)
                queue.append(new_pos)
    return region


regions = []

uncovered = set(grid.keys())
while len(uncovered) > 0:
    start = uncovered.pop()
    region = flood_fill(grid, start)
    uncovered -= region
    regions.append((grid[start], region))

def get_area(region):
    return len(region[1])

def get_perimeter(region):
    perimeter = 0
    for pos in region[1]:
        for d in [1, -1, 1j, -1j]:
            new_pos = pos + d
            if new_pos not in region[1]:
                perimeter += 1
    return perimeter

price = 0
for region in regions:
    area, perimeter = get_area(region), get_perimeter(region)
    price += area * perimeter

print("Part 1:", price)

def get_sides_count(region):
    perimeter_objects = set()
    for pos in region[1]:
        for d in [1, -1, 1j, -1j]:
            new_pos = pos + d
            if new_pos not in region[1]:
                perimeter_objects.add((new_pos, d))
    
    distinct_sides = 0
    while len(perimeter_objects) > 0:
        pos, d = perimeter_objects.pop()
        distinct_sides += 1
        next = pos + d * 1j
        while (next, d) in perimeter_objects:
            perimeter_objects.remove((next, d))
            next += d * 1j
        next = pos + d * -1j
        while (next, d) in perimeter_objects:
            perimeter_objects.remove((next, d))
            next += d * -1j
    return distinct_sides

price = 0
for region in regions:
    area, sides = get_area(region), get_sides_count(region)
    price += area * sides
    
print("Part 2:", price)

For the first step, segmentation into regions, I used a disjoint-set structure. (I borrowed the implementation from SciPy, though I've written my own a few times.) I add all the individual cells to it as single-element sets, then make a pass over the them and wherever a cell has the same letter as one of its neighbors to the right or below, I merge the two subsets they belong to. After that, the disjoint set contains one subset per region and the elements of those subsets are the cells of that region.

Then I do a scan over each cell in each region:

• For area, I obviously just count one per cell.

• For the perimeter, I count one each if the cell above, to the left, to the right, or below isn't in the region.

• For the sides, the key observation that I eventually realized is that there is a one-to-one correspondence between sides and corners. So I can just count the corners. There are two classes of corners:

  • Outer corners. If the cells above and to the left aren't in the region, then I have an upper-left outer corner. Picture it like this with X for cells in the region, O for cells outside the region, and ? for don't-care cells.

    ?   O   ?
      +--
    O | X   ?
    
    ?   ?   ?
    

    And of course I do the same for the other three outer corners by symmetry.

  • Inner corners. If the cells above and to the left are in the region, but the diagonal cell isn't, then I have an upper-left inner corner:

    O | X   ?
    --+
    X   X   ?
    
    ?   ?   ?
    

    And of course, here too, I do the same for the other three inner corners by symmetry.

So it's possible to count the area, perimeter, and sides just by scanning over the cells in each region and looking at the 3✕3 neighborhood around each cell.

I posted a visualization of this in action over on Reddit.

import fileinput, scipy

g = { ( x, y ): c
      for y, r in enumerate( fileinput.input() )
      for x, c in enumerate( r.strip( '\n' ) ) }

d = scipy.cluster.hierarchy.DisjointSet( g )
for ( x, y ), v in g.items():
    for n in ( ( x + 1, y ), ( x, y + 1 ) ):
        if g.get( n, None ) == v:
            d.merge( ( x, y ), n )

t1, t2 = 0, 0
for r in d.subsets():
    a, p, s = 0, 0, 0
    for x, y in r:
        # Area
        a += 1
        # Perimeter
        p += ( x - 1, y ) not in r
        p += ( x + 1, y ) not in r
        p += ( x, y - 1 ) not in r
        p += ( x, y + 1 ) not in r
        # Outer corners
        s += ( x - 1, y ) not in r and ( x, y - 1 ) not in r
        s += ( x + 1, y ) not in r and ( x, y - 1 ) not in r
        s += ( x - 1, y ) not in r and ( x, y + 1 ) not in r
        s += ( x + 1, y ) not in r and ( x, y + 1 ) not in r
        # Inner corners
        s += ( x - 1, y ) in r and ( x, y - 1 ) in r and ( x - 1, y - 1 ) not in r
        s += ( x + 1, y ) in r and ( x, y - 1 ) in r and ( x + 1, y - 1 ) not in r
        s += ( x - 1, y ) in r and ( x, y + 1 ) in r and ( x - 1, y + 1 ) not in r
        s += ( x + 1, y ) in r and ( x, y + 1 ) in r and ( x + 1, y + 1 ) not in r
    t1 += a * p
    t2 += a * s
print( t1, t2 )

from collections import deque
import os

file = 'test.txt' if os.environ.get('DEBUG') == 'y' else 'input.txt'

grid = []

with open(file, 'r') as f:
    for line in f:
        grid.append(list(line.strip()))

dirs = [
    (-1, 0),
    (0, 1),
    (1, 0),
    (0, -1)
]

same_side_dirs = {
    (-1, 0): (0, -1),
    (0, 1): (-1, 0),
    (1, 0): (0, -1),
    (0, -1): (-1, 0),
}

rows = len(grid)
cols = len(grid[0])

def _in(row, col):
    return 0 <= row < rows and 0 <= col < cols

def bfs(row, col, enqueued):
    if (row, col) in enqueued:
        return 0, 0, 0

    enqueued.add((row, col))
    q = deque([(row, col)])
    perimeter = 0
    area = 0
    walls = 0
    area_id = grid[row][col]
    
    while q:
        x, y = q.pop()
        area += 1
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if not _in(nx, ny) or grid[nx][ny] != area_id:
                perimeter += 1
                sx, sy = same_side_dirs[(dx, dy)]
                if not is_same_wall(x + sx, y + sy, dx, dy, area_id):
                    walls += 1
            elif (nx, ny) not in enqueued:
                enqueued.add((nx, ny))
                q.appendleft((nx, ny))
    return area, perimeter, walls

def is_same_wall(row, col, dx, dy, area_id):
    nx, ny = row + dx, col + dy 
    same_region = _in(row, col) and grid[row][col] == area_id
    is_wall_in_dir = not _in(nx, ny) or grid[nx][ny] != area_id
    return same_region and is_wall_in_dir

enqueued = set()
total = 0
total_new = 0
for row in range(rows):
    for col in range(cols):
        area, perimeter, walls = bfs(row, col, enqueued)
        if area * perimeter: print(f"{area=}, {perimeter=}, {walls=}")
        total += area * perimeter
        total_new += area * walls
print(total)
print(total_new)

/* Advent of Code 2024
 * Day 12: Garden Groups
 */

#import "Basic";
#import "File";
#import "Hash";
#import "Hash_Table";
#import "String";

Vector2_Int :: struct {
    x, y: int;
}

Vector2_Int_Set :: Table(
    Vector2_Int,
    void,
    (vector: Vector2_Int) -> u32 {
        return inline sdbm_hash(xx *vector, size_of(Vector2_Int));
    },
    (a: Vector2_Int, b: Vector2_Int) -> bool {
        return a.x == b.x && a.y == b.y;
    }
);

main :: () {
    input, success := read_entire_file("inputs/day_12.txt");
    assert(success);

    map := split(input, "\n");
    pop(*map);
    defer array_free(map);

    width := map[0].count;
    height := map.count;

    // Using an array like this appears to be faster than a table/set when we
    // don't need to count the elements.
    seen_positions := NewArray(width * height, bool);
    defer array_free(seen_positions);

    price_part_1 := 0;
    price_part_2 := 0;

    for x: 0..width - 1 {
        for y: 0..height - 1 {
            if seen_positions[y * width + x] {
                continue;
            }

            plant_type := map[y][x];
            position := Vector2_Int.{x, y};

            // Here, we need to count the elements (to find the area of the
            // plot) and iterate through them (to transfer all the plants in the
            // plot into seen_positions), so we're forced to use a set.
            plot: Vector2_Int_Set;
            table_add(*plot, position, #run {});
            defer deinit(*plot);

            // Because we're using arrays for fences_x and fences_y, we have to
            // store the perimeter separately.
            perimeter := 0;

            // These arrays store all the individual fences (like what is used
            // for part 1). fences_x stores vertical fences, and fences_y stores
            // horizontal ones - the arrays are named based on the direction the
            // fence is moved into from.
            //
            // The reason for using arrays is the same as with seen_positions,
            // though these need to be slightly bigger to fit all the fences.
            fences_x := NewArray((width + 1) * height, int);
            fences_y := NewArray(width * (height + 1), int);
            defer array_free(fences_x);
            defer array_free(fences_y);

            stack: [..] Vector2_Int;
            array_add(*stack, position);
            defer array_free(stack);

            while stack.count {
                current := pop(*stack);
                for *Vector2_Int.[
                    .{current.x - 1, current.y},
                    .{current.x + 1, current.y},
                    .{current.x, current.y - 1},
                    .{current.x, current.y + 1}
                ] {
                    if
                        it.x < 0 || it.x >= width || it.y < 0 || it.y >= height
                        || map[it.y][it.x] != plant_type
                    {
                        perimeter += 1;

                        // The first two indices are vertical sides, and the
                        // second two are horizontal.
                        if it_index < 2 {
                            if it_index == 0 {
                                it.x += 1;
                                fences_x[it.y * (width + 1) + it.x] = -1;
                            } else {
                                fences_x[it.y * (width + 1) + it.x] = 1;
                            }
                        } else {
                            if it_index == 2 {
                                it.y += 1;
                                fences_y[it.y * width + it.x] = -1;
                            } else {
                                fences_y[it.y * width + it.x] = 1;
                            }
                        }

                        continue;
                    }

                    if !table_contains(*plot, it) {
                        table_add(*plot, it, #run {});
                        array_add(*stack, it);
                    }
                }
            }

            price_part_1 += plot.count * perimeter;

            // I dislike having all this repeated code between vertical and
            // horizontal fences, but I'm not sure if there's a clean way to
            // make things less redundant. I'm just going to leave it.
            sides_x := 0;
            for fence_x: 0..width {
                in_side := false;
                side_bias: int;

                for fence_y: 0..height - 1 {
                    bias := fences_x[fence_y * (width + 1) + fence_x];
                    if bias != 0 {
                        if !in_side || bias != side_bias {
                            in_side = true;
                            side_bias = bias;
                            sides_x += 1;
                        }
                    } else if in_side {
                        in_side = false;
                    }
                }
            }

            sides_y := 0;
            for fence_y: 0..height {
                in_side := false;
                side_bias: int;

                for fence_x: 0..width - 1 {
                    bias := fences_y[fence_y * width + fence_x];
                    if bias != 0 {
                        if !in_side || bias != side_bias {
                            in_side = true;
                            side_bias = bias;
                            sides_y += 1;
                        }
                    } else if in_side {
                        in_side = false;
                    }
                }
            }

            price_part_2 += plot.count * (sides_x + sides_y);

            for plot {
                seen_positions[it_index.y * width + it_index.x] = true;
            }
        }
    }

    print("Part 1: %\nPart 2: %\n", price_part_1, price_part_2);
}

My solution to Part 1 relies on a UnionFind data structure, which I had prepared in advance of AoC. UnionFind allows you to efficiently find the area for each plant in the input by 'merging' adjacent plants.
Then it's a simple matter of finding the border tiles around a set of plants and counting them up.

pub fn part1(input: &PuzzleInput) -> String {
    let mut sum = 0;

    for region in find_regions(&input.garden).into_iter() {
        let mut border = HashMap::new();

        for coord in region.iter() {
            for neighbor in coord.neighbors() {
                if !region.contains(&neighbor) {
                    border.entry(coord).and_modify(|c| *c += 1).or_insert(1);
                }
            }
        }

        sum += border.values().sum::<i32>() * region.len() as i32;
    }

    sum.to_string()
}

pub fn find_regions(input: &Grid2D<char>) -> Vec<HashSet<Coordinate>> {
    let mut union_find = UnionFind::default();
    let mut sets = HashMap::new();
    let mut result = vec![];

    for (coord, &plant) in input.iter() {
        let set = union_find.make_set();
        sets.insert(coord, set);
    }

    for (coord, &plant) in input.iter() {
        for neighbor in coord.neighbors() {
            if let Some(neighbor_plant) = input.get(neighbor) {
                if *neighbor_plant == plant {
                    let _ = union_find.union(sets[&coord], sets[&neighbor]);
                }
            }
        }
    }

    for root in union_find.roots() {
        let mut plot = HashSet::new();

        for (coord, &set) in sets.iter() {
            if union_find.find(set) == Some(root) {
                plot.insert(*coord);
            }
        }

        result.push(plot);
    }

    result
}

I initially tried to walk along the edges of the plots. Doing so naively doesn't work with plots contained in other plots, but eventually I got all the test inputs passing. It just didn't work on the actual input.

So after hours of frustration, I instead fell back on UnionFind again to merge adjacent border tiles (which is really the more obvious way to do this, I guess, but it didn't work for me initially so I abandoned the idea). This needs to be done separately for horizontal and vertical borders, because those 'sides' are counted separately.

pub fn part2(input: &PuzzleInput) -> String {
    let mut sum = 0;

    // Replace every tile with 16 new tiles. This is probably overkill, but that's what worked.
    let input = input.garden.zoom(4);

    for region in find_regions(&input).into_iter() {
        let mut union_find_horizontal = UnionFind::default();
        let mut union_find_vertical = UnionFind::default();
        let mut sets_horizontal = HashMap::new();
        let mut sets_vertical = HashMap::new();

        let id = input[*region.iter().next().unwrap()];

        let mut border = HashSet::new();

        for coord in region.iter() {
            for neighbor in coord.moore_neighbors() {
                if !region.contains(&neighbor) {
                    border.insert(neighbor);
                }
            }
        }

        for coord in border.iter() {
            let set_h = union_find_horizontal.make_set();
            let set_v = union_find_vertical.make_set();
            sets_horizontal.insert(**coord, set_h);
            sets_vertical.insert(**coord, set_v);
        }

        for coord in border.iter() {
            let right = coord.neighbor(Direction::Right);

            if border.contains(&right) {
                union_find_horizontal
                    .union(sets_horizontal[&coord], sets_horizontal[&right])
                    .expect("Foo");
            }

            let down = coord.neighbor(Direction::Down);

            if border.contains(&down) {
                union_find_vertical
                    .union(sets_vertical[&coord], sets_vertical[&down])
                    .expect("Foo");
            }
        }

        let mut horizontal_count = 0;
        let mut horizontal_counted = HashSet::new();

        for (coord, set_h) in sets_horizontal.iter() {
            let root = union_find_horizontal.find(*set_h).unwrap();
            let size = union_find_horizontal.size_of_set(root).unwrap_or(0);

            if !horizontal_counted.insert(root) {
                continue;
            }

            if size > 1 {
                horizontal_count += 1;
            }
        }

        let mut vertical_count = 0;
        let mut vertical_counted = HashSet::new();

        for (coord, set_v) in sets_vertical.iter() {
            let root = union_find_vertical.find(*set_v).unwrap();
            let size = union_find_vertical.size_of_set(root).unwrap_or(0);

            if !vertical_counted.insert(root) {
                continue;
            }

            if size > 1 {
                vertical_count += 1;
            }
        }

        sum += (horizontal_count + vertical_count) * region.len() / 16;
    }

    return sum.to_string();
}

I'm omitting the UnionFind code. It's easy to write the data structure by following the Wikipedia article.