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

I know I’m late, but it’s still fun and I’m sure no-one will see this.

Part 2 took me way too long to get right. I was initially only returning the relative point to which a plot needed a fence. I ran into issues of knowing if it was a valid fence or not by my method of counting (later). I eventually went with returning a tuple of the plot and an enum flag of the sides that it has fences on.

For counting I grouped the points by one axis then sorted on the other and counted the number of times the transition between two wasn’t contiguous.

It could by done in parallel, but the original traversal would need de-duping, which I didn’t feel like doing. After that things are done on a region basis, which could be parallel.

I also can’t help but notice mine is by far the longest ( > . < )

F#

type Plant = char
type Plot = Plant * Point2I
type Region = Plot list

let area region = List.length region

let perimeter (region:Region) (farm:Grid<Plant>) =
    (0, region)
    ||> List.fold (fun sum plot ->
        movements4 (snd plot) farm
        |> List.fold (fun acc po ->
            acc + match po with
                  | ValueNone -> 1
                  | ValueSome pother ->
                      get pother farm
                      |> fun x ->
                          match x with
                          | ValueSome v when v <> fst plot -> 1
                          | _ -> 0
            ) 0
        |> (fun x -> x + sum)
        )

let movements (plot:Plot) g (visited:HashSet<Point2I>) =
    let plant, point = plot
    movements4 point g
    |> List.choosev (fun px ->
        let vx = get px g |> ifNoneFail "couldn't get point"
        struct(px,vx))
    |> List.filter (fun plotx ->
        let struct(px, vx) = plotx
        vx = plant && not (visited.Contains px))

// visited is needed because I'm using similar logic to the trails, but no stopping point, so I
// need to make sure that it doesn't retrace itself
let rec traverse grid plot (visited:HashSet<Point2I>) =
    let plant, point = plot
    if visited.Contains(point) then []
    else
        visited.Add(point) |> ignore
        let path =
            movements plot grid visited
            |> List.filter (fun struct(newPoint, newPlant) -> newPlant = plant && visited.Contains(newPoint) |> not )
            |> List.map(fun struct(newPoint, newPlant) -> traverse grid (newPlant, newPoint) visited)
            |> List.concat
            |> List.distinct
        plot :: path

/// Returns the list of plots walked and a new grid with the traversed plots set to '.'
let walk (plot:Plot) (farm:Grid<Plant>) : Region * Grid<Plant> =
    let foundMovements = HashSet()
    let region:Region = traverse farm plot foundMovements
    let updatedGrid =
        let arr = Array2D.copy farm
        for _, p in region do
            set p arr '.' |> ignore
        arr
    (region, updatedGrid)
    
let rec findRegions (farm:Grid<Plant>) : Region list=
    farm
    |> List.unfold (fun arr ->
        match (findFirst (fun struct(_,_,v) -> v <> '.' )) arr with
        | Some value ->
            let struct(x,y,v) = value
            let point = {X = x; Y = y}
            let plot : Plot = (v, point)
            let region, newFarm = walk plot arr
            Some (region, newFarm)
        | None -> None
    )
    
let part1 input =
    (readGrid2D input (fun _ c -> c))
    |> fun grid ->
        findRegions grid
        |> List.sumBy (fun region ->
            let a = area region
            let p = perimeter region grid
            a * p)

// Part 2 ---------------------------------------------
[<Flags>]
type Side = None = 0 | Top = 1 | Right = 2| Left = 4 | Bottom = 8
type PlotWithFence = Plot * Side 

type SideAndNextPoint = Side * Point2I

// I couldn't use my original movement function because it filters out off-grid positions, so I modified it here
let getSides plot grid =
    let toPlot (side:Side) (voption:Point2I voption) =
        match voption with | ValueNone -> None, side | ValueSome point -> (Some point, side)
    [
        l (snd plot) |> toPlot Side.Left
        r (snd plot) grid |> toPlot Side.Right
        u (snd plot) |> toPlot Side.Top
        d (snd plot) grid |> toPlot Side.Bottom
    ]


