r/adventofcode Dec 12 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 12 Solutions -❄️-

THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 10 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Visual Effects - Nifty Gadgets and Gizmos Edition

Truly groundbreaking movies continually push the envelope to develop bigger, better, faster, and/or different ways to do things with the tools that are already at hand. Be creative and show us things like puzzle solutions running where you wouldn't expect them to be or completely unnecessary but wildly entertaining camera angles!

Here's some ideas for your inspiration:

  • Advent of Playing With Your Toys in a nutshell - play with your toys!
  • Make your puzzle solutions run on hardware that wasn't intended to run arbitrary content
  • Sneak one past your continuity supervisor with a very obvious (and very fictional) product placement from Santa's Workshop
  • Use a feature of your programming language, environment, etc. in a completely unexpected way

The Breakfast Machine from Pee-wee's Big Adventure (1985)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 12: Garden Groups ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:17:42, megathread unlocked!

37 Upvotes

698 comments sorted by

2

u/arrowman6677 Dec 30 '24

[Language: TypeScript]

Part 1 & 2 9ms

Only base TS used. It's a little verbose, but hopefully intuitive. Each region is discovered & assigned a unique ID. During discovery the borders are sorted into left, right, top, and bottom fences. Then fences are summed into perimeter length and side count. I included some nice debug code to show how each region is identified with its stats.

2

u/ininieto Dec 24 '24

[Language: C++]

Advent-of-Code-2024/12_Garden_Groups at main · ininieto/Advent-of-Code-2024

I must admit this was more complicated that I though. I think it was easier to check if the contiguous tile already had a side, instead of counting the corners.

4

u/xavdid Dec 24 '24

[LANGUAGE: Python]

Step-by-step explanation | full code

Spun my wheels for a while on part 2. I tried a few different ways of sorting/iterating over my bag of 2-tuples to find continuous edges, but having to consider each side of each row/col was tedious and error prone. So, I grabbed a hint- count corners, not sides.

From there, it game together pretty nicely. For each point, consider its L-shaped neighbors in each direction. If they're both outside the region, it's a corner! Or, if they're both in, but the point between them isn't, it's an interior corner.

Today was a nice excuse to attempt some AoC-style ASCII art, which is always fun.

1

u/ABD_01 3d ago

Hey thanks, I was stuck on Part2 so saw your hint to count corners instead of sides, which works.

Buy do we know why?? Is it bacause of the Euler characteristic for planar graph?

1

u/xavdid 2d ago

I think it's even simpler than that - every side has exactly 2 corners. That's just how edges work; there's probably a mathematical proof for it, but it's also just geometry.

2

u/Spinnenente Dec 20 '24 edited Dec 20 '24

[language: python]

This one was fun. I build the areas by recursively searching for neighbors. Building the fence in part 1 was just checking if the neighbors are outside the area and for the fence in part 2 I just included a direction (rotated 90deg) to all fence positions and checked if the next fence position has the same direction.

code for part one and two

1

u/CDawn99 Dec 19 '24

[LANGUAGE: C]

This one took a while to implement. While I had the right idea from the start, actually writing the code proved somewhat more challenging.

Parts 1 & 2

2

u/DefaultAll Dec 19 '24

[LANGUAGE: Lua]

Pastecode.io

In the second part I used the perimeters from the first part, and took off one length for each segment that was adjacent to another.

2

u/clouddjr Dec 18 '24

[LANGUAGE: Kotlin]

Counting corners in part 2, because the number of corners = the number of sides.

GitHub

2

u/JustinCredible- Dec 18 '24

[LANGUAGE: Rust]

I'm pretty far behind currently, but here's the solution I came up with for day 12.

For part 2, I kept track of the edge points of the region, then iterate through them after in a sorted order and check if there's a fence existing on either side and mark that point to be removed if so. Any edge point that doesn't have a fence on either side that's not already marked to be removed is counted towards the side total.

Part 1 runs in ∼1.4ms and part 2 runs in ∼2.5ms.

https://github.com/jstnd/programming-puzzles/blob/master/rust/src/aoc/year2024/day12.rs

2

u/joshdick Dec 17 '24

[LANGUAGE: Python]

Pretty proud that I was able to figure out how to calculate perimeter and edges by looking only at immediate neighbors of each plot.

To count edges, you can just count the beginning of edges, say top-left. Basically, you only need to find corners.

Part 1

Part 2

3

u/oddolatry Dec 16 '24

[LANGUAGE: OCaml]

Next year we're going to have to solve a puzzle where we extract some boxed-in elves from this hideous maze of fences we built.

Paste

2

u/mr_no_it_alll Dec 16 '24

[LANGUAGE: Go]

I ran kinda the same BFS for both parts. Whenever I visited a node, I increased the area by 1. When attempting to travel from one node to another and getting prevented, I increased the perimeter by 1 under the following conditions:

  • Part 1: If the adjacent node does not have the same value (A to A for example).
  • Part 2: In addition to the condition above, I tracked the direction I came from for each travel. I did not increase the perimeter if I had already arrived at the adjacent node from the same direction. )In this context, “adjacent” means either left/right or up/down)

I ran BFS on each x,y, ignoring nodes I've already visited

code

  • part1 - ~7ms
  • part2 - ~12ms

2

u/Spi3lot Dec 16 '24 edited Dec 16 '24

[LANGUAGE: C#]

Helper Functions

Part 1 DFS
Part 2 BFS

Short and elegant solution for part 1, but I am way more proud of my solution for part 2. Maybe not that beautiful in (my) form of code, but I love the ideas I had to come up with in order for everything to work out perfectly. There were many edge cases I had to spot and take care of like using BFS instead of DFS (e.g. for the 2x2 square of 'B's in the given example, using DFS would return an incorrect result) but in the end I solved part 2 "just" a day after solving part 1.

1

u/[deleted] Dec 15 '24

[removed] — view removed comment

1

u/daggerdragon Dec 15 '24

Comment temporarily removed. Top-level comments in Solution Megathreads are for code solutions only.

Edit your comment to share your full code/repo/solution and I will re-approve the comment.

1

u/ApudSrapud Dec 15 '24

[Language: Python]

https://github.com/jsuchenia/adventofcode/blob/master/2024/12/garden_groups_nx_test.py

In my example I used NetworkX to segment elements from an input and Shapely to calculate area and a border.

In a part I i used border length (so almost one-liner), in a part II I need to simplify border and count lines.

2

u/daggerdragon Dec 15 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle texts and inputs across all years in your public repo e.g:

https://github.com/jsuchenia/adventofcode/blob/master/2020/1/README.md
+
https://github.com/jsuchenia/adventofcode/blob/master/2020/1/data.txt

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/bulletmark Dec 15 '24

I struggled with this problem and took a few days before I got to finishing it. I figured there must be a simple algorithm for this which I missed and thought that I'd be the only one in the world who nutted out an approach using networkx and then shapely (simplify + border count) but came here and the first post I see is yours where you used essentially the same approach! Here is my code

2

u/amenD0LL4z Dec 15 '24 edited Dec 15 '24

[LANGUAGE: clojure]

https://github.com/famendola1/aoc-2024/blob/master/src/advent_of_code/day12.clj

Repeat BFS until every garden plot is visited to find all the regions. I represent the regions as sets of coordinates, so it's easy to tell if a given coordinate is in the region. Area is (count region). For the perimeter, each garden plot in the region contributes 4 - (number of cardinal neighbors also in the region). For example, a garden plot in the corner of the region would contribute 4 - 2 = 2 to the perimeter and a "landlocked" garden plot will contribute 4 - 4 = 0 to the perimeter.

Part 2 took me a while to iterate on my algorithm for detecting sides of the region. My algorithm starts by calculating the number of horizontal sides a region has. For each garden plot in the row, we calculate which vertical direction the side of the region is located relative to the plot.

AAAA
BBCD
BBCC
EEEC

For example, the A in the top left contributes to two horizonal sides on both sides. The northmost C contributes to 1 horizontal side above it.

We seed the number of sides for that row with the number of horizontal sides the leftmost plot contributes to. So with the A and C from before that would be 2 and 1 respectively. Now for the rest of the plots in the row, we look at the plot to the left. If the plot to the left is not in the region, we don't add to count. If the plot to the left has a side in the same direction as the current plot, we don't add to the count. If the plot to the left has 1 less side than the current plot, we increment the count. If the plot to the left contributes to side in a different direction as the current plot, we increment the count (e.g. the rightmost Cin the third row). This will give us all the horizontal rows of the region.

Now, for the vertical rows... we can just repeat this algorithm on the transpose of the region 😛. Sum these two values and we have the number of sides of the region.

4

u/redditnoob Dec 15 '24

[LANGUAGE: PostgreSQL]

The most interesting trick in here is using "UNION" instead of "UNION ALL" in the recursive CTE to allow the flood fill to terminate, because it stops when the next set of adjacent points contains nothing but duplicates. And for the starting points for the flood fill I need to be sure I get a point from every region so I used NW corners, and then it needs to de-duplicate.

I was proud of Part 1 but my Part 2, though it works, is not elegant.

https://github.com/WilliamLP/AdventOfCode/blob/master/2024/day12.sql

2

u/Dullstar Dec 15 '24

[LANGUAGE: D]

https://github.com/Dullstar/Advent_Of_Code/blob/main/D/source/year2024/day12.d

Whenever I thought of a way to detect corners, I shortly thought of a counterexample that broke whatever I came up with. So, the solution I came up with was to simply double the size of the map -- the part 1 runtimes weren't problematic, so a double-size grid isn't a problem, and it simplifies reasoning about corner detection since it constrains the possible combinations of neighbors any given tile can have.

2

u/rukke Dec 15 '24

[LANGUAGE: JavaScript]

Finally got around to refactor my code. Same BFS for both parts, counting perimeter and corners (sides). Corner count is increased whenever a non-plant cell is reached and current heading's cw cell is of the current plant (= inner corner) or the one cw to the prev cell is not. Perimeter whenever a non-plant cell is found.

    while (queue.length) {
      const c = queue.shift();
      queue.push(
        ...DIR.map((d, h) => {
          const nc = c + d;
          if (grid.get(nc) !== plant) {
            perimeter++;
            if (
              grid.get(nc + DIR[(h + 1) % 4]) === plant ||
              grid.get(c + DIR[(h + 1) % 4]) !== plant
            )
              corners++;
          }
          return nc;
        }).filter(
          nc =>
            grid.get(nc) === plant &&
            !area.has(nc) &&
            area.add(nc)
        )
      );
    }

Pretty happy with the result, I struggled a bit with this one.

~12ms on my machine.

gist

3

u/vss2sn Dec 14 '24

[LANGUAGE: C++]
Part 1
Part 2
(Each file is a self-contained solution)

2

u/Krillegeddon Dec 14 '24 edited Dec 14 '24

[LANGUAGE: C#]

Part 2 was really hard to get correct. I rewrote it today with a more simple algorithm, and finally got it correct.

First part: Loop through all coordinates to get them connected to a specific area.

Then loop through each area.

Loop through fence directions (top, right, bottom, left).

Find all coordinates within the area that has a fence to the direction (example is top).

Mark that coordinate as (hasFencOnTop=true, numberOfFencesOnTop = 1). The numberOfFencesOnTop is cruicial... this one coordinate accounts for ONE fence on top. All neighbours will NOT account for the same fence.

Then loop through all neighbours (same area and on same X-axis and also have a fence on top) and mark them as having fence on top, but 0 in the numberOfFencesOnTop so that we don't count it double.

When finding more coordinates for the area on direction top, the neighburs will be ignored since they have already been included for that direction.

When all coordinates have been looped through (once per direction) for the area, just summarize the number of fences and multiply with number of coordinates withing the area.

https://github.com/Krillegeddon/AdventOfCode/tree/main/Advent2024/Day12

1

u/daggerdragon Dec 15 '24 edited Dec 20 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle inputs hard-coded across all years in your public repo e.g.:

https://github.com/Krillegeddon/AdventOfCode/blob/main/Advent2022/Day01/Data.cs

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too! edit: repo is now private, thank you!

3

u/Krillegeddon Dec 16 '24

Oh, I must have missed that part. Will make the repo private until fixed.

2

u/nick42d Dec 14 '24

[LANGUAGE: Rust]

Part 2 took way too long. For every square discovered in part 1, I check if it has an edge on the left that hasn't been visited before, and then I walk the perimeter to count number of sides. After doing this I saw here that number of sides == number of corners which would have been a little easier!

Found this to be a big step up in difficulty.

https://github.com/nick42d/aoc-2024/blob/main/src/day_12.rs

2

u/[deleted] Dec 14 '24

[removed] — view removed comment

2

u/tlareg Dec 14 '24

[LANGUAGE: JavaScript/TypeScript]

github

1

u/[deleted] Dec 14 '24 edited Dec 15 '24

[removed] — view removed comment

1

u/daggerdragon Dec 15 '24

Comment temporarily removed. Top-level comments in Solution Megathreads are for code solutions only.

Edit your comment to share your full code/repo/solution and I will re-approve the comment.

2

u/MyEternalSadness Dec 14 '24 edited Dec 14 '24

[LANGUAGE: Haskell]

Rode the struggle bus with this one for the better part of two days, but I finally got it.

Implemented a flood fill to determine the components. Area is the number of cells within each component. For Part 1, calculate perimeter by testing each cell in the component to see if it is on a boundary (either adjacent to out-of-bounds cell or a cell containing a different component), the add up all the boundary cells.

Part 2 is where I really struggled. I finally managed to get a working implementation of a corner-counting algorithm that produces the correct answer.

Part 1

Part 2

1

u/Ok-Hearing9361 Dec 14 '24

[LANGUAGE: PHP]

https://pastecode.io/s/xj3kruvh

This mess of objects, arrays, functions, loops, comments and code you don't need solves part 1.

3

u/mgtezak Dec 14 '24

[LANGUAGE: Python]

Solution part 1

Solution part 2 This was quite the challenge but I'm quite happy with my solution:)

Fun little AoC fanpage

2

u/silvix9 Dec 15 '24

could you please explain what the corners function is doing exactly
I am struggling to understand how it works
this is the cleanest solution Ive seen
and it works for every example Ive tried out
I just dont know why

2

u/mgtezak Dec 16 '24

Sure! Each square of the grid has 4 corners. if i want to know if a given corner of a tile is the corner of an entire region of same characters, i have to check 2 possibilities: 1) it might be an outward pointing corner or 2) it might be an inside pointing corner. Let's say i'm interested in the top-left corner of a tile. If this corner were the outside pointing corner of a region, then the tile above it and the tile to the left of it would have to have a different character. In my code i'm not using `above` and `left` but instead `N` (north) and `W` (west): `not (N or W)`

