C#

There is probably a more efficient way of finding the sides, but this way was what came to me.

using System.Diagnostics;
using Common;

namespace Day12;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = Input.ParseInput("sample.txt");
        var programInput = Input.ParseInput("input.txt");

        var (samplePart1, samplePart2) = Solve(sampleInput);
        Console.WriteLine($"Part 1 sample: {samplePart1}");
        Console.WriteLine($"Part 1 input: {samplePart2}");

        var (inputPart1, inputPart2) = Solve(programInput);
        Console.WriteLine($"Part 2 sample: {inputPart1}");
        Console.WriteLine($"Part 2 input: {inputPart2}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static (int part1, int part2) Solve(Input i)
    {
        var retail = 0;
        var bulk = 0;
        var allPlotPoints = new Dictionary<char, HashSet<Point>>();
        foreach (var p in Grid.EnumerateAllPoints(i.Bounds))
        {
            var plant = i.ElementAt(p);

            if (!allPlotPoints.TryGetValue(plant, out var previousPlotPoints))
            {
                previousPlotPoints = new();
                allPlotPoints[plant] = previousPlotPoints;
            }
            else if (previousPlotPoints.Contains(p)) continue;

            var plotPoints = new HashSet<Point>();
            var perimeter = SearchPlot(i, plotPoints, plant, p);
            var area = plotPoints.Count;
            var sides = CountSides(plotPoints);
            retail += area * perimeter;
            bulk += area * sides;

            previousPlotPoints.AddRange(plotPoints);
        }

        return (retail, bulk);
    }

    static int CountSides(HashSet<Point> plot)
    {
        var sides = 0;

        // Track the points we've visited searching for sides
        HashSet<Point> visitedDownRight = new(),
            visitedDownLeft = new(),
            visitedRightDown = new(),
            visitedRightUp = new();

        // Sort the points in the plot from upper-left to lower-right, so we can
        // go through them in reading order
        foreach (var p in plot.OrderBy(p => (p.Row * 10000) + p.Col))
        {
            // Move right while looking up
            sides += GetSideLength(p, plot, visitedRightUp, Direction.Right, Direction.Up) > 0 ? 1 : 0;
            
            // Move right while looking down
            sides += GetSideLength(p, plot, visitedRightDown, Direction.Right, Direction.Down) > 0 ? 1 : 0;
            
            // Move down while looking right
            sides += GetSideLength(p, plot, visitedDownRight, Direction.Down, Direction.Right) > 0 ? 1 : 0;
            
            // Move down while looking left
            sides += GetSideLength(p, plot, visitedDownLeft, Direction.Down, Direction.Left) > 0 ? 1 : 0;
        }

        return sides;
    }

    static int GetSideLength(Point p, HashSet<Point> plotPoints, HashSet<Point> visited, Direction move, Direction look)
    {
        if (!plotPoints.Contains(p)) return 0;
        if (!visited.Add(p)) return 0;
        if (plotPoints.Contains(p.Move(look))) return 0;
        return 1 + GetSideLength(p.Move(move), plotPoints, visited, move, look);
    }

    static int SearchPlot(Input i, HashSet<Point> plotPoints, char plant, Point p)
    {
        if (!plotPoints.Add(p)) return 0;
        return p
            .GetCardinalMoves()
            .Select(move =>
            {
                if (!i.IsInBounds(move) || (i.ElementAt(move) != plant)) return 1;
                return SearchPlot(i, plotPoints, plant, move);
            })
            .Sum();
    }
}

public class Input
{
    public required string[] Map { get; init; }
    
    public Point Bounds => new Point(this.Map.Length, this.Map[0].Length);
    public char ElementAt(Point p) => this.Map[p.Row][p.Col];
    public bool IsInBounds(Point p) => p.IsInBounds(this.Map.Length, this.Map[0].Length);
    
    public static Input ParseInput(string file) => new Input()
    {
        Map = File.ReadAllLines(file),
    };
}

J

Implementing flood fill or something like that would have been smart, so I didn’t do that. Instead I used a sparse-but-still-way-too-big-and-slow block matrix representation, which takes several minutes to compute the region partitions for the real problem. The rest is essentially simple, although counting edges has some picky details. The result is a lot of code though – way more than has been typical up to now.

