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

  • Quant@programming.dev
    link
    fedilink
    English
    arrow-up
    2
    ·
    7 days ago

    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 :D

    Run 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
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    4
    ·
    edit-2
    7 days ago

    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.

    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
    
    • Quant@programming.dev
      link
      fedilink
      arrow-up
      2
      ·
      7 days ago

      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 ^^’

      • mykl@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        7 days ago

        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
        
          • mykl@lemmy.world
            link
            fedilink
            arrow-up
            2
            ·
            edit-2
            7 days ago

            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.

            • Quant@programming.dev
              link
              fedilink
              arrow-up
              2
              ·
              5 days ago

              Damn that’s a lot time saved. I love how unassuming the addition looks for how great an effect it has

              • mykl@lemmy.world
                link
                fedilink
                arrow-up
                1
                ·
                5 days ago

                It was a real D’oh! moment when I visualised the data I was generating and saw all the zeros stretching across the page.

  • sjmulder@lemmy.sdf.org
    link
    fedilink
    arrow-up
    4
    ·
    12 days ago

    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);
    }
    

    https://github.com/sjmulder/aoc/blob/master/2024/c/day12.c

  • hades@lemm.ee
    link
    fedilink
    arrow-up
    3
    ·
    12 days ago

    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)));
    }
    
  • cabhan@discuss.tchncs.de
    link
    fedilink
    arrow-up
    3
    ·
    12 days ago

    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()
        }
    }
    
    • Quant@programming.dev
      link
      fedilink
      English
      arrow-up
      1
      ·
      7 days ago

      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

  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    3
    ·
    edit-2
    12 days ago

    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;
    
  • lwhjp@lemmy.sdf.org
    link
    fedilink
    arrow-up
    3
    ·
    12 days ago

    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
    
    • VegOwOtenks@lemmy.world
      link
      fedilink
      English
      arrow-up
      2
      ·
      edit-2
      12 days ago

      Thank you for showing the floodfill-algorithm using explored/open sets, mine was hellish inefficiently, reminds me of A*.

  • janAkali@lemmy.one
    link
    fedilink
    English
    arrow-up
    3
    ·
    edit-2
    12 days ago

    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()
    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

  • Gobbel2000@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    12 days ago

    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

  • VegOwOtenks@lemmy.world
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    12 days ago

    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
    
  • ystael@beehaw.org
    link
    fedilink
    arrow-up
    2
    ·
    12 days ago

    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 &lt; rsize, csize)'
    coords =: ($ grid) &amp; #:
    uncoords =: ($ grid) &amp; #.
    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 (&lt; @: ,"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. &lt;: 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. &lt;: 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 : '(#~ ((= &amp; (y { data)) @: ({ &amp; 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 : '&lt;./ {. |: 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 =. (-. ((&lt;: 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 &lt; c2 - c1 do. 0 return. end.
       if. (0 = r) +. rsize = r do. 1 return. end.
       upper_neighbors =. (uncoords"1) 2 2 $ (&lt;: r), c1, (&lt;: 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 &lt; r2 - r1 do. 0 return. end.
       if. (0 = c) +. csize = c do. 1 return. end.
       left_neighbors =. (uncoords"1) 2 2 $ r1, (&lt;: c), r2, &lt;: 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' =. (&lt; @: ;)"1 |: cell_edges"0 cells
       edge_pairs_of_row =. ((> @: {.) (,"0 1) ((2 &amp; (]\)) @: > @: {:))
       horiz_edge_groups =. ({. ;/.. {:) |: raw_horiz
       new_h_edges_per_row =. (-. @: (cells &amp; hconnected)"1 &amp;.>) (&lt; @: 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 &amp; vconnected)"1 &amp;.>) (&lt; @: 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
    
  • iAvicenna@lemmy.world
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    12 days ago

    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)
    
    
  • Ananace@lemmy.ananace.dev
    link
    fedilink
    arrow-up
    2
    ·
    12 days ago

    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;
    }
    
  • SteveDinn@lemmy.ca
    link
    fedilink
    arrow-up
    2
    ·
    12 days ago

    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),
        };
    }
    
    • hades@lemm.ee
      link
      fedilink
      arrow-up
      1
      ·
      11 days ago

      What is the Point type? I’m surprised that you can’t just lexicographically sort instead of plot.OrderBy(p => (p.Row * 10000) + p.Col).

      • SteveDinn@lemmy.ca
        link
        fedilink
        arrow-up
        1
        ·
        10 days ago

        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 :)

  • Pyro@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    12 days ago

    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()