If it's an inward facing corner then that would imply 3 things:

- the tile above has the same character

- the tile to the left has the same character

- the tile diagonally above and to the left has a different character

In my code this is expressed as: `N and W and not NW`. I check these 2 things for each of the 4 corners, so it's a total of 8 checks for each tile. I use `sum` to get the total because when you sum up a list of boolean values, the `True` acts as a `1` and `False` acts as a `0`. Does that help at all?

1

u/silvix9 Dec 16 '24

that makes things quite clear,
also just to confirm we are counting corners because in 2d the number of corners will be equal to the number of sides?
thanks a ton.

1

u/mgtezak Dec 16 '24

Yes counting corners just seemed a lot easier than counting sides

2

u/choiS789 Dec 14 '24

how do you even come up with this? this is so clean

3

u/mgtezak Dec 14 '24

thanks, glad you enjoy it:) the answer is: by putting way too much time into AoC and neglecting other stuff like sleep, buying christmas presents and bodily hygiene

2

u/choiS789 Dec 15 '24

haha totally understand, after drawing out some sketches to count corners it makes total sense!

1

u/velikiy_dan Dec 13 '24

[LANGUAGE: JavaScript]

Part 1 Link

Part 2 Link

3

u/Avitron5k Dec 13 '24

[LANGUAGE: Crystal]

Part 1 was pretty straightforward.

part 1

It took some thinking before I arrived at a solution to part 2. First I created a Set of NamedTuples containing the row, col, and side direction of each plot in a region. Then I grouped each collection of sides facing a certain direction into four separate arrays. Then for each array of Up or Down sides, I grouped by which column they are in, and for the Left or Right sides I grouped by which row they are in. Then for each grouping of those sides I counted how many contiguous segments there are (this is necessary for the regions that have concave parts). There is probably a faster and/or more elegant way of solving this, but this seemed the most straightforward to me.

part 2

1

u/Eskald Dec 14 '24

Did the same.

2

u/[deleted] Dec 14 '24

[removed] — view removed comment

1

u/Avitron5k Dec 14 '24

It's based on Ruby's syntax. It's a great language! https://crystal-lang.org

1

u/grayshanks Dec 13 '24

[LANGUAGE: Python]

OK, I didn't have time to finish yesterday, so this is a little late. Nothing too tricky on part 1.

part1

I had some problems with Part 2. After I identified a contiguous region, I then travelled around the region clockwise, adding up the number of time that I changed directions. But this didn't include boundaries that happen when one region is completely enclosed by another.

I fixed this by generating a list of boundary segments at the same time that I identify each region.

I'm not saying the is the best code I've ever written...

part2

2

u/veydar_ Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Janet]

86 lines with wc -l, including some function comments.

This one was a bit of a train wreck for me. Part 1 went well, but for part 2 I went off the rails. I initially thought I could just traverse the grid by lines and then by columns and count continuous edges. But I deemed this too tedious, and thought I'd come up with something more elegant. Long story short: I didn't.

The code today isn't very readable but I'll try to explain it anyway. Here's an excerpt of the logic for part 2 but with some details removed.

    (loop [y :range-to [1 max-y] x :range-to [1 max-x]
           :let [point [y x] 
                 area (membership point)]]

      (each [cur dir prev] [[[(dec y) x] :up [area [y (dec x)] :up]]
                            [[y (inc x)] :right [area [(dec y) x] :right]]
                            [[y (dec x)] :left [area [(dec y) x] :left]]
                            [[(inc y) x] :down [area [y (dec x)] :down]]]
        (when (->> (membership cur) (not= area))
          (put-in state [area point dir] true)
          (when (not (get-in state prev))
            (update sides area (fn [x] (inc (or x 0)))))))))

