Uiua

I spent a while thinking about how to best do a flood fill in Uiua when I saw that ⊜ (partition) works beautifully with multidimensional markers: “Groups are formed from markers that are adjacent along any axis.”, meaning I just had to convert all letters into numbers and I’d get all indices belonging to a field into an array.
For part 2, I cheated a bit by coming here and reading that you only need to count the edges. To my surprise, the second part is actually a bit faster than part 1. Takes less than 0.2 seconds each though :D

Run with example input here

$ RRRRIICCFF
$ RRRRIICCCF
$ VVRRRCCFFF
$ VVRCCCJFFF
$ VVVVCJJCFE
$ VVIVCCJJEE
$ VVIIICJJEE
$ MIIIIIJJEE
$ MIIISIJEEE
$ MMMISSJEEE
.
N     ← +[0_¯1 0_1 ¯1_0 1_0]
Areas ← ⊜□:⇡△.+1⍜♭⊛
Peri  ← -/+≡(/+∊N¤)⟜¤⟜(×4⧻)
Sides ← (
  ⊙(-¤)↯:▽⊙0×°⊟.+2⌵⊸-+1⊃⊣⊢⊸⍜⍉≡⍆
  ⧻⊚⊸∊1_3⧈(/+/+)2_2.⍜⊡=₀+1:
  +⊙(×2/+/+⧈(∊[[1_0 0_1][0_1 1_0]])2_2◌)
)
Cost! ← /+≡◇(×^0⟜⧻)

PartOne ← (
  # &rs ∞ &fo "input-12.txt"
  ⊜∘≠@\n.
  Cost!Peri Areas
)

PartTwo ← (
  # &rs ∞ &fo "input-12.txt"
  ⊜∘≠@\n.
  Cost!Sides Areas
)

&p "Day 12:"
&pf "Part 1: "
&p PartOne
&pf "Part 2: "
&p PartTwo

Rust

Areas are found by flooding, in the meantime whenever the adjacent plot would be outside the region (or out of bounds) the edge (inside plot, outside plot) is saved in a perimeter list. Part 1 takes just the size of that list, in part 2 we remove fence parts and all entries directly next to it on both sides.

use std::collections::{HashSet, VecDeque};

use euclid::{default::*, point2, vec2};

type Fences = HashSet<(Point2D<i32>, Point2D<i32>)>;
const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)];

fn parse(input: &str) -> Vec<&[u8]> {
    input.lines().map(|l| l.as_bytes()).collect()
}

fn price(field: &[&[u8]], start: (usize, usize), visited: &mut [Vec<bool>]) -> (u32, Fences) {
    let crop = field[start.1][start.0];
    let width = field[0].len();
    let height = field.len();
    let mut area_visited = vec![vec![false; width]; height];
    let mut area = 0;
    let mut fences: Fences = HashSet::new();

    area_visited[start.1][start.0] = true;
    visited[start.1][start.0] = true;
    let start = point2(start.0 as i32, start.1 as i32);
    let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32());
    let mut frontier = VecDeque::from([start]);
    while let Some(p) = frontier.pop_front() {
        area += 1;
        for dir in DIRS {
            let next = p + dir;
            if bounds.contains(next) {
                let next_u = next.to_usize();
                if area_visited[next_u.y][next_u.x] {
                    continue;
                }
                if field[next_u.y][next_u.x] == crop {
                    visited[next_u.y][next_u.x] = true;
                    area_visited[next_u.y][next_u.x] = true;
                    frontier.push_back(next);
                    continue;
                }
            }
            fences.insert((p, next));
        }
    }
    (area, fences)
}

fn part1(input: String) {
    let field = parse(&input);
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![false; width]; height];
    let mut total_price = 0;
    for y in 0..height {
        for x in 0..width {
            if !visited[y][x] {
                let (area, fences) = price(&field, (x, y), &mut visited);
                total_price += area * fences.len() as u32;
            }
        }
    }
    println!("{total_price}");
}

fn count_perimeter(mut fences: Fences) -> u32 {
    let list: Vec<_> = fences.iter().copied().collect();
    let mut perimeter = 0;
    for (v, w) in list {
        if fences.contains(&(v, w)) {
            perimeter += 1;
            let dir = w - v;
            let orth = dir.yx();
            let mut next = v + orth;
            while fences.remove(&(next, next + dir)) {
                next += orth;
            }
            let mut next = v - orth;
            while fences.remove(&(next, next + dir)) {
                next -= orth;
            }
        }
    }
    perimeter
}

