Why not search for the Chief Historian near the gardener and his massive farm? There's plenty of food, so The Historians grab something to eat while they search.

You're about to settle near a complex arrangement of garden plots when some Elves ask if you can lend a hand. They'd like to set up fences around each region of garden plots, but they can't figure out how much fence they need to order or how much it will cost. They hand you a map (your puzzle input) of the garden plots.

Visit the website for the full story and puzzle description.

One can sense that the difficulty has ramped up today with a more complex problem involving area and perimeter calculations.

First we determine the connected components (regions) of plants of the same type. This is done by picking a position of the garden and applying a standard flood-fill algorithm to it. The result is a region. As we process each region, we carefully remove all affected positions and then pick an untouched position to repeat the process. In a few iterations, the entire garden is associated with the correct regions. The size of the regions corresponds to the area in question. This logic is implemented in the GetRegions function below.

The second part of the problem, however, is more intriguing: how do we calculate the lengths of the fences? In part 1, this is relatively simple because we just iterate through each region and count the neighboring cells that belong to a different regions. This tells how many fence is needed. Unfortunately, this logic doesn't work for part 2...

I attempted to implement a "walk-around" approach, which involves finding a fence segment and tracing it like a line-following robot while counting the turns. The challenge with this approach is that some regions have holes, that require fences as well and I didnt want to implement hole finding.

Later realized that it is probably more straightforward to collect the fence segments along straight lines scanning the garden from top to bottom an right to left. This is how I solved the problem.

Finally went to reddit and read the hint: the number of segments equal to the number of corners... In other words difference between part 1 and 2 is very small. In part 1 we are building an edge detector which becomes a corner detector in part 2. I changed my implementation to that.

This concludes our day 12. I'll take an extra ⭐ for learning something new again.

namespace AdventOfCode.Y2024.Day12;

using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Linq;
using System.Numerics;

using Region = System.Collections.Generic.HashSet<System.Numerics.Complex>;

[ProblemName("Garden Groups")]
class Solution : Solver {

    Complex Up = Complex.ImaginaryOne;
    Complex Down = -Complex.ImaginaryOne;
    Complex Left = -1;
    Complex Right = 1;

    public object PartOne(string input) => CalculateFencePrice(input, FindEdges);

    public object PartTwo(string input) => CalculateFencePrice(input, FindCorners);

    int CalculateFencePrice(string input, MeasurePerimeter measure){
        var regions = GetRegions(input);
        var res = 0;
        foreach (var region in regions.Values.Distinct()) {
            var perimeter = 0;
            foreach (var pt in region) {
                perimeter += measure(regions, pt);
            }
            res += region.Count() * perimeter;
        }
        return res;
    }    
   
    delegate int MeasurePerimeter(Dictionary<Complex, Region> map, Complex pt);

    int FindEdges(Dictionary<Complex, Region> map, Complex pt) {
        var res = 0;
        var region = map[pt];
        foreach (var du in new[] { Right, Down, Left, Up}) {
            // x.
            if (map.GetValueOrDefault(pt + du) != region) {
                res++;
            }
        }
        return res;
    }

    int FindCorners(Dictionary<Complex, Region> map, Complex pt) {
        var res = 0;
        var region = map[pt];

        // check the 4 corner types
        foreach (var (du, dv) in new[] { (Up, Right), (Right, Down), (Down, Left), (Left, Up) }) {
            //  ..
            //  x. convex corner
            if (map.GetValueOrDefault(pt + du) != region && 
                map.GetValueOrDefault(pt + dv) != region
            ) {
                res++; 
            }

            //  x.
            //  xx concave corner
            if (map.GetValueOrDefault(pt + du) == region && 
                map.GetValueOrDefault(pt + dv) == region &&  
                map.GetValueOrDefault(pt + du + dv) != region
            ) {
                res++;
            }
        }
        return res;
    }

    // Maps the positions of plants in a garden to their corresponding regions, grouping plants 
    // of the same type into contiguous regions.
    Dictionary<Complex, Region> GetRegions(string input) {
        var lines = input.Split("\n");
        var garden = (
            from y in Enumerable.Range(0, lines.Length)
            from x in Enumerable.Range(0, lines[0].Length)
            select new KeyValuePair<Complex, char>(x + y * Down, lines[y][x])
        ).ToDictionary();

        // go over the positions of the garden and use a floodfill to determine the region
        var res = new Dictionary<Complex, Region>();
        var positions = garden.Keys.ToHashSet();
        while (positions.Any()) {
            var pivot = positions.First();
            var region = new Region { pivot };

            var q = new Queue<Complex>();
            q.Enqueue(pivot);

            var plant = garden[pivot];

            while (q.Any()) {
                var point = q.Dequeue();
                res[point] = region;
                positions.Remove(point);
                foreach (var dir in new[] { Up, Down, Left, Right }) {
                    if (!region.Contains(point + dir) && garden.GetValueOrDefault(point + dir) == plant) {
                        region.Add(point + dir);
                        q.Enqueue(point + dir);
                    }
                }
            }
        }
        return res;
    }

}

Please ☆ my repo if you like it!