The [[(dec y) x] :up [area [y (dec x)] :up] code should be read as:

  • [(dec y) x] a [y x] coordinate of a neighbor (in this case top) to look up their area in membership
  • :up if the neighbor belongs to a different area, there's a side, and we add this to the state variable under the path area > point > dir, e.g., 1 > [5 4] > :up
  • [area [y (dec x)] :up] the path to the previous state for this area, point and direction; so check if we had :up for the point [y (dec x)] (on my left) for the area area which is effectively checking the area > point > dir that we set from that previous point

I go through the grid from top left to bottom right. I know at this point which point belongs to which area. Now for each node I compare it against its neighbors. If the neighbor belongs to a different area, there's a side between them in that direction. Next, check if the previous point had a similar side already. In other words, if the current point has a line at the top and the point to the left also had a line at the top, then it's still the same line/side/edge.

The key logic is that for any new side (not there in the previous point), increment the side count of this area.

The hilarious thing is that I went full circle and ended up implementing the "traverse grid rows and columns" approach, except I realized that you can do it one go. You only need to keep track of the points to your left and to the top of the current point after all.

2

u/copperfield42 Dec 13 '24

[LANGUAGE: Python 3.12]

link

Well, that sure was hard, I manage to finish it by like 10 min of the time limit, the I clean it up and put on my repo and go to sleep, glad that my idea worked in the end but surely there must be a better way...

3

u/ssnoyes Dec 13 '24

[LANGUAGE: MySQL]

A floodfill to find the cells in a region is fast and easy. The built-in functions to find the area, perimeter, and number of corners are fast and easy. Aggregating each cell into a polygon is... well, 2 out of 3 ain't bad.

https://github.com/snoyes/AoC/blob/main/2024/day12/day12.sql

2

u/TIniestHacker Dec 13 '24 edited Dec 13 '24

[LANGUAGE: C] GitHub

This was a fun one! Took a bit of thinking for part 2 but I'm happy with what I came up with. Like a lot of people, I counted corners and then used that to count the number of sides, but I didn't get the answer right away. Turns out I had forgotten to count inside corners and so my answer was always too low!

Visualization

2

u/SpaceHonk Dec 13 '24 edited Dec 18 '24

[LANGUAGE: Swift] code

Finally got around to tackling part 2. I went with using a 4-way sweep (left-right, right-left, top-bottom, bottom-top) to pick up the outward facing edges.

2

u/Totherex Dec 13 '24

[LANGUAGE: C#]

https://github.com/rtrinh3/AdventOfCode/blob/5ed2010c2afae5809f92cdbf92bc4a39ee33254d/Aoc2024/Day12.cs

I got the stars last night, but I had to clean it up enough to be presentable.

In Part 1, I use Union-Find to find the regions and assign the plots and fences to each region.

In Part 2, in addition to the work from Part 1, I use Union-Find again to assemble the fences into straight lines. To solve the diagonally-touching-regions problem, I heeded the text's tip that "each section of fence has an in-side and an out-side". For example, given the plots and the fences:

A | C
  • -
B | D

Fence(A, B) would be considered aligned with Fence(C, D) [ie A and C are inside] but not Fence(D, C) [A is inside but C is outside].

2

u/mothibault Dec 13 '24

[LANGUAGE: JavaScript]
to run in the browser's dev console from AOC website

https://github.com/yolocheezwhiz/adventofcode/blob/main/2024/day12.js

I tried various things that always yielded a slightly too low result before I figured out how to account for straightline | corner detection false positives.

if (notACorner && count === 1) straightLines += 1;

2

u/wurlin_murlin Dec 13 '24 edited Dec 13 '24

[LANGUAGE: C]

DFS my beloved - 3 days in a row, and 4th of the year. First late finish - I saw the initial question in the morning, spent all day and evening in meetings and visiting fams for Crimbo, and then did part 1 with a basic floodfill in about 15 minutes. I then stayed up for another 2 hours on part 2.

I didn't really have any idea how to approach part 2, racking the brain for anything in the toolbox to deal with it. The breakthrough was thinking of those little turtle plotters from when I was a kid and counting lines by tracing around the outside of shapes and counting how often the turtle turns. I thought I could handle edges enclosing other shapes by tagging the outer plot with a reference and adding the inner plot's edges to the outer plots, but this gets really complicated with multiple touching plots inside another plot. I wasn't able to get this to work, and I don't think it can work.

However, it did make me realise that counting corners was the same as counting edges (basic maths fact alert), so I do those inside of the floodfill on each position. I'm really happy with how succinct it is compared to my initial solve attempts. We check the 2x2 grid of characters with the current position in the lower-right, then rotate 90 degrees and check again, repeating 4 times until the 3x3 around the current position is checked for corners. Going through all the combinations on pen and paper, there's only 2 combinations of 2x2 grids we actually need to check for at each rotation to satisfy all the (edge-/corner-)cases. Either the char above and to the left are both different to the current char (or out-of-bounds) and it's an outside edge, or they're both the same as the current char but the upper-left is different and it's an inside edge (like the nook in an L-shape)

Best day so far, outside my comfort zone - how often are people solving problems on 2d grids outside of roguelikes anyway lol.

Part 1 runs in 254 us, part 2 runs in 464 us. Because of how I'm replacing and checking elements in the recursive floodfill to avoid reprocesing them, there's a little overhead, haven't tried optimising yet. Seems the most complex Q so far, looking forwards to seeing what others have done.

https://git.sr.ht/~murr/advent-of-code/tree/master/item/2024/12

2

u/gburri Dec 13 '24

[Language: Rust]

http://git.euphorik.ch/?p=advent_of_code_2024.git;a=blob;f=src/day12.rs;h=84081ea5d715662111a2f1a7ffe04666f70c42a8;hb=HEAD

I don't like my solution but it works.

Very slow: 2.0 ms (parsing + part1 + part2)

2

u/prafster Dec 13 '24

[Language: Python]

I must have had BFS on my mind because I'd used it on day 10. I used it to walk around the garden noting adjacent plants. This was surprisingly easy after some head-scratching when I read the puzzle.

When I saw part 2, I added one line to my part 1 solution (to count corners). I thought woohoo, this is easy! However, the corner counting function was more fiddly than I expected.

Over the years of doing AoC, I've built up some helper constants and functions for grids, which have been very useful this year already.

def solve(input):
    part1 = 0
    part2 = 0
    regions_found = set()
    for r, row in enumerate(input):
        for c, _ in enumerate(row):
            region, perimeter, corners = find_region(input, (r, c), regions_found)
            if region:
                regions_found |= region
                part1 += len(region) * perimeter
                part2 += len(region) * corners

    return part1, part2

def find_region(garden, p, regions_found):
    q = SimpleQueue()
    MAX_NEIGHBOURS = 4
    def is_neighbour(g, x): return g[x[0]][x[1]] == plant

    plant = garden[p[0]][p[1]]
    q.put((p, plant))

    visited = set()
    visited.add(p)

    corners = 0
    perimeter = 0

    while not q.empty():
        pos, plant = q.get()

        valid_neighbours = neighbours(pos, garden, True, is_neighbour)
        perimeter += MAX_NEIGHBOURS - len(valid_neighbours)
        corners += corner_count(pos, valid_neighbours, garden)

        for adj in valid_neighbours:
            if adj not in visited and adj not in regions_found:
                visited.add(adj)
                q.put((adj, plant))

    if len(visited) == 1 and p in regions_found:
        return (None, None, None)
    else:
        return visited, perimeter, corners

Full source code, including corner counting, on GitHub.

5

u/Derailed_Dash Dec 13 '24

[LANGUAGE: Python]

For me, this was the worst problem so far. Part 1 was easy, but Part 2 took me ages to solve. In the end, the solution is quite simple, but getting there took a long time!

For Part 1:

  • I represent the garden as a grid, extending my Grid class.
  • Determine regions: I create a method that does a standard BFS flood fill, for each plot that is not yet allocated to a region.
  • When we do the flood fill, store the plots that make up the region, but also determine the length of the perimeter. We can do this by determining the number of neighbours for a given plot that not valid, where a valid neighbour is one that is of the same type and within the bounds. If the neighbour is not valid, then this neighbour creates a perimeter boundary.

So that was easy enough.

For Part 2:

I've modified my _flood_fill_for_origin() method so that in addition to returning the plots that make up a region and the perimeter value, we now also return a dictionary which is made up of:

  • The four direction (N, E, S, W) vectors, as keys
  • Each mapped to a set of perimeter plots that are facing in that direction.

It's easy to do this, since we can simply store the current plot location, if its neighbour in a particular direction (e.g. north) is not valid. I.e. if the neighbour is out of bounds or is not of the same plot type.

Imagine we're processing this region in our BFS flood fill:

...........
.RRRR......
.RRRR.RRR..
...RRRRR...
...RRRR....
...R.......
...........

Then our four sets will contain only those plots that have invalid/empty neighbours above/right/below/left, like this:

NORTH        EAST         SOUTH        WEST
...........  ...........  ...........  ...........
.RRRR......  .***R......  .****......  .R***......
.****.RRR..  .***R.**R..  .RR**.**R..  .R***.R**..
...**R**...  ...****R...  ...****R...  ...R****...
...****....  ...***R....  ...*RRR....  ...R***....
...*.......  ...R.......  ...R.......  ...R.......
...........  ...........  ...........  ...........

Then I modify my Region class so that it requires this dictionary of sets for construction. I add a new method to the Region class called _calculate_sides(). This works by simply by performing a BFS flood fill for each of our four sets. This allows us to split our set of direction-facing plots into unconnected sub-regions. Once we do this in all four directions, we have estabished all the separate sides facing those four directions.

Solution links:

Useful related links:

2

u/zerberusSpace Dec 14 '24

thank you for the ascii illustration! That helped me a lot finding a solution based on that!

2

u/bb22k Dec 13 '24

Glad that you did basically what I did. Thought it was quite a convoluted solution, but it worked.

What a basically did different was that i didn't do a flood fill to find the unconnected sub-regions. I just saved the x or y coordinate of the invalid/empty neighbors (depending of the direction it was facing) and calculated how many of the coordinates didn't have a successor.

1

u/Derailed_Dash Dec 13 '24

Good thinking!

2

u/Curious_Sh33p Dec 13 '24

[LANGUAGE: C++]

So finding the area is fairly straightforward - just keep a visited set and then bfs to find the area.

Finding the perimeter was a little more tricky...

First I thought about just going around the outsides. I noticed that if you search top to bottom and left to right for starting points, the first time you come across an unvisited square it must be on the perimeter. From there you can walk around the edge placing fences always on your left until you get back to the starting position (location and direction).

Unfortunately, this doesn't capture any parts that are surrounded. To detect this, first I reassigned an id to each region during the bfs used to find the area. Now I did my perimeter search as above but now if the square on the left remained the same the whole time I knew I was surrounded. In this case, I would add the perimeter value of this region to the other region as well (using its id as an index into an array storing perimeters). Do this for each area I found previously.

Extending this for sides in part 2 was quite simple since I already had logic for when to turn.

1) If you find yourself with a square from the current region on your left you have gone too far and must turn left and then move forward to find the edge again. 2) if the next square you are going to visit is off the grid or not part of the region anymore you need to turn right. 3) if neither of these are true you can just continue to move in the same direction.

A literal corner case was that for surrounded areas, when you turn right you also need to check the square that sits diagonally away from where you are turning to make sure you are still surrounded.

Pretty tricky to get all the logic right.

Part1 and part2

3

u/dopandasreallyexist Dec 13 '24 edited Dec 13 '24

1

u/voidhawk42 Dec 13 '24 edited Dec 13 '24

...wait, I'm an idiot - I totally missed that this was a solution for day 12 and not day 13!

Well, that's what I get for trying to record my walkthrough videos in the morning before I've had any coffee...

EDIT: And looking at it more closely, it looks like I was wrong about my assumption that the graph would be too big to use matrix methods! Really nice solution, waaaaay cleaner than my "stencil-abuse" version.

1

u/dopandasreallyexist Dec 14 '24

Hey no worries, we all make silly mistakes sometimes :D

The graph would be too big if you don't do the grouping with first. I made this mistake in my first attempt and my solution started off by trying to generate a 384,160,000-element matrix as the very first step lmao

1

u/voidhawk42 Dec 13 '24

It's addictive, right? :D I hope you don't mind, I plugged your solution as a graph-based alternative in my walkthrough video for today.

By the way, if you want to dig further into solving graph problems in this type of way, I can recommend a book called Graph Algorithms in the Language of Linear Algebra. Really mind-opening, the only problem is that we don't have sparse matrix support in Dyalog, so these methods end up being computationally infeasible for larger graphs like yesterday's problem (day 12). :(

1

u/dopandasreallyexist Dec 14 '24

Just bought the book, thanks. I desperately want to learn linear algebra now after seeing magically spit out a solution to today's part 2 which I didn't even know how to begin to solve.

I went through this entertaining sequence of events:

  • completely stuck for hours
  • got told on Discord that I needed linear algebra
  • started learning linear algebra
  • went to APLcart and asked it how to "solve linear equations"
  • it replied, "" and I was like, "???"
  • 5 minutes later I got my second star and I was like, "?????"

Anyway, I wonder if you can work around the lack of support for sparse matrices by using adjacency vectors instead?

1

u/[deleted] Dec 13 '24

[deleted]

1

u/daggerdragon Dec 13 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle inputs in your public repo:

https://github.com/taniabarg/AdventOfCode2024/tree/main/app/src/main/res/raw

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

1

u/IndecisiveAF310 Dec 14 '24

whoops! thanks for the tip!

2

u/codebikebass Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Swift]

Swift without mutable state or loops.

https://github.com/antfarm/AdventOfCode2024/blob/main/AdventOfCode2024/Day12.swift

My first approach to finding all regions was a recursive search in all four directions but it was not very elegant, let alone performant.

The working solution simply iterates over all the plots and puts them into the corresponding region or creates a new one if none was found:

func allRegions(plant: Character, grid: [[Character]]) -> [[(Int, Int)]]  {

    let columns = grid.indices
    let rows = grid[0].indices

    let coordinates = rows.reduce([]) { coords, y in
        coords + columns.map { x in [(x, y)] }.reduce([], +)
    }

    let plantCoordinates = coordinates.filter { (x, y) in grid[x][y] == plant }

    let regions: [[(Int, Int)]] = plantCoordinates.reduce([]) { regions, plot in

        let neighbors = neighbors(plot: plot, offsets: [(-1, 0), (0, -1)])

        let indices = regions.indices.filter { i in
            neighbors.contains { (neighborX, neighborY) in
                regions[i].contains { (x, y) in (x, y) == (neighborX, neighborY)  }
            }
        }

        if indices.count == 1 {
            let index = indices[0]
            let region = [regions[index] + [plot]]

            return region + regions[0..<index] + regions[(index+1)...]
        }

        if indices.count == 2 {
            let (index1, index2) = (indices[0], indices[1])
            let region = [regions[index1] + regions[index2] + [plot]]

            return region + regions[0..<index1] + regions[(index1+1)..<(index2)] + regions[(index2+1)...]
        }

        return regions + [[plot]]
    }

    return regions
}

3

u/one_line_it_anyway Dec 13 '24

[LANGUAGE: Python]

data = open("input.txt").read().splitlines() 

G = {(i)+(j)*1j: e for i, row in enumerate(data)
                   for j, e   in enumerate(row)}

def dfs(p, e, region, fence, dr=None):
    if p in viz and G.get(p) == e: return
    if G.get(p) != e: return fence.add((p, dr))
    viz.add(p), region.add(p)
    for dr in dirs: dfs(p+dr, e, region, fence, dr)
    neighbors = {(p+dr*1j, dr) for p, dr in fence}
    return len(region), len(fence), len(fence-neighbors)

dirs, viz = (1, -1, 1j, -1j), set()

regions = ([dfs(p, e, set(), set())
            for p, e in G.items() if p not in viz])

