Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

🌻 - 2024 DAY 12 SOLUTIONS -🌻

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

28 comments

  • 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

  • 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.

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

  • 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

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

  • 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.

     nim
        
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

  • 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

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

  • 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

  • I know I'm late, but it's still fun and I'm sure no-one will see this.

    Part 2 took me way too long to get right. I was initially only returning the relative point to which a plot needed a fence. I ran into issues of knowing if it was a valid fence or not by my method of counting (later). I eventually went with returning a tuple of the plot and an enum flag of the sides that it has fences on.

    For counting I grouped the points by one axis then sorted on the other and counted the number of times the transition between two wasn't contiguous.

    It could by done in parallel, but the original traversal would need de-duping, which I didn't feel like doing. After that things are done on a region basis, which could be parallel.

    I also can't help but notice mine is by far the longest ( > . < )

    F#

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

  • 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

     uiua
        
$ 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

  • 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

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

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

  • 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.

  • 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.

    Also on github

28 comments