fn part2(input: String) {
    let field = parse(&input);
    let width = field[0].len();
    let height = field.len();
    let mut visited = vec![vec![false; width]; height];
    let mut total_price = 0;
    for y in 0..height {
        for x in 0..width {
            if !visited[y][x] {
                let (area, fences) = price(&field, (x, y), &mut visited);
                total_price += area * count_perimeter(fences);
            }
        }
    }
    println!("{total_price}");
}

util::aoc_main!();

Also on github

C

No big trouble today, just a bit of careful debugging of my part 2 logic for which I was greatly helped by some Redditor’s testcase 🙏

Happy to have gotten it all in the single flood fill function without any extra passes.

#include "common.h"

#define GZ 144
static char g[GZ][GZ];
static char seen[GZ][GZ];

static void
count(char c, int x, int y, int *area, int *perim, int *sides)
{
	if (g[y][x] != c) { (*perim)++; return; }
	if (seen[y][x]) return;

	*area += 1;
	seen[y][x] = 1;

	/* count start of top/left edges, end of bottom/right edges */
	*sides += g[y-1][x]!=c && ((g[y-1][x-1]==c) || (g[y][x-1]!=c));
	*sides += g[y+1][x]!=c && ((g[y+1][x+1]==c) || (g[y][x+1]!=c));
	*sides += g[y][x-1]!=c && ((g[y-1][x-1]==c) || (g[y-1][x]!=c));
	*sides += g[y][x+1]!=c && ((g[y+1][x+1]==c) || (g[y+1][x]!=c));

	count(c, x, y-1, area, perim, sides);
	count(c, x, y+1, area, perim, sides);
	count(c, x-1, y, area, perim, sides);
	count(c, x+1, y, area, perim, sides);
}

int
main(int argc, char **argv)
{
	int p1=0,p2=0, x,y, area, perim, sides;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	for (y=1; fgets(g[y]+1, GZ-2, stdin); y++)
		assert(y+1 < GZ);

	for (y=1; y<GZ-1; y++)
	for (x=1; x<GZ-1; x++)
		if (isalpha(g[y][x]) && !seen[y][x]) {
			area  = perim = sides = 0;
			count(g[y][x], x, y, &area, &perim, &sides);
			p1 += area * perim;
			p2 += area * sides;
		}

	printf("12: %d %d\n", p1, p2);
}

https://github.com/sjmulder/aoc/blob/master/2024/c/day12.c

Rust

I essentially used flood fill to collect each region. Part 1 was then relatively easy: for each point, check how many neighbors are outside of the region.

Part 2 took me forever, and I ended up looking for hints online, where I discovered that an easy way to count the number of sides is to instead count the number of corners. Doing this for “normal” corners (e.g. in a square) was relatively easy, but “reverse corners” took me a long time. Corners like here what we see in the NE corner of the first C in the third row here:

....
..C.
..CC
...C

I’m more or less happy with my solution, but my brain is now totally fried.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day12.rs?ref_type=heads

use std::collections::HashSet;

use crate::grid::{Coordinate, Direction, Grid};
use crate::solver::DaySolver;

fn perimeter_score(c: Coordinate, grid: &MyGrid) -> usize {
    let plant_type = grid[c];

    Direction::orthogonal_iter()
        .map(|d| grid.neighbor_in_direction(c, d))
        .map(|c_opt| match c_opt {
            None => 1,
            Some(c) => if grid[c] == plant_type {
                0
            } else {
                1
            }
        })
        .sum()
}

type MyGrid = Grid<char>;

struct Region {
    #[allow(dead_code)]
    plant_type: char,
    coordinates: HashSet<Coordinate>,
}

impl Region {
    fn new(plant_type: char, coordinates: HashSet<Coordinate>) -> Region {
        Region { plant_type, coordinates }
    }

    fn iter(&self) -> impl Iterator<Item = &Coordinate> {
        self.coordinates.iter()
    }

    fn part1_score(&self, grid: &MyGrid) -> usize {
        self.coordinates.len() * self.coordinates.iter().map(|c| perimeter_score(*c, grid)).sum::<usize>()
    }

    fn part2_score(&self, grid: &MyGrid) -> usize {
        let area = self.coordinates.len();
        let sides = self.number_of_corners(grid);

        area * sides
    }