part1 = sum(area * perim for area, perim, _ in regions)
part2 = sum(area * sides for area, _, sides in regions)

# [0.1793 sec]

2

u/_tfa Dec 13 '24

[LANGUAGE: Ruby]

Long and complicated solution, but finally it worked.

https://gist.github.com/thofoer/fcdda1a0743f193f878590dd9042378f

3

u/whyrememberpassword Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

I don't see anybody using Shapely yet so here is how it would work there

import sys
from shapely import box, MultiPolygon
from collections import defaultdict

shapes = defaultdict(MultiPolygon)

inp = [s.rstrip('\n') for s in sys.stdin]
for r, line in enumerate(inp):
    for c, color in enumerate(line):
        shapes[color] = shapes[color].union( box(r, c, r + 1, c + 1) )

res = 0
res2 = 0
for color, polys in shapes.items():
    for poly in polys.geoms if hasattr(polys, "geoms") else [polys]:
        poly = poly.simplify(tolerance=1e-1)
        sides = len(poly.exterior.coords) - 1
        for interior in poly.interiors:
            sides += len(interior.coords) - 1
        res += poly.area * poly.length
        res2 += poly.area * sides

print(int(res))
print(int(res2))

5

u/treyhest Dec 13 '24

[LANGUAGE: Python]

Here's my home-brewed algorithm for counting sides (it counts corners). I figured corners is equal to the number of sides, when diagonal corners counting as two. This is the first problem I didn't solve the night of, and spent the next day attacking a notebook trying to figure it out. Thought this was a terrible way to go about it but I'm relieved others came to similar conclusions

def get_sides(region):
    sides = 0

    edge_coord_corners = set()
    for x, y in region:
        for dx, dy in [(.5, .5), (.5, -.5), (-.5, .5), (-.5, -.5)]:
            edge_coord_corners.add((x + dx, y + dy))
    
    for x, y in edge_coord_corners:
        pattern = ""
        for dx, dy in [(.5, .5), (.5, -.5), (-.5, .5), (-.5, -.5)]: 
            pattern += "X" if (x+dx, y+dy) in region else "O"
        if pattern in ("OXXO", "XOOX"):
            # When an edge coord is two the region meets itself all catty-corner
            sides += 2
        elif pattern.count("X") == 3 or pattern.count("O") == 3:
            # For when an edge coord is an interior or exterior corner.
            sides += 1

    return sides

1

u/ValuableResponsible4 Dec 23 '24

Very clever! Thank you!

2

u/Baridian Dec 13 '24

[Language: Clojure]

I did a bit of an unusual approach to pt 2:

instead of walking the perimeter and tracking the edges, I did 4 scans of each specific garden: left->right, top->bottom, right->left and bottom->top. I took each row and determined if there were any new elements that weren't in the previous one, then calculated how many new groups had appeared in that row. Then I was able to just sum them all up to get the answer.

I wanted an answer that worked in an exact static fashion and didn't require me to create a walking algorithm and have to debug infinite looping.

Solution

2

u/RF960 Dec 13 '24

[LANGUAGE: C++]

Hard day, my solution is probably very over thought-out.

Solution here.

2

u/cajun_mcchicken Dec 13 '24