let rec findEdges grid (plot:Plot) (visited:HashSet<Point2I>) =
    
    // this attempt that works is to attach the side information to each point
    // I didn't see a great way to use the existing movements function, so I copied it and added a mapping
    // so that I know in what direction the movement options are
    let sidesWithFence = getSides plot grid

    let plant, point = plot
    if visited.Add(point) |> not then Side.None
    else
        // use the movements to find edges
        let edges = 
            sidesWithFence
            |> List.fold (fun sides next ->
                match next with
                | None, side ->  sides ||| side
                | Some point, side when (get point grid >>= fun v -> v <> plant) |> ifNone false -> sides ||| side
                | _ -> sides
            ) Side.None
            
        edges

let getSideCount2 (plotFences:(Point2I * Side) list) =
    // ok, now I have information on each SIDE that a fence is one... omg I suck at this.
    // I'll try to do the whole compare horizontally and vertically thing again, but this time
    // within each I'll have to check the top and bottom, or I'll iterate it twice
    
    let getX (pf:Point2I * Side) : int = (fst pf) |> _.X
    let getY (pf:Point2I * Side) : int = (fst pf) |> _.Y
    
    let countContiguous side group sort =
        plotFences
        |> Seq.filter (fun pf -> (snd pf) &&& side = side)
        |> Seq.groupBy group 
        |> Seq.map(fun (key, g) -> g |> Seq.sortBy sort)
        // |> Array.ofSeq // debugging code
        |> Seq.sumBy(fun grouping ->
            let total =
                grouping
                |> Seq.splitByComparison (fun last current -> 
// splitByComparison is an implementation I took from ChatGPT for a function that I commonly use in C# as part of the MoreLinq library that does the same thing. Here, I'm splitting whenever there is a difference. 
// in hindsight, it probably could have been a window
                    let l = sort last 
                    let r = sort current
                    l <> (r - 1)
                )
                |> Seq.length
            total)
    
    let topCounts = countContiguous Side.Top getY getX
    let bottomCounts = countContiguous Side.Bottom getY getX
    let leftCounts = countContiguous Side.Left getX getY
    let rightCounts = countContiguous Side.Right getX getY
    
    topCounts + bottomCounts + leftCounts + rightCounts


let part2 input =
    (readGrid2D input (fun _ c -> c))
    |> fun grid ->
        findRegions grid
        // |> List.take 1
        |> List.sumBy(fun region ->
            let (plotCount, edgecount) =
                let visited = HashSet()
                let regionCounts =
                    region
                    |> List.map(fun p -> (snd p), findEdges grid p visited)
                    |> getSideCount2
                (visited.Count, regionCounts)
            
            let area = plotCount
            area * edgecount
            )

Uiua

Takes about 3 seconds to solve both parts for live data, caused primarily by my terrible fill function in FieldCoords which repeatedly refills and dedups already discovered cells. I promised myself when I wrote it that I would revisit it, but I really can’t be bothered right now. Sorry Kai.

LATE EDIT: Thanks to Quant for the inspiration to revisit this. With his code snippet and the realisation that I should normalise all fields to remove wasted space, runtime is now down to 55ms.

Data ← ⊜∘⊸≠@\n "AAAA\nBBCD\nBBCC\nEEEC"
N₄     ← [¯1_0 1_0 0_¯1 0_1]               # Four orthogonal neighbours.
Fences ← /+/+=0≡(⬚0⊡+N₄¤)⊙¤⊚.°⊚            # Fences for a field, by looking for edges.
Cs     ← [0 1 1 0 1 0 2 1 1 2 0 1 0 1 1 0] # Number of corners keyed by bitarray of 2x2 grid.
Sides  ← /+♭⬚0⧈(⊡:Cs°⋯♭)2_2°⊚              # Add border, look for corners in 2x2 windows.

# Use `classify` to find fields, then normalise to 0_0.
Fields ← ≡⍚(-¤⊸/↧)⊜□:⇡△.+1⍜♭⊛Data # Thanks to Quant!

/+×≡◇⊃⧻Fences Fields
/+×≡◇⊃⧻Sides Fields

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()
    }
}