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;

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

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

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