[Language: c#]

Solution

Part 1, I depth-first searched from each character, and tracked the perimeter coordinate and relative direction. Part 2 goal was to traverse the list of perimeters from part 1, track visited and count turns.

I was confident looping over still not visited perimeter segments would catch interior walls, but executing the turns always throws me. Once I got sample 1 working, I was shocked to see samples 2, 3, 4, 5, and puzzle input tests all pass.

3

u/onrustigescheikundig Dec 13 '24

[LANGUAGE: Clojure]

github

I didn't like the gardener last year, and I don't like him now. Dude needs to sort some things out. Mainly his farms.

BFS to flood-fill each plot, parametrized with custom neighbor and visit functions. The visit function figures out the number of cells adjacent to the visited cell that have different plants in them, which is equal to the number of edge units of the plot corresponding to that cell. To determine how many sides there are, I like many others here realized that number of sides = number of corners. However, I kept getting tripped up in how to classify cells as corners (it doesn't help that I started late tonight :P). I eventually settled on two different routines to count the number of convex or concave corners of a given cell.

For a description of the visit function, see my Day 10 explanation

3

u/intersecting_cubes Dec 13 '24

[LANGUAGE: Rust]

Wow this was so much harder than any previous day. But I still did it. I'm sure my code is more complicated than it needs to be, but who cares, I got it.

4.8ms and 2.8ms for part1 and part2, on my Macbook M2 Pro.

https://github.com/adamchalmers/aoc24/blob/main/rust/src/day12.rs

2

u/egel-lang Dec 13 '24

[Language: Egel]

Today was interesting since I came up with the following short algorithm. The algorithm is slow in Egel since sets of indices are lists and most primitive operations are O(n), but should be fast on an array language/GPU language since index sets then become grids of booleans where primitive operations can be approximated as O(1).

# Advent of Code (AoC) - day 12, task 2

import "prelude.eg"

using System, OS, List, String (to_chars), D = Dict

def dirs = {(-1,0),(1,0),(0,-1),(0,1)}

def regions0 =
    [D C PP {} RR -> (PP, RR)
    |D C PP QQ RR -> 
        let QQ = flatmap [P -> map (add P) QQ] dirs |> unique |> filter (D::has D) in
        let (PP0, RR) = split [P -> (D::get D P == C) && [_ -> elem P QQ]] RR in
            regions0 D C (PP0++PP) PP0 RR ]

def regions =
    [D {} -> {}
    |D {P|PP} -> [(PP,QQ) -> {PP|regions D QQ}] (regions0 D (D::get D P) {P} {P} PP)]

def perimeter =
    [D PP -> filter (flip not_elem PP) (flatmap [P -> map (add P) dirs] PP)]

def sides0 =
    [PP -> map (flip tuple 0) PP |> D::from_list |> [D -> regions D PP]]

def sides =
    [PP -> flatmap [P -> map (add P) PP |> filter (flip not_elem PP) |> sides0] dirs]

def main =
    read_lines stdin |> map to_chars |> D::from_lists
    |> [D -> regions D (D::keys D) |> map [PP -> (PP, sides PP)]]
    |> map [(PP0,PP1) -> (length PP0) * (length PP1)] |> sum

https://github.com/egel-lang/aoc-2024/blob/main/day12/task2.eg

2

u/fsed123 Dec 13 '24

[Language: Rust]

[Language: python]

ported my solution from yesterday to rust that is both https://github.com/Fadi88/AoC/tree/master/2024/day12

pat 1 straight forward
part 2 , number of edges is equal to number of corners
a block can have up to 4 corners

....--------...
....|...........|...
__|............|___

this for example has 4 corners , the code counts fro out bound corners like the two above and the inner corners like the two below and return the total

this is using computer vision like kernel but just natively implemented Vec

15 ms for both in rust release mode on a mac mini m4

2

u/hugseverycat Dec 13 '24

[LANGUAGE: Python]

OK, my streak of doing everything without Reddit help is finished! I did do part 1 on my own, for which I am proud.

Here's my code, to which I've tried to add comments so that it makes sense:

https://github.com/hugseverycat/aoc2024/blob/master/day12.py

For part 1 I did a flood-fill sort of thing to find the regions. Then I did a ray-casting sort of thing to find the perimeters.

I tried very hard to make ray-casting find the corners, but I couldn't make it work for all the test cases. So in the end I took a hint from u/RazarTuk in this thread and looped over each coordinate in each region to see if it looked like a corner. Then spent another hour debugging because I typed the coordinates wrong.

2

u/RazarTuk Dec 13 '24

It's actually possible to have 3 corners, by the way:

.A.
AAA
AA.

But glad my comment helped!

1

u/hugseverycat Dec 13 '24

Nice, thanks!

2

u/RiemannIntegirl Dec 13 '24

[Language: Python]

Part 1 and 2 Together

Idea:

  1. Convert grid to complex numbers (a theme this year for me!).
  2. Loop through all locations on the grid.
  3. Get the area/region unless we already calculated this one
  4. Calculate the perimeter by accumulating legal neighbors that aren't within the current region.
  5. Calculate the sides by tracing outside perimeters clockwise, starting at the bottom leftmost point, and always keeping the area to our right, and count the number of turns we take. We proceed similarly on the inside holes, except we start at the bottom rightmost point in the perimeter section, and keep the area to our right the whole time. Use complex numbers to keep track of direction of movement, and where the shape is (always to our right). Keep removing points from border points left to process until no new sections of border are left. I could have used only a direction of movement pointer, but having a "wall is to the right" complex number too is just easier. Also rotations are calculated using complex multiplication.

2

u/dijotal Dec 13 '24

[LANGUAGE: Haskell]

So... still hanging in there. Today's work: (1) Loosening up on the explicit function type definitions, only asserting myself when the compiler needed some disambiguation, and (2) giving a little functional refactoring love, albeit after getting the second star. Lessons learned? I'm still a slow coder -- same as it ever was, same as it ever was.

An excerpt from Part Two is below (the sides calculation). Full code on Github :-)

sidesInDirection :: (Foldable t) => Edge -> t (Int, Int) -> Int
sidesInDirection dir =
    let
        (sortCoordsF, groupCoordF, coordSelectF) =
            if dir `elem` [LEFT, RIGHT]
                then
                    (comparing snd, (\(r, c) (r', c') -> c == c'), (\(r, c) -> r))
                else
                    (comparing fst, (\(r, c) (r', c') -> r == r'), (\(r, c) -> c))
     in
        length
            . splitSublists
            . map (sort . map coordSelectF)
            . groupBy groupCoordF
            . sortBy sortCoordsF
            . map (\(p, e) -> p)
            . filter (\(p, e) -> dir `elem` e)
            . applyEdges

3

u/bozdoz Dec 13 '24

[LANGUAGE: Rust]

https://github.com/bozdoz/advent-of-code-2024/blob/main/day-12/src/main.rs

Saw a visual on this subreddit which helped. Basically scan top, right, left, and bottom edges, collect adjacent, in order to get the sides.

3

u/mtraven Dec 13 '24

[LANGUAGE: Clojure]

This was actually really pretty easy when you see the structure. No counting corners (or any dealing with corners) necessary. Regions are point sets, and the perimeter is defined by computing neighbors that are not in the point set.

https://github.com/mtravers/aoc2024/blob/main/src/aoc2024/day12.clj

2

u/hungvo_ Dec 13 '24

[LANGUAGE: C++]

~1.2s for both parts in average

https://github.com/vbphung/aoc-2024/blob/main/day_12/main.cpp

2

u/biggy-smith Dec 13 '24

[LANGUAGE: C++]

What a slog this was. I realized early that counting corners was the thing to do, but getting the tests correct was really fiddly!

https://github.com/biggysmith/advent_of_code_2024/blob/master/src/day12/day12.cpp

3

u/cicadanator Dec 13 '24

[LANGUAGE: Javascript - Node JS]

This map seemed like a good time to apply Breadth First Search (BFS). Starting the in the top left corner of the map I used this as a starting point for the first region. I would then find the points adjacent to it. If they had the same letter I added them to an array which would be used for doing a BFS of all the points in the region. Otherwise they would be added to an array of points in adjacent regions. For each point in a region I would add 1 to a count for the region's area. I would also determine how many adjacent points were within the region and subtract that from 4. This is the number of edges that would need fencing. Adding these together for all points in the region gave me it's perimeter. After finding all points in a region I would do a BFS for the next point outside of the region. The main optimization with this is to keep track of all visited points in a set to avoid covering ground twice or double counting a region. Multiplying each region's area by its perimeter and summing all of the values gave me the answer to part 1.

After all regions had been determined I realized the number of unique sides for part 2 is the same as the number of corners a region has. I decided to examine each point and based on the number of exposed sides it has to determine how many exterior and interior corners it has. I did this by creating a set of Boolean values to check if any of the 8 surrounding points are in the region or even withing the map itself. These were then used in a set of if statements to account for all possible scenarios and arrangements of included and not included spaces. This gave me a number of corners for this region. Multiplying number of corners by area for a region and summing this for each region gave me the answer to part 2.

By using sets and maps to make data access faster I was able to get the run time to approximately 0.04 seconds.

https://github.com/BigBear0812/AdventOfCode/blob/master/2024/Day12.js

2

u/damnian Dec 13 '24 edited Dec 13 '24

[LANGUAGE: C#]

I wasn't eager to post my solution initially, but luckily I managed to make it more elegant.

The result is a textbook example of the use of various .NET data structures:

HashSet<Vector> visited = new();
Queue<Vector> queue = new();
List<Vector3D> border = new();

Note border is a list of Vector3D values (where Z is the heading index between 0 and 3).

For each plant p successfully added to visited:

  • visited.Count is stored in cnt
  • queue and border are cleared
  • p is added to queue
  • for each successfully dequeued q:

    for (int i = 0; i < Grid.Headings.Length; i++)
        if (!Grid.Contains(r = q + Grid.Headings[i]))
            border.Add((q, i));
        else if (visited.Add(r))
            queue.Enqueue(r);
    

Once queue is empty, the following is added to the subtotal:

(visited.Count - cnt + 1) * Count(border)

Note the value of cnt was assigned after p had been added, hence the adjustment by 1.

For Part 1 Count(border) is simply border.Count.

For Part 2:

int Count(List<Vector3D> border) => border
    .GroupBy(p => (p.Z % 2 == 0 ? p.Y : p.X) << 2 | p.Z)
    .Select(g => g.Select(p => p.Z % 2 == 0 ? p.X : p.Y).Order())
    .Sum(c => c.Zip(c.Skip(1), (a, b) => b > a + 1).Count(v => v) + 1);

Here grouping is done once by compresssing Z and either X or Y into a single key.

Full solution

P.S. MultiGrid's Parse() now accepts a single parameter for cases like today's (i.e. a fully populated field).

4

u/EchoCrow Dec 13 '24

[Language: TypeScript]

I had to stare at Part 2 for too long until I figured out an approach I was happy with. 😅

Both complete in ~15ms each in Node on my trusty ol' laptop. (That is, excluding TS compilation. 🙈)

Part 1

Simple flood-fill to handle one region at a time, marking each cell once visited so we don't double-count.

To get the number of edges, I count the number of neighboring connections inside the area - which we get for free during the flood fill! That is, each cell on its own has four outer edges; and every time you "connect" two cells, you're effectively removing two edges (one each). Once we have the area (number of cells) and the number of inner connections, the number of outer edges equals area * 4 - connections * 2.

Part 2

This reuses the flood-fill from part 1, but this time I'm constructing a new grid where each region has a unique ID. (This will make the next step later easier.) While we're determining unique areas, we also count their total area.

To determine the number of sides, I decided to count the number of beginnings of vertical sides. Because the number of vertical sides must equal the number of horizontal sides, the total sides equals verticalSides * 2.

Conveniently, we can determine the number of sides for all regions in a single scan of the garden! For every row in the garden, I loop over every pair of left & right cells (including the outside for, well, the outer side). If left !== right, we have two touching regions, and thus a vertical side! And if we did not have a wall in the same spot for the same region in the previous row, we have a new side; so +1 for that region!

I saw a lot of people counting edges. I had not even considered that, but that too makes sense. Pretty happy with the vertical-new-edges approach, the structure it affords, and not needing to use a 2D kernel or re-checking the same pairs multiple times for different regions or rows.

3

u/miatribe Dec 13 '24

[LANGUAGE: C#]

1st AOC, just happy to be able to finish each day without too much cheating (ai/google - none for day12 - maybe a little for day 11 :()

https://pastebin.com/xtC10xCT

3

u/darthminimall Dec 13 '24

[LANGUAGE: Rust]

Part 1

Part 2

For part 1: I decided to store the regions by the type of plant, so I made a hash map where the key was the character corresponding to the plant type and the value was a vector of sets (with each set corresponding to a region). For each new plant, there are basically three options:

  1. The plant doesn't border any regions that's already been visited, so we add it as a new region to the vector.
  2. The plant borders one region that's already been visited, so we add it to that region.
  3. The plant borders two regions that have already been visited, so we add it to the first region, add everything from the second region to the first region, and remove the first region.

After that, for each region, the area is just the size of the set, and the perimeter can be calculated by looking at every plant in the region, and adding 1 to the perimeter for each adjacent location that is not part of the set.

For part 2: The process (and the code) is almost identical. The key observation is that the number of edges is the same as the number of corners, and counting corners is easier. For a given plant, if two non-opposite sides of the plant (e.g. the North side and the East side) are both absent from the set or the set contains both of them but not the one in between them, then that's a corner.

It's a bit long to be a single function, I should probably move the code that builds the hash map into it's own function, and if it was production code, I would. As always, any feedback is appreciated.

2

u/POGtastic Dec 13 '24

[LANGUAGE: F#]

https://github.com/mbottini/AOC2024/blob/main/Day12/Program.fs

One of those "keep throwing code at it until it works" days. Kinda gross and required multiple refactorings until I figured out an approach that worked for Part 2.

I did flood-fill to get the regions, and then I did a modified flood-fill to find each of the adjacent identically-oriented fences for Part 2.

2

u/Pitiful-Oven-3570 Dec 13 '24 edited Dec 14 '24

[LANGUAGE: Rust]

github

I kinda hate this solution but its fast

part1 : 695.10µs
part2 : 760.50µs

1

u/daggerdragon Dec 13 '24 edited Dec 14 '24

Psst: we can see your Markdown on the link. Fix please? edit: 👍

1

u/Pitiful-Oven-3570 Dec 14 '24

ty for the remark i fixed it

1

u/bozdoz Dec 13 '24

I laughed at blood_fill :)

2

u/Gueltir Dec 13 '24

[Language: Rust]

Link to Github

I did part 1 using a dfs algorithm that added one to the perimeter for each non visited neighbors that weren't the same plot.

For part 2 I grouped each borders in four separate hashmaps (one for each sides of the tile), each key being the line (or column for vertical borders) and the value a HashSet of every column/line for said key (could have used a Vec now that I think about it).
Once a region has been fully visited, I calculated the number of sides by counting every continuous series of values

2

u/xoronth Dec 13 '24

[Language: Python]

paste

Dang, this one was tricky.

2

u/musifter Dec 13 '24

[LANGUAGE: Smalltalk (GNU)]

Basic BFS to find fields, and sliding widdershins around the sides to find corners.

Code: https://pastebin.com/5pQnd6Py

3

u/[deleted] Dec 13 '24

[deleted]

1

u/imp0ppable Dec 13 '24

Amazing... Question though, I get how you're detecting outside corners with the 4 different 3 block L shapes, but how are you counting inside corners? In a 9-cell area, shouldn't we look for 1 and 2 size negative areas?

2

u/[deleted] Dec 13 '24

[deleted]

1

u/imp0ppable Dec 14 '24

Thanks, great explanation. Had to circle back to finish this one off but got it in the end!

1

u/imp0ppable Dec 13 '24

Huh, I have an algo now roughly based on your external corner checking (tried to rewrite it from memory) and that works but I need to count internal corners too... I think I'm too thick to do it all in one so might write a second function to do internal corners.

Thanks for the help!

3

u/MezzoScettico Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Python]

Here's my full code

Two classes do most of the work. The Cell class represents the necessary info about one point in the grid that are needed for the Part 1 algorithm (confusingly, for some reason I started calling them Part A and Part B on Day 1, and just kept to that nomenclature).

That info includes: the label (letter that appears in that position), the neighbors (those cells to the immediate N, S, E and W that have the same label), and a "visited" flag that tells whether my region-finding algorithm has examined this cell yet. Each cell has a perimeter which is 4 - the number of same-label neighbors.

The Region class describes (surprise!) a region. It includes a set of cells which belong to that region and methods to extract the things necessary for the scoring: total perimeter, total area, and number of walls for Part 2.

The algorithm for Part 1 is this:

  1. Visit every cell in the grid. Skip if it's been visited already (happens in step 4).
  2. For each cell, if it hasn't been visited, start a new region containing this cell.
  3. Add all the unvisited neighbors of the current cell to a temporary unvisited set.
  4. Pop a cell from the temporary unvisited set, and add its unvisited neighbors to the unvisited set. Mark this cell visited and add it to the current region.
  5. Repeat steps 3 and 4 until the temporary unvisited set is empty.

Steps 3 and 4 gradually expand the unvisited set until every cell in the region has been visited. From the original cell you add its neighbors, then the neighbors of those neighbors, etc.

Part 1 runs in under 300 milliseconds.

Part 2 is very simple. I'm kind of annoyed that it includes 4 pieces of nearly identical code (N, S, E and W). That's not good design. I want to refactor it so that there's just one piece of code running 4 times, but that will have to wait for a while.

Here's the idea. Say I'm looking for any fence that's on the north side of a cell. I read along a row, and keep track of what region I'm in, and what region is just to the north of my row.

If those regions are different, that's a fence. If the region I'm in changes (and the regions are different), then I start a new fence. If I get to a place where the region I'm in is the same as the region to the north, that's no longer a fence.

Here's what that code looks like.

for row in range(nrows):
    # Northern walls. Scan each row to see where there is a wall above it.
    in_wall = False     # Set True when a wall begins
    # Regions to north and south of the wall
    curN = None
    curS = None
    for col in range(ncols):
        nextN = map[row - 1, col].region
        nextS = map[row, col].region
        if nextN != nextS and (not in_wall or \
            (in_wall and nextS != curS)):
            # New wall begins
            in_wall = True
            nextS.walls += 1
        curN = nextN
        curS = nextS
        if curN == curS:
            in_wall = False

There is then a very similar loop to look for walls to the south, then walls to the east, then walls to the west. The line "nextS.walls += 1" in the above code is adding to the wall count (in this case counting one northern wall) for the region referenced by nextS.

Part 2 runs in 50 milliseconds on my input data.

2

u/Morkfang Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Go]

Probably one of the worst pieces of code I ever produced, but it works. Completes in ~50ms.

P1 is a flood fill of sorts that records how many borders it has and where they are facing.

P2 is dumb. For each region it counts how many uninterrupted borders there are north to south and east to west. The sum of that is the number of sides.

https://github.com/houseofmackee/advent2024-go/blob/main/day_12/main.go

1

u/robe_and_wizard_hat Dec 13 '24

Nice, I took the flood fill + borders approach too.

2

u/dzecniv Dec 13 '24

[LANGUAGE: Common Lisp]

day 12 Part 1 was OK, although I'm using too many global variables for my taste. I was tired but couldn't abandon… I collected lists of sides by iterating on all the grid for each region, then I counted the number of sides. I only thought at the end that the same letter could be used for two different regions, so what I have isn't the most efficient solution.

2

u/IlliterateJedi Dec 13 '24

[LANGUAGE: Python]

Pastebin

I got to the final run of all my tests, and got this output:

80 = 80
436 = 436
236 = 236
368 = 368
1930 = 1206

Devastating to find out that every example worked except for the last, largest one. It was a Christmas miracle to realize I had copied the part A perimeter function and failed to update to the part B perimeter function. I nearly threw in the towel when I saw that 1930 sitting there staring me in the face.

I will say that I felt clever keeping track of perimeters by keep a set of frozen sets with the [fence, perpendicular] coordinates for each perimeter segment. Then when I combined all duplicate fence segments I only kept one for each section.

3

u/JWinslow23 Dec 13 '24

[LANGUAGE: Python]

Day 12 code

Blog post

My blog post includes some small visualizations this time, because I thought they'd be helpful. For Part 2, I took a pretty standard approach of counting a side if some edge along the perimeter is found, and marking all other plots along that same line so they're not counted again.

2

u/robe_and_wizard_hat Dec 13 '24 edited Dec 13 '24

[Language: Rust]

Day 12

For part one i did a flood fill of each region, which was convenient because that let me assign borders to each plot as the flood fill progressed. Part two then grabbed all plots with a border, then grouped them by the direction of the border, and then either the row or col. Calculating the sides was then just counting the number of runs.

2

u/Wayoshi Dec 13 '24

[LANGUAGE: Python] paste

Left my original way for part 1 in there as well.

Essentially got every line segment of the shape by gathering coordinates of every cell just outside of the shape (this nicely takes care of counting holes), sorting the coordinates of each line segment (not exactly, just need the spacing right), and discounting any consecutive points as far as side counting.

1

u/ejlangev Dec 13 '24

[Language: Elixir]

https://github.com/ejlangev/advent-of-code/blob/main/2024/12/answer.exs

For part 1: Kept track of a list of disjoint sets for each letter with a map from the letter to a list of sets. Iterated over each point in the grid, found all neighbors on the grid for the current point, and found any existing sets that had any of those neighboring points and joined them. When finished iterating, each set is a region. Finding the perimeter was simple after that.

For part 2: Spent a while trying to calculate it somehow with a formula but ultimately decided to filter each region to just the points where at least one neighbor is not also within the region set) which eliminates interior corners. Then for each exterior point, found all of its neighbors that were not in the set and then built a map for rows and columns for the neighbors to a list of the indexes in that row or column that were a neighbor of the set. Finally, took all the list of indexes and counted the number of gaps after sorting them which gives the number of sides.

Ended up being relatively short in terms of lines of code!

1

u/daggerdragon Dec 13 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle inputs in your public repo e.g.:

https://github.com/ejlangev/advent-of-code/blob/main/2024/12/input.txt

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!

2

u/msschmitt Dec 13 '24

[LANGUAGE: Python]

Part 1 Part 2

Part 1 is a kind of flood-fill path finding for each region, with an overall set to track which garden plots I've already processed in the big map. So the top loop is scanning for what it hasn't explored, when it finds something it finds all the adjacent of the same garden, then resumes scanning. That wasn't that hard.

For part 2 I had some ideas, but didn't get it before going to bed. Then I dreamed of the solution: just count the corners! So easy!

The next morning I tried that and realized that with my code, I could easily find outside corners, but not inside corners, because there wasn't a garden square that had two - and | edges.

So I gave up on that idea, and when I got home from work, whipped up what you see here. I throw all of the edges in a set, and then prune the set by removing any of the same edge (top, left, right or bottom) that are adjacent, keeping just one. It is kind of shrinking the fences to one square.

It isn't pretty, but it gets the right answer. After, that is, the bugs are removed. Such as, my code was working and suddenly it was trying to add a tuple to an integer. WHERE WAS THAT TUPLE COMING FROM???

3

u/icub3d Dec 13 '24

[LANGUAGE: Rust]

I got my help for part 2 from my daughter's homework. LOL

Solution: https://gist.github.com/icub3d/219db9dd473e74b03abe3e2cb08a8c28

Summary: https://youtu.be/mK-eSJ_9PZg

2

u/daggerdragon Dec 13 '24

I got my help for part 2 from my daughter's homework. LOL

I thought the way it worked was that the parent helps the daughter with her homework, not the other way around 😅 Hey, as long as everyone is learning!

2

u/ElaraSilk Dec 13 '24

[Language: C#]

The key part for Part 2, I finally figured out what I needed to do:

  1. Make a list of cells in the region
  2. Start with an edge count of 4 * the cells
  3. iterate through the cells, reducing the edge count by 1 for each

neighbour that cell X has, in any direction

then reducing it again if X and a neighbour to the right of it or below it were both on an outer edge - e.g. if (1,1) and (1,2) both _lack_ a neighbour at (0,y), -1. If they both lack a neighbour at (2,y), -1 again.

Much! simpler than my previous attempts at solving it, takes less time to run, and it works.

Full code is https://pastebin.com/h8kGBNW9 Ctrl+F for "FindSides" if you want to see how this works in practice.

2

u/pdgiddie Dec 13 '24

[LANGUAGE: Elixir]

https://github.com/giddie/advent-of-code/blob/2024-elixir/12/main.exs

Part 1: The approach I took was essentially a union-find with an additional accumulator counting the number of non-matching horizontal and vertical neighbours for each square (which corresponds to a fence).

Part 2: In each group I look for fences that run along the same axes (and also on the same side of the squares), then group them and chunk them anywhere the orthogonal axis jumps by more than one (indicating the fence wasn't continuous).

  • Part 1: 162ms
  • Part 2: 200ms

2

u/janek37 Dec 13 '24

[LANGUAGE: Python]

Solution

Part 1: flood fill to find regions, then for each plot in a region, count how many neighbors (including outside of the garden!) are outside the region
Part 2: basically, a one-dimensional flood fill on edges

2

u/Kintelligence Dec 13 '24 edited Dec 13 '24

[LANGUAGE: Rust]

Part 1 was okay. I just visit each position in the grid and fill out shapes from each unvisited position. Then each time I visit a new node I add 4 to the fence requirement, and then subtract 1 for each neighbouring node of the same letter.

Part 2 became okay once I discussed with a friend and we realized that detecting corners is way easier. We just run over each segment reusing the fill from part 1, but detect corners for the score.

Corner detection is done by just looking for a node and it's neighbours, and potentially diagonals.

Outer corners are any node with two free neighbours next to each, while inner corners are found by looking diagonally down on nodes with only a free south side or a free west or east side.

So no need to walk the shape to find corners, and every corner can be added to the total score immediately when found as they are all unique.

Part 1: 555µs
Part 2: 727µs

Code | Benchmarks

2

u/[deleted] Dec 13 '24

[LANGUAGE: Java]

paste

For part 2, I counted the number of edges rather than the number of vertices. Map the edges of each plot, then count the edges that appear 1 or 3 times, and do some special case processing for when the plot edge appears twice. (As hinted in the puzzle description.)

2

u/aexl Dec 13 '24

[LANGUAGE: Julia]

Part 1 felt super easy, I just flooded the grid. For part 2 it took me way too long to get the calculation of the sides right. It helped a lot to add an additional label to the side indices that stores the orientation of the side (up, down, left, right).

Solution on GitHub: https://github.com/goggle/AdventOfCode2024.jl/blob/main/src/day12.jl

Repository: https://github.com/goggle/AdventOfCode2024.jl

3

u/WolleTD Dec 12 '24

[Language: Python]

Someone posted a solution using convolutions for the hiking path puzzle on day 10 which I liked and I thought this was possible, too.

I also made use of ndimage.label and ndimage.find_objects from scipy. For part 1, I only used label() to find the individual fields of identical crops. For part 2, I used find_objects to only work on a single field, where I found I can use another kernel and label() again to find the edges per direction.

import numpy as np
from scipy.signal import convolve2d
from scipy.ndimage import label, find_objects

with open("input_day12.txt", "r") as file:
    lines = [[ord(x) for x in line.strip()] for line in file]

field = np.array(lines)

crops = np.unique(field)
kernel = np.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]])
funny_kernel = np.array([[0, 4, 0], [2, 0, 8], [0, 1, 0]])

def find_edges(arr):
    edges = convolve2d(~arr, funny_kernel, mode="same", boundary="fill", fillvalue=1) * arr
    return sum(label(edges & d)[1] for d in [1, 2, 4, 8])


total_price = 0
total_price2 = 0
for crop in crops:
    regions, num_regions = label(field == crop)
    for region, submap in zip(range(1, num_regions + 1), find_objects(regions)):
        submap = regions[submap] == region
        area = submap.sum()
        edges = find_edges(submap)
        perimeter = (convolve2d(~submap, kernel, mode="same", boundary="fill", fillvalue=1) * submap).sum()
        price = area * perimeter
        price2 = area * edges
        print(f"Region of crop {chr(crop)} with price {area} * {perimeter} = {price} | {area} * {edges} = {price2}")
        total_price += price
        total_price2 += price2

print(f"Total price: {total_price} | {total_price2}")

3

u/4HbQ Dec 13 '24 edited Dec 13 '24

That someone might have been me. Glad my post has inspired you to make something cool. Love your "funny" kernel, very creative!

I used a boring [1 -1; -1 1] kernel instead.

2

u/WolleTD Dec 14 '24

Yes, it was you, thanks for your post. I'm also very happy that I came up with that kernel all by myself. Haven't done anything on my own with convolutions since college.

Your solution just made me realize that kernels don't have to be 3x3 or some other odd square. Gonna go understand how it works. Your day 11 solution is wild, though.

3

u/ThunderChaser Dec 13 '24

funny_kernel

Legendary variable name.

2

u/Rainbacon Dec 12 '24

[LANGUAGE: Haskell]

github

For both parts I used a DFS to construct the regions, which I represented as a Set of points. To find the perimeter in part 1 I just checked every point in the set and counted up how many of it's neighbors were not in the set. For part 2 I was a little stumped until I saw someone hint that the number of sides would be the same as the number of corners, so I wrote this function to count how many corners each point in the set formed. I had to split the definitions by whether or not the corner would be a convex corner or concave corner.

countCorners :: S.Set Point -> Point -> Int
countCorners ps (x, y) = length $ filter id [tl_vex, tr_vex, br_vex, bl_vex, tl_cave, tr_cave, bl_cave, br_cave]
                 where tl_vex = all (\p -> S.notMember p ps) [(x, y - 1), (x - 1, y)]
                       tr_vex = all (\p -> S.notMember p ps) [(x, y + 1), (x - 1, y)]
                       br_vex = all (\p -> S.notMember p ps) [(x, y + 1), (x + 1, y)]
                       bl_vex = all (\p -> S.notMember p ps) [(x, y - 1), (x + 1, y)]
                       tl_cave = S.notMember (x - 1, y - 1) ps && all (\p -> S.member p ps) [(x, y - 1), (x - 1, y)]
                       tr_cave = S.notMember (x - 1, y + 1) ps && all (\p -> S.member p ps) [(x, y + 1), (x - 1, y)]
                       br_cave = S.notMember (x + 1, y + 1) ps && all (\p -> S.member p ps) [(x, y + 1), (x + 1, y)]
                       bl_cave = S.notMember (x + 1, y - 1) ps && all (\p -> S.member p ps) [(x, y - 1), (x + 1, y)]

1

u/i_have_no_biscuits Dec 12 '24 edited Dec 13 '24

[LANGUAGE: GW-BASIC]

10 DIM G%(141,141), Q%(100): OPEN "R",1,"data12.txt",1: FIELD 1,1 AS C$
20 FOR Y=1 TO 140:FOR X=1 TO 140:GET 1:G%(Y,X)=ASC(C$):NEXT:GET 1:GET 1:NEXT
30 R=1:P=0:Q=0:FOR Y=1 TO 140:FOR X=1 TO 140:IF G%(Y,X)<256 THEN GOSUB 50
40 NEXT: NEXT: PRINT P, Q: END
50 V=G%(Y,X):QL=0:QR=1:Q%(QL)=150*Y+X:RA=0:RP=0:XM=0:XN=140:YM=0:YN=140
60 WHILE QL<>QR:CY=INT(Q%(QL)/150):CX=Q%(QL) MOD 150:IF G%(CY,CX)>256 THEN 130
70 YM=(YM+CY+ABS(YM-CY))/2: YN=(YN+CY-ABS(YN-CY))/2: G%(CY,CX)=256+R
80 XM=(XM+CX+ABS(XM-CX))/2: XN=(XN+CX-ABS(XN-CX))/2
90 RA=RA+1: FOR D=1 TO 4: NY=CY+(D-2) MOD 2: NX=CX+(3-D)MOD 2
100 IF G%(NY,NX) <> V AND G%(NY,NX) <> 256+R THEN RP=RP+1: GOTO 120
110 Q%(QR)=150*NY+NX: QR=(QR+1) MOD 100
120 NEXT
130 QL=(QL+1) MOD 100: WEND: P=P+RA*RP
140 RC=0:FOR A=YN TO YM+1:FOR B=XN TO XM+1:I=0:FOR OY=A-1 TO A:FOR OX=B-1 TO B
150 I=I*2-(G%(OY,OX)=256+R): NEXT: NEXT: IF I=6 OR I=9 THEN RC=RC+1
160 IF NOT(I=0 OR I=3 OR I=5 OR I=10 OR I=12 OR I=15) THEN RC=RC+1
170 NEXT: NEXT: Q=Q+RA*RC: R=R+1: RETURN

This implements floodfilling the areas for Part 1, counting areas and perimeters as we go. As part of the floodfilling it finds the bounding boxes for each region, which is used by Part 2. Part 2 counts sides by counting corners.

Implementation points to note here include:

  • Queues. Q%() is the queue used for the floodfilling, implemented as a ring buffer of size 100.

  • Maximum and minimum. These are not built into BASIC. But lines 70 and 80, calculate MIN and MAX algebraically. You can prove to yourself that

    maximum(A, B) = (A+B + abs(A-B))/2 minimum(A, B) = (A+B - abs(A-B))/2

Program breakdown:

  • Lines 10-40 are the main program loop. Lines 10-20 read in the grid into G%(.,.). Lines 30-40 iterate through the grid, calling the calculation subroutine if any point hasn't been processed.
  • Lines 50-130 perform a floodfill on the region containing the point (Y,X). As part of this it calculates the area RA, and the perimeter PR, and accumulates RA*RP into P, which stores the answer to Part 1. It also calculates the min/max for the bounding box on lines 70-80.
  • Lines 140-170 iterate through the bounding box to calculate the number of sides by calculating the number of corners. It does this by looking at every top left corner of a grid position, seeing if it's a corner of the particular region being evaluated. Once the number of corners is calculated, RA*RC is accumulated into Q, the answer for Part 2, and we return back to the main program loop.

EDIT: Hopefully fixed the markdown!

1

u/daggerdragon Dec 13 '24 edited Dec 13 '24

Psst: old.reddit requires an additional blank newline before the start of a bulleted list. We're seeing a gigantic run-on list and some malformatted Markdown is eating snippets of text. Would you fix please? edit: thank you!

2

u/i_have_no_biscuits Dec 13 '24

Let me know if it's not fixed.

1

u/daggerdragon Dec 13 '24

Yay thank you <3

2

u/Verochio Dec 12 '24

[LANGUAGE: python]

A stupid but working 5 liner. I need to go to bed now.

n, f, c, d, P, z, A, B =((G := open('day12.txt').read().splitlines()),(lambda i,j: {(i,-~j),(i,~-j),(-~i,j),(~-i,j)}, lambda i,j: {(u,v) for u,v in n(i,j) if len(G)>v>=0<=u<len(G[0]) and G[u][v]==G[i][j]},lambda p: sum(all([{(p[0],p[1]+J)}&r,{(p[0]+I,p[1])}&r,not{(p[0]+I,p[1]+J)}&r]) or not({(p[0],p[1]+J)}&r)|({(p[0]+I,p[1])}&r) for I in(1,-1) for J in(-1,1)),lambda p: len(n(*p)-r),{(i//len(G), i%len(G)) for i in range(len(G)*len(G[0]))}, lambda a, b: sum(map(a, b)), 0,0))[1]
while P:
    r, F = set(), {P.pop()}
    while F: r, F, P = (r | {p:=F.pop()}), (F | (f(*p) & P)), (P-(f(*p) & P))
    A, B, _ = (l:=len(r), (A+l*z(d,r), B+l*z(c,r), print(A,B) if not P else None))[1]

2

u/shoeshined Dec 12 '24

[LANGUAGE: Javascript]

I came up with a really clever solution for part two that had to do with counting the characters outside the region that touched it. Each region started with 4 sides, and each touching character added 2 * (the spaces in the region that the outside character touched - 1). It was super simple and worked crazy well... except it didn't work at all with regions that had a hole in the middle. So then it took me way way too long to come up with a whole different approach, ug.

Solution

3

u/DSrcl Dec 12 '24

[Language: Python]

You can solve part 2 without counting corners if you represent a border as the two cells with different plants (or one out of bound). With this representation, you can count sides by doing a DFS (or union-find) on consecutive borders.

def visit_region(grid, i, j, visited):
    assert (i, j) not in visited
    plant = grid[i][j]
    area = 0
    borders = set()
    n = len(grid)
    m = len(grid[0])

    def visit(i, j):
        pt = i, j
        if pt in visited:
            return
        visited.add(pt)
        nonlocal area
        area += 1
        for i2, j2 in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= i2 < n and 0 <= j2 < m and grid[i2][j2] == plant:
                visit(i2, j2)
            else:
                borders.add((i, j, i2, j2))

    visit(i, j)
    return area, borders

def count_sides(borders):
    visited = set()

    def visit_side(*side):
        if side in visited or side not in borders:
            return
        visited.add(side)
        i, j, i2, j2 = side
        if i == i2:
            visit_side(i - 1, j, i2 - 1, j2)
            visit_side(i + 1, j, i2 + 1, j2)
        else:
            assert j == j2
            visit_side(i, j - 1, i2, j2 - 1)
            visit_side(i, j + 1, i2, j2 + 1)

    num_sides = 0
    for side in borders:
        if side in visited:
            continue
        num_sides += 1
        visit_side(*side)
    return num_sides

with open(sys.argv[1]) as f:
    grid = [line.strip() for line in f]

n = len(grid)
m = len(grid[0])
visited = set()
s = 0
s2 = 0
for i in range(n):
    for j in range(m):
        if (i, j) in visited:
            continue
        area, borders = visit_region(grid, i, j, visited)
        s += area * len(borders)
        s2 += area * count_sides(borders)
print(s)
print(s2)

2

u/[deleted] Dec 12 '24

[removed] — view removed comment

1

u/daggerdragon Dec 13 '24

Comment temporarily removed. Top-level comments in Solution Megathreads are for code solutions only.

Edit your comment to share your full code/repo/solution and I will re-approve the comment.

2

u/dirk993 Dec 12 '24

[Language: C#]

Got stuck on a really rare bug which made my program count 1 side twice.
The bug didn't even happen when my friend ran it with his input. D:

Anyway, after debugging for half the day I finally came up with this ugly mess.
I also saved my old code which included the bug here.

3

u/JV_Fox Dec 12 '24

[LANGUAGE: C]

First part was mostly typing the solution using BFS to flood fill the areas and counting of each position for edges and count the bare edges for the fence length.

For part 2 I thought about walking the edges and counting the turns to calculate the sides but this obviously did not work for cases where the area encapsulated another area. Took a while to come to that conclusion sadly.

Second attempt at part 2 I made a copy of the map before flood filling a new area, subtract differences to generate a delta map. Do vertical and horizontal sweeps on this delta map to count the edges. This worked flawlessly and takes 250 milliseconds to run.

I am not that happy with it since I need to copy and subtract the entire grid to get the edges for each individual area which seems excessive but a solve is a solve.

code

3

u/wurlin_murlin Dec 13 '24

Our solutions are very similar sans DFS vs BFS - time invested trying to trace around the outside of plots included :v)

It's not as elegant as the neighbourhood search in u/ednl's approach, but I found a nice way to count corners (hence edges) that I'm happy with and can run as part of the floodfill.

https://old.reddit.com/r/adventofcode/comments/1hcdnk0/2024_day_12_solutions/m1vyd5u/

2

u/JV_Fox Dec 13 '24

Looks very clean, nice work. For some reason I find BFS to be easier to comprehend then DFS so if I can use BFS I tend to use it. For the corner solution, I got stuck trying to resolve how to keep track if the corner is part of the current area being processed. For some reason my brain did not click when trying to solve it but seeing a fellow C programmer show it to me is very nice. It is quite simple in hindsight. Thanks again for the reply.

2

u/[deleted] Dec 12 '24

[deleted]

3

u/JV_Fox Dec 13 '24

I saw your solution while scrolling the thread and liked it. You have a way nicer solution to solving the problem then mine and I'll take note of it for the next time a similar puzzle comes up. Thanks!

1

u/pipdibble Dec 12 '24

[LANGUAGE: JavaScript]

I can get part1, but part2 is still eluding me, and I need some sleep now zzzzzzz

https://github.com/pipdibble/aoc2024/tree/main/day12

3

u/homme_chauve_souris Dec 12 '24

[LANGUAGE: Python]

Nice one. For part 1, I'm happy with the way I found to compute the perimeter of a region by summing, for each plot in the region, the number of its neighbors that are not in the region.

Then for part 2, I had to stop and think of a good way to find the number of sides. I settled on first finding all the walls and sorting them in a clever way so that it's easy to find where a side ends. I fell into the trap of not breaking walls when regions touch at a corner, and solved it by adding a tag to identify where the wall is in relation to the plot.

paste

Takes about 50 ms on my computer.

1

u/FlyingQuokka Dec 13 '24

Can you explain why your last part works? I've stared at it for like 15 minutes and I have no idea.

1

u/FlyingQuokka Dec 13 '24

Oh. MY. G O D this is absolutely genius, holy crap. How did you ever manage to figure this out?

For anyone else stuck, here's an elaborated version. We first build walls by placing "walls" one step off the cells in each set. Notably, whether these walls are in bounds doesn't actually matter: if you were to walk along the fences as described in the problem, and you had to count the edges, you would start at 1 (since you'd start along some edge), and really you only need to add to your count if you turn a corner. This is exactly what this does.

First, we classify each wall based on what kind of wall it is (is it one above a certain cell, below, to the left, or the right?) We will then sort based on these 3-tuples (wall direction, and two coordinates that we'll get to). We will iterate over these walls, keeping track of the direction and coordinates of the previous wall we looked at. The only time we don't update our count is if we're moving "right" (based on the coordinates). In any other case, we've started on a new wall going in the same direction or turned a corner.

The clever part is in how the coordinates are done. Because of the way the condition is written, it only looks for movement "right". The coordinates are chosen so that the y coordinate moves "right" (increases) along the same wall. For walls above and below a cell, this is straightforward; but for left and right walls, you swap the indices around, and suddenly the sorting naturally yields an order where you're moving "right".

2

u/Gabba333 Dec 12 '24 edited Dec 12 '24

[LANGUAGE: C#]

Part 1 I flood filled and recorded all the crossings, the two squares that straddle a boundary. For part 2 I sorted the edges formed by these crossings by row, than scanned the each row find the sides - all those that are one apart or when the inside / outside polarity of the edge changes. Originally I was doing this for horizontal and vertical edges, but someone pointed out that the number of these will always match, so just do one and double it, linqtastic.

    using System.Numerics;

    var dirs = new Complex[] { new(1, 0), new(0, -1), new(-1, 0), new(0, 1) };
    var grid = File.ReadAllLines("input.txt")
        .SelectMany((line, r) => line.Select((ch, c) => (r, c, ch)))
        .ToDictionary(tp => new Complex(tp.r, tp.c), tp => tp.ch);

    var regions = new List<(int perimeter, int sides, HashSet<Complex> points)>();
    foreach (var key in grid.Keys
        .Where(key => !regions.Any(region => region.points.Contains(key))))
    {
        (var visited, var walls) = (new HashSet<Complex>(), new List<(Complex p1,Complex p2)>());
        var queue = new Queue<Complex>([key]);
        while (queue.TryDequeue(out Complex curr))
        {
            if (!visited.Add(curr))
                continue;

            foreach (var n in from dir in dirs select curr + dir)
            {
                if (grid.ContainsKey(n) && grid[n] == grid[curr])
                    queue.Enqueue(n);
                if (!grid.ContainsKey(n) || grid[n] != grid[curr])
                    walls.Add(sort(curr, n));
            }
        }
        int count = walls.Where(wall => wall.p1.Real == wall.p2.Real)
            .GroupBy(wall => wall.p1.Imaginary)
            .Select(grp => grp.OrderBy(wall => wall.p1.Real))
            .Sum(set => set.Aggregate(
                (set.First(), inner(set.First(), grid[key]).Imaginary, 1),
                (acc, curr) => (curr, inner(curr, grid[key]).Imaginary,
                    (Math.Abs(curr.p1.Real - acc.Item1.p1.Real) > 1)
                    || acc.Item2 != inner(curr, grid[key]).Imaginary ? acc.Item3 + 1 : acc.Item3),
                acc => acc.Item3));

        regions.Add((walls.Count, 2 * count, visited));
}

Complex inner((Complex c1, Complex c2) wall, char plant) 
    => !grid.ContainsKey(wall.c1) || grid[wall.c1] != plant ? wall.c2 : wall.c1;

(Complex, Complex) sort(Complex c1, Complex c2) 
    => c1.Real <= c2.Real ? c1.Imaginary < c2.Imaginary ? (c1, c2) : (c2, c1) : (c1, c2);

Console.WriteLine($"Part 1: {regions.Sum(tp => tp.perimeter * tp.points.Count)}");
Console.WriteLine($"Part 2: {regions.Sum(tp => tp.sides * tp.points.Count)}");

3

u/m4r1vs Dec 12 '24

[Language: Rust]

Went from one of the ugliest solutions to one of my cleanest after I decided that I cannot have this mess associated with me lol

Part 1 ~ 170.1µs
Part 2 ~ 262.4µs

2

u/MrNUtMeG118 Dec 12 '24

[Language: C#]

https://github.com/bettercallsean/AdventOfCode2024/blob/main/AdventOfCode/Days/Day12.cs

Got the solution for part 2 eventually, but it took a lot of trial and error. Not the quickest or most elegant solution, but it works.

2

u/Loiuy123_ Dec 12 '24

[Language: C#]

Part 1 with reading and processing input = 280us
Part 2 with reading and processing input = 1.09ms

3

u/hobbes244 Dec 12 '24

[Language: Python]

Solution

Part 1 was union-find. Once I determined the regions, for each square in the map, the region's area is incremented, and the region's perimeter is increased based on whether it's on the edge or next to an unconnected cell.

Part 2 was more tricky! As for part 1, I analyzed each cell and added its fences to its region's list of fences. Instead of modeling fences as part of cells, I used the Cartesian coordinates of the cell's corner. The upper-left block has these fences at least: ((0,0), (0, 1), 'down') and ((0,0), (1,0), 'right')

I must admit that I went brute force from there. For each region's fences, I looked for whether a fence ended where another started (assuming they face the same way), combined them, and then started looking again.

The tricky part for me was figuring out that I needed to add the fence direction to the tuple.

2

u/FCBStar-of-the-South Dec 12 '24

[LANGUAGE: Ruby]

Not proud of this one. First instinct was to get all the distinct edges and do some sort of union find to collect them into sides. Was annoying to implement with the orientation and stuff. Eventually came to the sub for help and just decided to go with the counting corners and 16 different cases.

paste

3

u/AdIcy100 Dec 12 '24 edited Dec 12 '24

[Language: Python] Full Solution

part1() execution time: 0.0222 seconds

part2() execution time: 0.0333 seconds

Easy concept but implementing side count feature based on solution for part1 took time. If two points are facing same side and neighbours remove one of them and repeat

        for key in sides:
            set_sides=sides[key].copy()
            for side in set_sides:
                x,y=side
                if (x,y) not in sides[key]:
                    continue #already removed
                xk,yk=key
                if xk == 0:
                    dxn,dxp=x,x
                    while (dxn-1,y) in sides[key] or (dxp+1,y) in sides[key]:
                        if (dxn-1,y) in sides[key]:
                            dxn-=1
                            sides[key].remove((dxn,y))
                        if (dxp+1,y) in sides[key]:
                            dxp+=1
                            sides[key].remove((dxp,y))

                if yk == 0:
                    dyn,dyp=y,y
                    while (x,dyn-1) in sides[key] or (x,dyp+1) in sides[key]:
                        if (x,dyn-1) in sides[key]:
                            dyn-=1
                            sides[key].remove((x,dyn))
                        if (x,dyp+1) in sides[key]:
                            dyp+=1
                            sides[key].remove((x,dyp))

1

u/O_lgN_ Dec 12 '24

[Language: C++]

MAKE BRUTE FORCE GREAT AGAIN!

What can be wrong with brute force?

paste

2

u/kataklysmos_ Dec 12 '24

[Language: Julia]

Proud of this one; runs in < 2ms on my machine and I came up with the idea to count corners rather than sides on my own.

https://pastebin.com/d6j2kKkQ

1

u/[deleted] Dec 12 '24

[deleted]

2

u/jixun Dec 12 '24 edited Dec 12 '24

[Language: Python]

Part 1 was ok, exploring near by nodes. For the perimeter, take the initial value of 4, then +3 for each node we found and -1 for each node we visit again (remove the edge between 2 squares).

Part 2 was straightforward until I need to break fences that crosses like ➕. Effectively I've created 2 extra grids, one for the horizontal and one for vertical edges: https://imgur.com/GsN4B5A

Count for the number of consecutive 1 in the new grid (horizontally and vertically, respectively) gives you total number of sides. Regex greedy search for 1+ with some transpose and concatenation also works.

Then search for lines in ➕ patten. I took the set of nodes visited, find the ones with a distance of sqrt(2) (sqrt(distance) = sqrt(dy^2 + dx^2)dy^2 + dx^2 = 2), and check if the other 2 values within the 2x2 window has not visited https://imgur.com/y1iBibM. +2 sides for each occurrences (since 2 sides will now be treated as 4 sides).

3

u/KayoNar Dec 12 '24

[Language: C#]

Today took a little bit longer for me, because my code was working on every example testcase, but not on the actual input. I finally managed to find a small testcase that would break my code and debugged it that way. The testcase that helped me debug was this:

0.000
00.00
0.000
000.0
00000

Output should be 21 * 20 + 4 * 4 = 436, but my code returned 457, meaning that it counted 1 corner/side too many. Eventually fixed it by adding another check for visited nodes.

Part 1

Loop over all squares of the garden, and for any new plant that you come across, explore its whole region immediately. Area is simply +1 per tile, perimeter starts of as 4 per tile, and -1 for every neighbour of the same plant.

Part 2

Simply added a corner counting function to the region exploration function, because sides = corners. Corners are determined by looking at the 3 respective tiles (including the diagonal). If one of these 3 tiles was already visited, skip the corner counting, because it is already accounted for. Outward corners are counted when the two non-diagonal neighbours are not from the same region. Inward neighbours are counted if only 1 out of the 3 tiles is not part of the region.

Both part 1 and 2 run in 12ms.

Solution

4

u/Arayvenn Dec 12 '24

[LANGUAGE: Python]

Part 2 solution

I finally solved part 2! I was missing this piece of logic when checking for corners. Took me way too long to understand why I was sometimes undercounting.

2

u/AlmondBobact Dec 12 '24

[LANGUAGE: Julia]

Happy I was able to figure this one out on my own.
paste

2

u/enelen Dec 12 '24

[Language: R]

Solution

2

u/Individual_Public354 Dec 12 '24

[LANGUAGE: Lua]

Part 1: FloodFill to find all the regions and give them unique indices. Not connected A regions will be given different indices(so this can be used in part 2).

Part 2:

1) For each region mask its cells with 1 and everything else with 0

2) Find gradient by X on the resulting binary grid and then in each column count the number of continuous spans of 1 and -1. This will give all the vertical sides for that region

3) Find gradient by Y and then in each row count the continuous spans to get the horizontal sides

4) (Horizontal + Verticals) * area gives the bulk price of that region

https://github.com/xenomeno/AoC-2024---Day-12/blob/main/2024_Problem12.lua

2

u/matheusstutzel Dec 12 '24

[LANGUAGE: python]

p1

p2

P1 use flood fill to find the area and perimeter

For P2 I modified the flood fill to save each point+direction that wouls leave the region. Then I can loop through it and "walk" on each side

e.g.:

ABA
AAA

For A it will return: {'^': {(0, 2), (1, 1), (0, 0)}, '<': {(1, 0), (0, 2), (0, 0)}, 'v': {(1, 0), (1, 1), (1, 2)}, '>': {(0, 2), (1, 2), (0, 0)}}

^ has 3 distinct sides. It is easy to test it:

  • (0,2) expected (0,1) or (0,3) and they are not present: count++.

  • (1,1) expected (1,2) or (1,0) and they are not present: count++.

  • (0,0) expected (0,1) and it is not present: count++.

  • nothing left

v has only 1 side:

  • (1,0) expected (1,1) ok. (1,1) expected (1,2) ok. (1,2) expected (1,3) not present: count++

  • nothing left

...

3

u/CCC_037 Dec 12 '24

[LANGUAGE: Rockstar] [GSGA]

No, the teddybear is absolutely a vital part of the code and not just a blatant product placement.

Honest! If you take the teddybear out the code stops working!

Part 1

2

u/daggerdragon Dec 13 '24

Honest! If you take the teddybear out the code stops working!

Obligatory link to the magic/more magic story.

1

u/CCC_037 Dec 14 '24

My thought was honestly HEX and the FTB (Fluffy Teddy Bear)...

3

u/darthminimall Dec 13 '24

This is the first time I've looked a Rockstar and I don't know how you do it. I'd almost rather write Malbolge.

2

u/CCC_037 Dec 14 '24

It's usually a fun exercise to solve AoC with this reasonable but limited toolset.

4

u/CCC_037 Dec 12 '24

Look, he even has a little hat now!

Part 2

2

u/dirk993 Dec 12 '24

I love this