    fn number_of_corners(&self, grid: &MyGrid) -> usize {
        self.coordinates.iter().cloned()
            .map(|coordinate| {
                // How many corners do we have from here?
                // println!("Checking {}", border_coordinate);

                let corner_count = Direction::diagonal_iter()
                    .filter(|corner_direction| {
                        // Either:
                        // 1) Both neighbor directions are not 100% in the region
                        // 2) Both neighbors are in the region, but the corner itself isn't

                        let corner_in_region = match grid.neighbor_in_direction(coordinate, *corner_direction) {
                            None => false,
                            Some(c) => self.coordinates.contains(&c),
                        };

                        let both_neighbors_not_in_region = corner_direction.neighbor_directions().iter()
                            .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                None => true,
                                Some(c) => !self.coordinates.contains(&c),
                            });

                        let both_neighbors_in_region = corner_direction.neighbor_directions().iter()
                            .all(|direction| match grid.neighbor_in_direction(coordinate, *direction) {
                                None => false,
                                Some(c) => self.coordinates.contains(&c),
                            });

                        both_neighbors_not_in_region || (both_neighbors_in_region && !corner_in_region)
                    })
                    .count();
                // println!("Corner count = {}", corner_count);
                corner_count
            })
            .sum()
    }
}

fn parse_input(input: String) -> MyGrid {
    input.lines()
        .map(|line| line.chars().collect())
        .collect::<Vec<Vec<char>>>()
        .into()
}

fn find_region_at(grid: &MyGrid, start: Coordinate) -> Region {
    let plant_type = grid[start];
    let mut coordinates = HashSet::new();
    let mut frontier = vec![start];

    while let Some(coordinate) = frontier.pop() {
        if grid[coordinate] == plant_type  && !coordinates.contains(&coordinate) {
            coordinates.insert(coordinate);
            frontier.extend(grid.orthogonal_neighbors_iter(coordinate));
        }
    }

    Region::new(plant_type, coordinates)
}

fn find_regions(grid: &MyGrid) -> Vec<Region> {
    let mut visited_coordinates: HashSet<Coordinate> = HashSet::new();
    let mut regions = vec![];

    for coordinate in grid.coordinates_iter() {
        if !visited_coordinates.contains(&coordinate) {
            let region = find_region_at(grid, coordinate);
            visited_coordinates.extend(region.iter().cloned());
            regions.push(region);
        }
    }

    regions
}

pub struct Day12Solver;

impl DaySolver for Day12Solver {
    fn part1(&self, input: String) -> usize {
        let grid = parse_input(input);
        let regions = find_regions(&grid);

        regions.into_iter()
            .map(|region| region.part1_score(&grid))
            .sum()
    }

    fn part2(&self, input: String) -> usize {
        let grid = parse_input(input);
        let regions = find_regions(&grid);

        regions.into_iter()
            .map(|region| region.part2_score(&grid))
            .sum()
    }
}

Python

Part 1: Simple DFS counting up the cells and exposed edges

Part 2: Still DFS, however I chose to keep track of all segments of the area, merging them if two segments connected. In the end, number of non-overlapping, non-intersecting segments is equal to number of sides. Not the most efficient solution, but it works.

import os
from collections import defaultdict

# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, "input.txt")

# read input
with open(filepath, mode="r", encoding="utf8") as f:
    data = f.read()
# setup input vars
garden = data.splitlines()
m, n = len(garden), len(garden[0])


def part1():
    visited = set()

    def calcFenceCostFrom(i, j):
        """Calculates the fencing cost of the region starting from coords (i, j)"""
        global garden, m, n

        plant_type = garden[i][j]
        stack = [(i, j)]
        area, perimeter = 0, 0

        while stack:
            ci, cj = stack.pop()
            if (ci, cj) in visited:
                continue
            visited.add((ci, cj))

            # add cell to area
            area += 1

            # check top cell
            if ci > 0 and garden[ci - 1][cj] == plant_type:
                stack.append((ci - 1, cj))
            else:
                # if no top cell, add the edge to perimeter
                perimeter += 1

            # check left cell
            if cj > 0 and garden[ci][cj - 1] == plant_type:
                stack.append((ci, cj - 1))
            else:
                # if no left cell, add the edge to perimeter
                perimeter += 1

            # check bottom cell
            if ci < m - 1 and garden[ci + 1][cj] == plant_type:
                stack.append((ci + 1, cj))
            else:
                # if no bottom cell, add the edge to perimeter
                perimeter += 1

            # check right cell
            if cj < n - 1 and garden[ci][cj + 1] == plant_type:
                stack.append((ci, cj + 1))
            else:
                # if no right cell, add the edge to perimeter
                perimeter += 1

        return area * perimeter

    # calculate fencing cost for every region
    fencing_cost = 0
    for i in range(m):
        for j in range(n):
            if (i, j) in visited:
                continue
            fencing_cost += calcFenceCostFrom(i, j)

    print(fencing_cost)


