Day 12: Garden Groups
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
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 :DRun 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
Uiua
Takes about 3 seconds to solve both parts for live data, caused primarily by my terrible fill function inFieldCoords
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
I found multidimensional markers for partition to work really well for finding the fields:
Areas ← ⊜□:⇡△.+1⍜♭⊛
It just groups the other array’s contents according to adjacent markers, horizontally and vertically. Took me quite a bit to figure out what’s actually happening in the example in the documentation ^^’Ooh, interesting, I’ll have to give that a try. Thanks!
(edit) Wow, that replaced my three lines of overly complex code without a hitch.
classify
is an operator I never really got the point of before. Beautiful.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. Fields ← ⊜□:⇡△.+1⍜♭⊛Data /+×≡◇⊃⧻Fences Fields /+×≡◇⊃⧻Sides Fields
Nice :D
How’s the speed now?1.8s now. 99% of that in
Sides
. I’ve just had an idea though…maybe too late for today though!edit: prepending
≡⍚(-¤⊸/↧)
toFields
spared me from manipulating hundreds of irrelevant 0’s, so time is very good now at 55ms.Damn that’s a lot time saved. I love how unassuming the addition looks for how great an effect it has
It was a real D’oh! moment when I visualised the data I was generating and saw all the zeros stretching across the page.
C
No big trouble today, just a bit of careful debugging of my part 2 logic for which I was greatly helped by some Redditor’s testcase 🙏
Happy to have gotten it all in the single flood fill function without any extra passes.
Code
#include "common.h" #define GZ 144 static char g[GZ][GZ]; static char seen[GZ][GZ]; static void count(char c, int x, int y, int *area, int *perim, int *sides) { if (g[y][x] != c) { (*perim)++; return; } if (seen[y][x]) return; *area += 1; seen[y][x] = 1; /* count start of top/left edges, end of bottom/right edges */ *sides += g[y-1][x]!=c && ((g[y-1][x-1]==c) || (g[y][x-1]!=c)); *sides += g[y+1][x]!=c && ((g[y+1][x+1]==c) || (g[y][x+1]!=c)); *sides += g[y][x-1]!=c && ((g[y-1][x-1]==c) || (g[y-1][x]!=c)); *sides += g[y][x+1]!=c && ((g[y+1][x+1]==c) || (g[y+1][x]!=c)); count(c, x, y-1, area, perim, sides); count(c, x, y+1, area, perim, sides); count(c, x-1, y, area, perim, sides); count(c, x+1, y, area, perim, sides); } int main(int argc, char **argv) { int p1=0,p2=0, x,y, area, perim, sides; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (y=1; fgets(g[y]+1, GZ-2, stdin); y++) assert(y+1 < GZ); for (y=1; y<GZ-1; y++) for (x=1; x<GZ-1; x++) if (isalpha(g[y][x]) && !seen[y][x]) { area = perim = sides = 0; count(g[y][x], x, y, &area, &perim, &sides); p1 += area * perim; p2 += area * sides; } printf("12: %d %d\n", p1, p2); }
Clean and concise. Admirable!
Woah! That solution is a work of art!
Nim
Runtime:
7ms3.18 msPart 1: I use flood fill to count all grouped plants and keep track of each border I see.
Part 2: I use an algorithmsimilar 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()
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()
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)70 or so lines, half a second to run, so that's fine for today.
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
Solution
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
Thank you for showing the floodfill-algorithm using explored/open sets, mine was hellish inefficiently, reminds me of A*.
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() } }
Counting the number of corners was a very useful hint for part 2. I had the most trouble with detecting the double corners, i.e. like in the example where the two B fields touch diagonally:
AAAAAA AAABBA AAABBA ABBAAA ABBAAA AAAAAA
Still, I would’ve taken a lot longer and probably made really-bad-performance-code without reading this :D
Rust
Areas are found by flooding, in the meantime whenever the adjacent plot would be outside the region (or out of bounds) the edge (inside plot, outside plot) is saved in a perimeter list. Part 1 takes just the size of that list, in part 2 we remove fence parts and all entries directly next to it on both sides.
Solution
use std::collections::{HashSet, VecDeque}; use euclid::{default::*, point2, vec2}; type Fences = HashSet<(Point2D<i32>, Point2D<i32>)>; const DIRS: [Vector2D<i32>; 4] = [vec2(0, -1), vec2(1, 0), vec2(0, 1), vec2(-1, 0)]; fn parse(input: &str) -> Vec<&[u8]> { input.lines().map(|l| l.as_bytes()).collect() } fn price(field: &[&[u8]], start: (usize, usize), visited: &mut [Vec<bool>]) -> (u32, Fences) { let crop = field[start.1][start.0]; let width = field[0].len(); let height = field.len(); let mut area_visited = vec![vec![false; width]; height]; let mut area = 0; let mut fences: Fences = HashSet::new(); area_visited[start.1][start.0] = true; visited[start.1][start.0] = true; let start = point2(start.0 as i32, start.1 as i32); let bounds = Rect::new(Point2D::origin(), Size2D::new(width, height).to_i32()); let mut frontier = VecDeque::from([start]); while let Some(p) = frontier.pop_front() { area += 1; for dir in DIRS { let next = p + dir; if bounds.contains(next) { let next_u = next.to_usize(); if area_visited[next_u.y][next_u.x] { continue; } if field[next_u.y][next_u.x] == crop { visited[next_u.y][next_u.x] = true; area_visited[next_u.y][next_u.x] = true; frontier.push_back(next); continue; } } fences.insert((p, next)); } } (area, fences) } fn part1(input: String) { let field = parse(&input); let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![false; width]; height]; let mut total_price = 0; for y in 0..height { for x in 0..width { if !visited[y][x] { let (area, fences) = price(&field, (x, y), &mut visited); total_price += area * fences.len() as u32; } } } println!("{total_price}"); } fn count_perimeter(mut fences: Fences) -> u32 { let list: Vec<_> = fences.iter().copied().collect(); let mut perimeter = 0; for (v, w) in list { if fences.contains(&(v, w)) { perimeter += 1; let dir = w - v; let orth = dir.yx(); let mut next = v + orth; while fences.remove(&(next, next + dir)) { next += orth; } let mut next = v - orth; while fences.remove(&(next, next + dir)) { next -= orth; } } } perimeter } fn part2(input: String) { let field = parse(&input); let width = field[0].len(); let height = field.len(); let mut visited = vec![vec![false; width]; height]; let mut total_price = 0; for y in 0..height { for x in 0..width { if !visited[y][x] { let (area, fences) = price(&field, (x, y), &mut visited); total_price += area * count_perimeter(fences); } } } println!("{total_price}"); } util::aoc_main!();
Also on github
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
Reveal Code
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
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)
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.
C#
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; }
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
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), }; }
What is the
Point
type? I’m surprised that you can’t just lexicographically sort instead ofplot.OrderBy(p => (p.Row * 10000) + p.Col)
.It’s a simple record type I use for (x,y) coordinate problems:
record struct Point(int X, int Y);
It’s defined in a separate project containing things I use in multiple problems.
Maybe I could have done it that way, but this was the first thing I thought of, and it worked :)
Python
Part 1: Simple DFS counting up the cells and exposed edges
Part 2: Still DFS, however I chose to keep track of all segments of the area, merging them if two segments connected. In the end, number of non-overlapping, non-intersecting segments is equal to number of sides. Not the most efficient solution, but it works.
import os from collections import defaultdict # paths here = os.path.dirname(os.path.abspath(__file__)) filepath = os.path.join(here, "input.txt") # read input with open(filepath, mode="r", encoding="utf8") as f: data = f.read() # setup input vars garden = data.splitlines() m, n = len(garden), len(garden[0]) def part1(): visited = set() def calcFenceCostFrom(i, j): """Calculates the fencing cost of the region starting from coords (i, j)""" global garden, m, n plant_type = garden[i][j] stack = [(i, j)] area, perimeter = 0, 0 while stack: ci, cj = stack.pop() if (ci, cj) in visited: continue visited.add((ci, cj)) # add cell to area area += 1 # check top cell if ci > 0 and garden[ci - 1][cj] == plant_type: stack.append((ci - 1, cj)) else: # if no top cell, add the edge to perimeter perimeter += 1 # check left cell if cj > 0 and garden[ci][cj - 1] == plant_type: stack.append((ci, cj - 1)) else: # if no left cell, add the edge to perimeter perimeter += 1 # check bottom cell if ci < m - 1 and garden[ci + 1][cj] == plant_type: stack.append((ci + 1, cj)) else: # if no bottom cell, add the edge to perimeter perimeter += 1 # check right cell if cj < n - 1 and garden[ci][cj + 1] == plant_type: stack.append((ci, cj + 1)) else: # if no right cell, add the edge to perimeter perimeter += 1 return area * perimeter # calculate fencing cost for every region fencing_cost = 0 for i in range(m): for j in range(n): if (i, j) in visited: continue fencing_cost += calcFenceCostFrom(i, j) print(fencing_cost) def part2(): visited = set() def calcFenceCostFrom(i, j): """Calculates the fencing cost of the region starting from coords (i, j)""" global garden, m, n plant_type = garden[i][j] stack = [(i, j)] area = 0 # keep track of all distinct, non-intersecting horizontal and vertical segments segments = { "H": defaultdict(set), "V": defaultdict(set) } # fmt: skip while stack: ci, cj = stack.pop() if (ci, cj) in visited: continue visited.add((ci, cj)) # add cell to area area += 1 # check top cell if ci > 0 and garden[ci - 1][cj] == plant_type: stack.append((ci - 1, cj)) else: # record edge segment ei = ci - 0.25 # push out the horizontal segment segment_set = segments["H"][ei] ej_from, ej_to = cj - 0.5, cj + 0.5 # extend the segment to connect with neighbors merge_segments(segment_set, ej_from, ej_to) # merge with current segment set # check left cell if cj > 0 and garden[ci][cj - 1] == plant_type: stack.append((ci, cj - 1)) else: # record edge segment ej = cj - 0.25 # push out the vertical segment segment_set = segments["V"][ej] ei_from, ei_to = ci - 0.5, ci + 0.5 # extend the segment to connect with neighbors merge_segments(segment_set, ei_from, ei_to) # merge with current segment set # check bottom cell if ci < m - 1 and garden[ci + 1][cj] == plant_type: stack.append((ci + 1, cj)) else: # record edge segment ei = ci + 0.25 # push out the horizontal segment segment_set = segments["H"][ei] ej_from, ej_to = cj - 0.5, cj + 0.5 # extend the segment to connect with neighbors merge_segments(segment_set, ej_from, ej_to) # merge with current segment set # check right cell if cj < n - 1 and garden[ci][cj + 1] == plant_type: stack.append((ci, cj + 1)) else: # record edge segment ej = cj + 0.25 # push out the vertical segment segment_set = segments["V"][ej] ei_from, ei_to = ci - 0.5, ci + 0.5 # extend the segment to connect with neighbors merge_segments(segment_set, ei_from, ei_to) # merge with current segment set # number of distinct segments == number of sides sides = sum(len(segment_set) for seg_dict in segments.values() for segment_set in seg_dict.values()) return area * sides def merge_segments(segment_set: set, idx_from: int, idx_to: int): """Merge segment into existing segment set""" # find any overlapping / intersecting segments before and after current former_segment, latter_segment = None, None for s_from, s_to in segment_set: if s_from < idx_from and s_to >= idx_from: former_segment = (s_from, s_to) if s_to > idx_to and s_from <= idx_to: latter_segment = (s_from, s_to) if former_segment is None and latter_segment is None: # there is no overlapping segment segment_set.add((idx_from, idx_to)) elif former_segment == latter_segment: # the overlap segment contains our full segment pass elif former_segment is None: # there is a latter segment only segment_set.remove(latter_segment) segment_set.add((idx_from, latter_segment[1])) elif latter_segment is None: # there is a former segment only segment_set.remove(former_segment) segment_set.add((former_segment[0], idx_to)) else: # both are disconnected segments segment_set.remove(former_segment) segment_set.remove(latter_segment) segment_set.add((former_segment[0], latter_segment[1])) fencing_cost = 0 for i in range(m): for j in range(n): if (i, j) in visited: continue fencing_cost += calcFenceCostFrom(i, j) print(fencing_cost) part1() part2()