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

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

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

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