def part2():
    visited = set()

    def calcFenceCostFrom(i, j):
        """Calculates the fencing cost of the region starting from coords (i, j)"""
        global garden, m, n

        plant_type = garden[i][j]
        stack = [(i, j)]
        area = 0

        # keep track of all distinct, non-intersecting horizontal and vertical segments
        segments = {
            "H": defaultdict(set),
            "V": defaultdict(set)
        }  # fmt: skip

        while stack:
            ci, cj = stack.pop()
            if (ci, cj) in visited:
                continue
            visited.add((ci, cj))

            # add cell to area
            area += 1

            # check top cell
            if ci > 0 and garden[ci - 1][cj] == plant_type:
                stack.append((ci - 1, cj))
            else:
                # record edge segment
                ei = ci - 0.25  # push out the horizontal segment
                segment_set = segments["H"][ei]
                ej_from, ej_to = cj - 0.5, cj + 0.5  # extend the segment to connect with neighbors
                merge_segments(segment_set, ej_from, ej_to)  # merge with current segment set

            # check left cell
            if cj > 0 and garden[ci][cj - 1] == plant_type:
                stack.append((ci, cj - 1))
            else:
                # record edge segment
                ej = cj - 0.25  # push out the vertical segment
                segment_set = segments["V"][ej]
                ei_from, ei_to = ci - 0.5, ci + 0.5  # extend the segment to connect with neighbors
                merge_segments(segment_set, ei_from, ei_to)  # merge with current segment set

            # check bottom cell
            if ci < m - 1 and garden[ci + 1][cj] == plant_type:
                stack.append((ci + 1, cj))
            else:
                # record edge segment
                ei = ci + 0.25  # push out the horizontal segment
                segment_set = segments["H"][ei]
                ej_from, ej_to = cj - 0.5, cj + 0.5  # extend the segment to connect with neighbors
                merge_segments(segment_set, ej_from, ej_to)  # merge with current segment set

            # check right cell
            if cj < n - 1 and garden[ci][cj + 1] == plant_type:
                stack.append((ci, cj + 1))
            else:
                # record edge segment
                ej = cj + 0.25  # push out the vertical segment
                segment_set = segments["V"][ej]
                ei_from, ei_to = ci - 0.5, ci + 0.5  # extend the segment to connect with neighbors
                merge_segments(segment_set, ei_from, ei_to)  # merge with current segment set

        # number of distinct segments == number of sides
        sides = sum(len(segment_set) for seg_dict in segments.values() for segment_set in seg_dict.values())
        return area * sides

    def merge_segments(segment_set: set, idx_from: int, idx_to: int):
        """Merge segment into existing segment set"""
        # find any overlapping / intersecting segments before and after current
        former_segment, latter_segment = None, None
        for s_from, s_to in segment_set:
            if s_from < idx_from and s_to >= idx_from:
                former_segment = (s_from, s_to)
            if s_to > idx_to and s_from <= idx_to:
                latter_segment = (s_from, s_to)

        if former_segment is None and latter_segment is None:
            # there is no overlapping segment
            segment_set.add((idx_from, idx_to))
        elif former_segment == latter_segment:
            # the overlap segment contains our full segment
            pass
        elif former_segment is None:
            # there is a latter segment only
            segment_set.remove(latter_segment)
            segment_set.add((idx_from, latter_segment[1]))
        elif latter_segment is None:
            # there is a former segment only
            segment_set.remove(former_segment)
            segment_set.add((former_segment[0], idx_to))
        else:
            # both are disconnected segments
            segment_set.remove(former_segment)
            segment_set.remove(latter_segment)
            segment_set.add((former_segment[0], latter_segment[1]))

    fencing_cost = 0
    for i in range(m):
        for j in range(n):
            if (i, j) in visited:
                continue
            fencing_cost += calcFenceCostFrom(i, j)

    print(fencing_cost)


part1()
part2()