data_file_name =: '12.data'
grid =: ,. > cutopen fread data_file_name
data =: , grid
'rsize csize' =: $ grid
size =: # data
inbounds =: monad : '(*/ y >: 0 0) * (*/ y < rsize, csize)'
coords =: ($ grid) & #:
uncoords =: ($ grid) & #.
neighbors =: monad : 'uncoords (#~ inbounds"1) (coords y) +"1 (4 2 $ 1 0 0 1 _1 0 0 _1)'
components =: 1 ((i.size) ,. i.size)} 1 $. (size, size); (0 1); 0
NB. fuse (m, n) fuses together the components of linear indices m and n onto the
NB. lesser of the two
fuse =: monad define
   fused_row =. >./ y { components
   NB. 4 $. is a version of 1 I. that works on sparse arrays: it gives us the index array,
   NB. but it's rows of index vectors so we have to transpose to get just the column indices
   fused_indices =. {. |: 4 $. fused_row
   components =: 1 (, fused_indices (< @: ,"0/) fused_indices)} components
)
NB. fuse_all fuses all adjacent pairs of cells according to the grid contents; this makes
NB. a "block diagonal" matrix of 1's where the block index groups are components
fuse_cols =: monad define
   for_r. i. rsize do.
      for_c. i. <: csize do.
         n =. uncoords (r, c)
         pair =. n, n + 1
         if. =/ (pair { data) do. fuse pair end.
      end.
   end.
   components
)
NB. To speed this up we only execute fusion once on each pair of adjacent contiguous groups,
NB. since each row has already had its columns fused.
fuse_rows =: monad define
   for_r. i. <: rsize do.
      cur_cell =. a:
      in_group =. 0
      for_c. i. csize do.
         n =. uncoords (r, c)
         if. cur_cell ~: n { data do.
            cur_cell =. n { data
            in_group =. 0
         end.
         pair =. n, n + csize
         if. =/ (pair { data) do.
            if. in_group = 1 do. continue.
            else.
               fuse pair
               in_group =. 1
            end.
         else. in_group =. 0 end.
      end.
   end.
   components
)
fuse_all =: fuse_rows @: fuse_cols
NB. count_edges n counts the number of fenced edges, which is 4 minus the number of neighbor
NB. cells in the same component
component_neighbors =: monad : '(#~ ((= & (y { data)) @: ({ & data))) neighbors y'
count_edges =: monad : '4 - # component_neighbors y'
NB. components component_index n gives the least cell index in n's component
component_index =: dyad : '<./ {. |: 4 $. y { x'
NB. distinct components gives the list of component indices
distinct_components =: monad : '~. 0 $. y component_index"_ 0 i.size'
NB. components component_cells m gives the cell list of component m
component_cells =: dyad : 'I. 0 $. y { x'"_ 0
NB. components area m gives the area of component m
area =: (# @: component_cells)"_ 0
NB. components perimeter m gives the perimeter of component m
perimeter =: (+/ @: (count_edges"0) @: component_cells)"_ 0
components =: fuse_all components
result1 =: +/ components (area * perimeter) distinct_components components

NB. cell edges are given coordinates as follows: horizontal edges are numbered according to the
NB. cell they are above, so [0..rsize] x [0..csize), and vertical edges are numbered according to
NB. the cell they are left of, so [0..rsize) x [0..csize]. Two adjacent (connected) cell edges
NB. belong to the same component edge if they have a component cell on the same side.
NB. cell_edges m gives the edge coordinates in the schema above of the cell with linear index m,
NB. as a boxed list horizontal_edges;vertical_edges.
cell_edges =: monad define
   'r c' =. coords y
   neighbors =. component_neighbors y
   horiz_edges =. (-. ((y - csize), y + csize) e. neighbors) # 2 2 $ r, c, (>: r), c
   vert_edges =. (-. ((<: y), >: y) e. neighbors) # 2 2 $ r, c, r, >: c
   horiz_edges ; vert_edges
)
NB. cells hconnected r c1 c2 if (r, c1) and (r, c2) are horizontally connected edges
hconnected =: dyad define
   'r c1 c2' =. y
   if. 1 < c2 - c1 do. 0 return. end.
   if. (0 = r) +. rsize = r do. 1 return. end.
   upper_neighbors =. (uncoords"1) 2 2 $ (<: r), c1, (<: r), c2
   lower_neighbors =. (uncoords"1) 2 2 $ r, c1, r, c2
   (*/ upper_neighbors e. x) +. (*/ lower_neighbors e. x)
)
NB. cells vconnected c r1 r2 if (r1, c) and (r2, c) are vertically connected edges
vconnected =: dyad define
   'c r1 r2' =. y
   if. 1 < r2 - r1 do. 0 return. end.
   if. (0 = c) +. csize = c do. 1 return. end.
   left_neighbors =. (uncoords"1) 2 2 $ r1, (<: c), r2, <: c
   right_neighbors =. (uncoords"1) 2 2 $ r1, c, r2, c
   (*/ left_neighbors e. x) +. (*/ right_neighbors e. x)
)
component_edges =: dyad define
   cells =. x component_cells y
   'raw_horiz raw_vert' =. (< @: ;)"1 |: cell_edges"0 cells
   edge_pairs_of_row =. ((> @: {.) (,"0 1) ((2 & (]\)) @: > @: {:))
   horiz_edge_groups =. ({. ;/.. {:) |: raw_horiz
   new_h_edges_per_row =. (-. @: (cells & hconnected)"1 &.>) (< @: edge_pairs_of_row)"1 horiz_edge_groups
   total_h_edges =. (# horiz_edge_groups) + +/ ; new_h_edges_per_row
   vert_edge_groups =. ({: ;/.. {.) |: raw_vert
   new_v_edges_per_row =. (-. @: (cells & vconnected)"1 &.>) (< @: edge_pairs_of_row)"1 vert_edge_groups
   total_v_edges =. (# vert_edge_groups) + +/ ; new_v_edges_per_row
   total_h_edges + total_v_edges
)
result2 =: +/ components (area * (component_edges"_ 0)) distinct_components components

Ended up oversleeping somewhat, so I did the first part on the way to work using flood fills over a global visited set, and now that work’s over I’ve sat down to expand that solution to do corner counting for part two as well.

char[] map = new char[0];
(int X, int Y) size = (0, 0);

public void Input(IEnumerable<string> lines)
{
  map = string.Concat(lines).ToCharArray();
  size = (lines.First().Length, lines.Count());
}

Dictionary<HashSet<(int,int)>,int> areas = new Dictionary<HashSet<(int,int)>,int>();
public void PreCalc()
{
  HashSet<(int, int)> visited = new HashSet<(int, int)>();
  for (int y = 0; y < size.Y; ++y)
    for (int x = 0; x < size.X; ++x)
    {
      var at = (x, y);
      if (visited.Contains(at))
        continue;

      var area = Flood((x, y), visited);
      areas[area.Area] = area.Perim;
    }
}

public void Part1()
{
  int sum = areas.Select(kv => kv.Key.Count * kv.Value).Sum();

  Console.WriteLine($"Fencing total: {sum}");
}
public void Part2()
{
  int sum = areas.Select(kv => kv.Key.Count * countCorners(kv.Key)).Sum();

  Console.WriteLine($"Fencing total: {sum}");
}

readonly (int dX, int dY)[] links = new[] { (1, 0), (0, 1), (-1, 0), (0, -1) };
(HashSet<(int,int)> Area, int Perim) Flood((int X, int Y) from, HashSet<(int X, int Y)> visited)
{
  char at = map[from.Y * size.X + from.X];

  (HashSet<(int,int)> Area, int Perim) ret = (new HashSet<(int,int)>(), 0);
  visited.Add(from);
  ret.Area.Add(from);

  foreach (var link in links)
  {
    (int X, int Y) newAt = (from.X + link.dX, from.Y + link.dY);
    char offset ;
    if (newAt.X < 0 || newAt.X >= size.X || newAt.Y < 0 || newAt.Y >= size.Y)
      offset = '\0';
    else
      offset = map[newAt.Y * size.X + newAt.X];

    if (offset == at)
    {
      if (visited.Contains(newAt))
        continue;

      var nextArea = Flood(newAt, visited);
      ret.Area.UnionWith(nextArea.Area);
      ret.Perim += nextArea.Perim;
    }
    else
    {
      ret.Perim += 1;
    }
  }

  return ret;
}

readonly (int dX, int dY)[] cornerPoints = new[] { (0, 0), (1, 0), (1, 1), (0, 1) };
readonly int[] diagonalValues = new[] { (2 << 0) + (2 << 2), (2 << 1) + (2 << 3) };
int countCorners(HashSet<(int X, int Y)> points)
{
  int corners = 0;
  var bounds = findBounds(points);
  for (int y = bounds.minY - 1; y < bounds.maxY + 1; ++y)
    for (int x = bounds.minX - 1; x < bounds.maxX + 1; ++x)
    {
      var atPoint = cornerPoints.Select(c => points.Contains((x + c.dX, y + c.dY)));
      var before = corners;
      if (atPoint.Where(c => c).Count() % 2 == 1)
        corners++;
      else if (diagonalValues.Contains(atPoint.Select((c, i) => c ? (2 << i) : 0).Sum()))
        corners += 2;
    }

  return corners;
}

(int minX, int minY, int maxX, int maxY) findBounds(HashSet<(int X, int Y)> points)
{
  (int minX, int minY, int maxX, int maxY) ret = (int.MaxValue, int.MaxValue, int.MinValue, int.MinValue);
  foreach (var point in points)
  {
    ret.minX = Math.Min(ret.minX, point.X);
    ret.minY = Math.Min(ret.minY, point.Y);
    ret.maxX = Math.Max(ret.maxX, point.X);
    ret.maxY = Math.Max(ret.maxY, point.Y);
  }

  return ret;
}

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.

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  ← /+/+⧈(⊡:Cs°⋯♭)2_2⌝↘¯1_¯1⌝↘1_1°⊚   # Add border, look for corners in 2x2 windows.

ValidN₄     ← ▽≠@_⬚@_⊡:Data.+N₄¤
FieldCoords ← ⍥(◴⍆⊂▽⊙:=⊢∩(⊡:Data),,⟜(⍆◴∧(⊂ValidN₄)⊙[]))∞¤  # Terrible fill to get a list of coords given a starting point.
Fields      ← ↘1{⍢(:⊙▽:¬∈,,FieldCoords⊢.|>0⧻)}⊙◌↯∞_2°⊡Data # Repeatedly find next fields coords until grid exhausted.

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

Python

Had to rely on an external polygon library for this one. Part 1 could have been easily done without it but part 2 would be diffucult (you can even use the simplify function to count the number of straight edges in internal and external boundaries modulo checking the collinearity of the start and end of the boundary)

import numpy as np
from pathlib import Path
from shapely import box, union, MultiPolygon, Polygon, MultiLineString
cwd = Path(__file__).parent

def parse_input(file_path):
  with file_path.open("r") as fp:
    garden = list(map(list, fp.read().splitlines()))

  return np.array(garden)

def get_polygon(plant, garden):
  coords = list(map(tuple, list(np.argwhere(garden==plant))))
  for indc,coord in enumerate(coords):

    box_next = box(xmin=coord[0], ymin=coord[1], xmax=coord[0]+1,
                   ymax=coord[1]+1)

    if indc==0:
      poly = box_next
    else:
      poly = union(poly, box_next)

  if isinstance(poly, Polygon):
    poly = MultiPolygon([poly])

  return poly

def are_collinear(coords, tol=None):
    coords = np.array(coords, dtype=float)
    coords -= coords[0]
    return np.linalg.matrix_rank(coords, tol=tol)==1

def simplify_boundary(boundary):

  # if the object has internal and external boundaries then split them
  # and recurse
  if isinstance(boundary, MultiLineString):
    coordinates = []
    for b in boundary.geoms:
      coordinates.append(simplify_boundary(b))
    return list(np.concat(coordinates, axis=0))

  simple_boundary = boundary.simplify(0)
  coords = [np.array(x) for x in list(simple_boundary.coords)[:-1]]
  resolved = False

  while not resolved:

    end_side=\
    np.concat([x[:,None] for x in [coords[-1], coords[0], coords[1]]], axis=1)

    if  are_collinear(end_side.T):
      coords = coords[1:]
    else:
      resolved = True

  return coords

def solve_problem(file_name):

  garden = parse_input(Path(cwd, file_name))
  unique_plants = set(garden.flatten())
  total_price = 0
  discounted_total_price = 0

  for plant in unique_plants:

    polygon = get_polygon(plant, garden)

    for geom in polygon.geoms:
      coordinates = simplify_boundary(geom.boundary)
      total_price += geom.area*geom.length
      discounted_total_price += geom.area*len(coordinates)

  return int(total_price), int(discounted_total_price)

Dart

Filling to find regions was easy. Counting areas was easy. Counting fences was okay. Counting sides caused me a lot of frustration as I tried and rejected a number of approaches, eventually arriving at a reasonably simple corner-counting approach. None of this was helped by all the examples lacking at least two important layouts, causing today to be the first day that I ran out of hints for wrong answers :-(.

(corners is where the magic happens)

import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';

const List<Point> n4 = [Point(0, 1), Point(0, -1), Point(1, 0), Point(-1, 0)];
List<Point> n8 = n4 + [Point(1, 1), Point(1, -1), Point(-1, 1), Point(-1, -1)];
const List<Point> c4 = [Point(0, 0), Point(0, 1), Point(1, 0), Point(1, 1)];

(Map<Point, String>, Map<Point, List<Point>>) parse(ls) {
  var nodes = {
    for (var y in 0.to(ls.length))
      for (var x in 0.to(ls.first.length)) Point<num>(x, y): ls[y][x] as String
  };
  var nexts = Map.fromEntries(nodes.keys.map((n) => MapEntry(
      n,
      n4
          .map((d) => n + d)
          .where((d) => (nodes[d] ?? '') == nodes[n]!)
          .toList())));
  return (nodes, nexts);
}

(int, Set<Point>) survey(
    Point here, String target, Map<Point<num>, List<Point>> nexts,
    [Set sofar = const {}]) {
  seen.add(here);
  var fences = 4 - nexts[here]!.length;
  var area = {here};
  for (var f in nexts[here]!.where((e) => !seen.contains(e))) {
    var (fs, a) = survey(f, target, nexts, sofar.toSet()..add(f));
    fences += fs;
    area.addAll(a);
  }
  return (fences, area);
}

late Set<Point> seen;
List<(int, Set<Point<num>>)> costs(List<String> lines) {
  seen = {};
  var ret = <(int, Set<Point<num>>)>[];
  var (nodes, nexts) = parse(lines);
  var toVisit = nodes.keys.toSet();
  while (toVisit.isNotEmpty) {
    var here = toVisit.first;
    toVisit.remove(here);
    ret.add(survey(here, nodes[here]!, nexts));
    toVisit.removeAll(seen);
  }
  return ret;
}

Function eq = const ListEquality().equals;
int corners(Set<Point> points) {
  var border = points.map((e) => n8.map((n) => n + e)).flattenedToSet
    ..addAll(points);
  // A corner is where a 2x2 grid contains one/three in-shape points, or
  // two diagonally-opposite cells
  var corners = 0;
  for (var cell in border) {
    var count = c4.map((e) => points.contains(e + cell)).toList();
    if (count.count((e) => e) % 2 == 1) {
      corners += 1;
    } else {
      if (eq(count, [true, false, false, true]) ||
          eq(count, [false, true, true, false])) {
        corners += 2;
      }
    }
  }
  return corners;
}

part1(lines) => costs(lines).map((e) => e.first * e.last.length).sum;
part2(lines) => costs(lines).map((e) => corners(e.last) * e.last.length).sum;

C#

public class Day12 : Solver
{
  private string[] data;
  private int width, height;
  private Dictionary<int, long> perimeters = [];
  private Dictionary<int, long> areas = [];
  private Dictionary<int, long> sides = [];
  private int region_count;

  public void Presolve(string input) {
    data = input.Trim().Split("\n").ToArray();
    height = data.Length;
    width = data[0].Length;
    var graph_cc = MakeGraph(false);
    var cc = new ConnectedComponentsAlgorithm<Point, PointEdge>(graph_cc);
    cc.Compute();
    var graph_all = MakeGraph(true);
    Dictionary<(int Component, int Y), List<int>> x_sides = [];
    Dictionary<(int Component, int X), List<int>> y_sides = [];
    var search = new UndirectedBreadthFirstSearchAlgorithm<Point, PointEdge>(graph_all);
    search.SetRootVertex((0, 0));
    search.FinishVertex += vertex => {
      if (IsWithinBounds(vertex.Item1, vertex.Item2)) {
        int component = cc.Components[vertex];
        areas.TryAdd(component, 0L);
        areas[component] += 1;
      }
    };
    search.ExamineEdge += edge => {
      var (si, ti) = (IsWithinBounds(edge.Source), IsWithinBounds(edge.Target));
      bool border = si != ti || cc.Components[edge.Source] != cc.Components[edge.Target];
      if (si && border) {
        int component = cc.Components[edge.Source];
        perimeters.TryAdd(component, 0L);
        perimeters[component] += 1;
        if (edge.Source.Item1 == edge.Target.Item1) {
          int y = Math.Min(edge.Source.Item2, edge.Target.Item2);
          x_sides.TryAdd((component, y), []);
          x_sides[(component, y)].Add(edge.Source.Item2 > edge.Target.Item2 ? edge.Source.Item1 : -edge.Source.Item1 - 5);
        } else {
          int x = Math.Min(edge.Source.Item1, edge.Target.Item1);
          y_sides.TryAdd((component, x), []);
          y_sides[(component, x)].Add(edge.Source.Item1 > edge.Target.Item1 ? edge.Source.Item2 : -edge.Source.Item2 - 5);
        }
      }
    };
    search.Compute();
    region_count = cc.ComponentCount;
    foreach (var side_projection in x_sides) {
      side_projection.Value.Sort();
      sides.TryAdd(side_projection.Key.Component, 0);
      int last_x = int.MinValue;
      foreach (var x in side_projection.Value) {
        if (x != (last_x + 1)) sides[side_projection.Key.Component] += 1;
        last_x = x;
      }
    }
    foreach (var side_projection in y_sides) {
      side_projection.Value.Sort();
      sides.TryAdd(side_projection.Key.Component, 0);
      int last_y = int.MinValue;
      foreach (var y in side_projection.Value) {
        if (y != (last_y + 1)) sides[side_projection.Key.Component] += 1;
        last_y = y;
      }
    }
    foreach (var component in Enumerable.Range(0, region_count)) {
      if (!areas.ContainsKey(component)) continue;
    }
  }

  public string SolveFirst() =>
    Enumerable.Range(0, region_count)
      .Where(component => areas.ContainsKey(component))
      .Select(component => areas[component] * perimeters[component]).Sum().ToString();

  public string SolveSecond() =>
    Enumerable.Range(0, region_count)
      .Where(component => areas.ContainsKey(component))
      .Select(component => areas[component] * sides[component]).Sum().ToString();

  private record struct PointEdge(Point Source, Point Target): IEdge<Point>;

  private IUndirectedGraph<Point, PointEdge> MakeGraph(bool with_edges_between_plots)=>
    new DelegateUndirectedGraph<Point, PointEdge>(GetVertices(), with_edges_between_plots? GetAllEdges : GetEdgesWithoutBorders, false);

  private bool IsWithinBounds(int x, int y) => x >= 0 && x < width && y >= 0 && y < height;
  private bool IsWithinBounds(Point p) => IsWithinBounds(p.Item1, p.Item2);

  private readonly (int, int)[] directions = [(-1, 0), (0, -1), (1, 0), (0, 1)];

  private bool GetEdgesWithoutBorders(Point arg, out IEnumerable<PointEdge> result) {
    List<PointEdge> result_list = [];
    var (x, y) = arg;
    bool inside = IsWithinBounds(x, y);
    foreach (var (dx, dy) in directions) {
      var (ox, oy) = (x + dx, y + dy);
      if (!inside || !IsWithinBounds(ox, oy)) continue;
      if (data[y][x] == data[oy][ox]) result_list.Add(new(arg, (ox, oy)));
    }
    result = result_list;
    return true;
  }

  private bool GetAllEdges(Point arg, out IEnumerable<PointEdge> result) {
    List<PointEdge> result_list = [];
    var (x, y) = arg;
    foreach (var (dx, dy) in directions) {
      var (ox, oy) = (x + dx, y + dy);
      if (ox >= -1 && ox <= width && oy >= -1 && oy <= height) result_list.Add(new(arg, (ox, oy)));
    }
    result = result_list;
    return true;
  }

  private IEnumerable<(int, int)> GetVertices() => Enumerable.Range(-1, width + 2).SelectMany(x => Enumerable.Range(-1, height + 2).Select(y => (x, y)));
}

Haskell

This was a bit of a fiddly one. There’s probably scope for golfing it down some more, but I’ve had enough for today :3

import Control.Arrow
import Data.List
import Data.Map (Map)
import Data.Map qualified as Map
import Data.Set (Set)
import Data.Set qualified as Set

readInput :: String -> Map (Int, Int) Char
readInput s = Map.fromList [((i, j), c) | (i, l) <- zip [0 ..] (lines s), (j, c) <- zip [0 ..] l]

(i1, j1) .+. (i2, j2) = (i1 + i2, j1 + j2)

(i1, j1) .-. (i2, j2) = (i1 - i2, j1 - j2)

directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] :: [(Int, Int)]

edges = zip ps (drop 1 ps) :: [((Int, Int), (Int, Int))]
  where
    ps = [(0, 1), (1, 1), (1, 0), (0, 0), (0, 1)]

regions :: Map (Int, Int) Char -> [Set (Int, Int)]
regions = unfoldr (fmap (uncurry removeRegion) . Map.minViewWithKey)
  where
    removeRegion (p, t) = go Set.empty (Set.singleton p)
      where
        go r ps plots
          | Set.null ps = (r, plots)
          | otherwise =
              let ps' =
                    Set.filter (\p -> plots Map.!? p == Just t) $
                      Set.fromList (concatMap adjacent ps) Set.\\ ps
               in go (Set.union r ps) ps' (Map.withoutKeys plots ps')
        adjacent = (`map` directions) . (.+.)

boundary :: Set (Int, Int) -> Set ((Int, Int), (Int, Int))
boundary region =
  Set.fromList $
    [ (p .+. e1, p .+. e2)
      | p <- Set.elems region,
        (d, (e1, e2)) <- zip directions edges,
        p .+. d `Set.notMember` region
    ]

perimeter :: Set (Int, Int) -> [[(Int, Int)]]
perimeter = unfoldr (fmap (uncurry removeChain) . Set.minView) . boundary
  where
    removeChain e@(e1, e2) es = first (e1 :) $ go [] e es
    go c e@(e1, e2) es =
      case find ((== e2) . fst) es of
        Nothing -> (e1 : c, es)
        Just e' -> go (e1 : c) e' (Set.delete e' es)

countSides :: [(Int, Int)] -> Int
countSides ps = length $ group $ zipWith (.-.) (drop 1 ps) ps

main = do
  input <- readInput <$> readFile "input12"
  let rs = map (Set.size &&& perimeter) $ regions input
  print . sum $ map (\(a, p) -> a * sum (map (subtract 1 . length) p)) rs
  print . sum $ map (\(a, p) -> a * sum (map countSides p)) rs

Haskell

Detecting regions is a floodfill. For Part 2, I select all adjacent tiles that are not part of a region and group them by the direction relative to the closest region tile, then group adjacent tiles with the same direction again and count.

Edit:

Takes 0.06s

import Control.Arrow

import Data.Array.Unboxed (UArray)
import Data.Set (Set)
import Data.Map (Map)

import qualified Data.List as List
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.Array.Unboxed as UArray

parse :: String -> UArray (Int, Int) Char
parse s = UArray.listArray ((1, 1), (n, m)) . filter (/= '\n') $ s
        where
                n = takeWhile (/= '\n') >>> length $ s
                m = filter (== '\n') >>> length >>> pred $ s

neighborCoordinates (p1, p2) = [(p1-1, p2), (p1, p2-1), (p1, p2+1), (p1+1, p2)]

allNeighbors p a = neighborCoordinates
        >>> filter (UArray.inRange (UArray.bounds a))
        $ p

regionNeighbors p a = allNeighbors p
        >>> filter ((a UArray.!) >>> (== pTile))
        $ a
        where
                pTile = a UArray.! p

floodArea :: Set (Int, Int) -> Set (Int, Int) -> UArray (Int, Int) Char -> Set (Int, Int)
floodArea e o a
        | Set.null o = e
        | otherwise  = floodArea e' o' a
        where
                e' = Set.union e o
                o' = Set.fold (Set.union . Set.fromDistinctAscList .  (filter (`Set.notMember` e')) . (flip regionNeighbors a)) Set.empty o

findRegions garden = findRegions' (Set.fromList . UArray.indices $ garden) garden

findRegions' remainingIndices garden
        | Set.null remainingIndices = []
        | otherwise = removedIndices : findRegions' remainingIndices' garden
        where
                removedIndices = floodArea Set.empty (Set.singleton . Set.findMin $ remainingIndices) garden
                remainingIndices' = Set.difference remainingIndices removedIndices

perimeter region = Set.fold ((+) . length . filter (`Set.notMember` region) . neighborCoordinates) 0 region

part1 rs = map (Set.size &&& perimeter)
        >>> map (uncurry (*))
        >>> sum
        $ rs

turnLeft ( 0, 1) = (-1, 0) -- right
turnLeft ( 0,-1) = ( 1, 0) -- left
turnLeft ( 1, 0) = ( 0, 1) -- down
turnLeft (-1, 0) = ( 0,-1) -- up

turnRight = turnLeft . turnLeft . turnLeft

move (py, px) (dy, dx) = (py + dy, px + dx)

tupleDelta (y1, x1) (y2, x2) = (y1-y2, x1-x2)

isRegionInner region p = all (`Set.member` region) (neighborCoordinates p)

groupEdges d ps
        | Set.null ps = []
        | otherwise   = collectedEdge : groupEdges d ps'
        where
                ps' = Set.difference ps collectedEdge
                collectedEdge = Set.union leftPoints rightPoints
                leftPoints = iterate (move dl)
                        >>> takeWhile (`Set.member` ps)
                        >>> Set.fromList
                        $ currentPoint
                rightPoints = iterate (move dr)
                        >>> takeWhile (`Set.member` ps)
                        >>> Set.fromList
                        $ currentPoint
                currentPoint = Set.findMin ps
                dr = turnRight d
                dl = turnLeft  d

linearPerimeter region = Map.foldr ((+) . length) 0 $ groupedEdges
        where 
                edgeTiles = Set.filter (not . isRegionInner region) region
                regionNeighbors = List.concatMap (\ p -> map (p,). filter (`Set.notMember` region) . neighborCoordinates $ p) . Set.toList $ region
                groupedNeighbors = List.map (uncurry tupleDelta &&& Set.singleton . snd)
                        >>> Map.fromListWith (Set.union)
                        $ regionNeighbors
                groupedEdges = Map.mapWithKey groupEdges
                        $ groupedNeighbors

part2 rs = map (Set.size &&& linearPerimeter)
        >>> map (uncurry (*))
        >>> sum
        $ rs

main = getContents
        >>= print
        . (part1 &&& part2)
        . findRegions
        . parse

Nim

Runtime: 7ms 3.18 ms

Part 1: I use flood fill to count all grouped plants and keep track of each border I see.
Part 2: I use an algorithm similar to “merge overlapping ranges” to count spans of borders (border orientation matters) in each row and column, for each group. Resulting code (hidden under spoiler) is a little messy and not very DRY (it’s completely soaked).

Edit: refactored solution, removed some very stupid code.

proc groupSpans(borders: seq[(Vec2, Dir)]): int =
  ## returns number of continuous groups of cells with same Direction
  ## and on the same row or column
  var borders = borders
  var horiz = borders.filterIt(it[1] in {U, D})
  while horiz.len > 0:
    var sameYandDir = @[horiz.pop()]
    var curY = sameYandDir[^1][0].y
    var curDir = sameYandDir[^1][1]
    for i in countDown(horiz.high, 0):
      if horiz[i][0].y == curY and horiz[i][1] == curDir:
        sameYandDir.add horiz[i]
        horiz.del i
    sameYandDir.sort((a,b)=>cmp(a[0].x, b[0].x), Descending)

    var cnt = 1
    for i, (p,d) in sameYandDir.toOpenArray(1, sameYandDir.high):
      if sameYandDir[i][0].x - p.x  != 1: inc cnt
    result += cnt

  var vert = borders.filterIt(it[1] in {L, R})
  while vert.len > 0:
    var sameXandDir = @[vert.pop()]
    var curX = sameXandDir[^1][0].x
    var curDir = sameXandDir[^1][1]
    for i in countDown(vert.high, 0):
      if vert[i][0].x == curX and vert[i][1] == curDir:
        sameXandDir.add vert[i]
        vert.del i
    sameXandDir.sort((a,b)=>cmp(a[0].y, b[0].y), Descending)

    var cnt = 1
    for i, (p,d) in sameXandDir.toOpenArray(1, sameXandDir.high):
      if sameXandDir[i][0].y - p.y  != 1: inc cnt
    result += cnt

type
  Dir = enum L,R,U,D
  Vec2 = tuple[x,y: int]
  GroupData = object
    plantCount: int
    borders: seq[(Vec2, Dir)]

const Adjacent: array[4, Vec2] = [(-1,0),(1,0),(0,-1),(0,1)]

proc solve(input: string): AOCSolution[int, int] =
  let grid = input.splitLines()
  var visited = newSeqWith(grid.len, newSeq[bool](grid[0].len))
  var groups: seq[GroupData]

  proc floodFill(pos: Vec2, plant: char, groupId: int) =
    visited[pos.y][pos.x] = true
    inc groups[groupId].plantCount
    for di, d in Adjacent:
      let pd: Vec2 = (pos.x+d.x, pos.y+d.y)
      if pd.x < 0 or pd.y < 0 or pd.x > grid[0].high or pd.y > grid.high or
        grid[pd.y][pd.x] != plant:
        groups[groupId].borders.add (pd, Dir(di))
        continue
      if visited[pd.y][pd.x]: continue
      floodFill(pd, plant, groupId)

  for y in 0..grid.high:
    for x in 0..grid[0].high:
      if visited[y][x]: continue
      groups.add GroupData()
      floodFill((x,y), grid[y][x], groups.high)

  for gid, group in groups:
    result.part1 += group.plantCount * group.borders.len
    result.part2 += group.plantCount * group.borders.groupSpans()

Codeberg repo