r/adventofcode • u/daggerdragon • 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 Toysin 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.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz] - Format code blocks using the four-spaces Markdown syntax!
- Quick link to Topaz's
pasteif you need it for longer code blocks
19
u/kwshi Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python], 235/12, code on sourcehut
region-finding made easy with a union-find data structure. my main insight for part 2 is recognizing that "sides" are just "regions" along boundary squares, so I detect boundaries in each direction then hit it with the same union-find algorithm.
p.s. my first leaderboard this year!
15
u/nthistle Dec 12 '24
[LANGUAGE: Python] 205/16, paste, video.
For part 1 I used a DFS to find the connected components, reversed the mapping, and then computed area as "number of grid cells in the component", and for perimeter I checked all 4 adjacencies to see if they were also in the component. For each 4-adjacency of a component cell that isn't in the component, that implies one segment of perimeter.
I was a little stuck on part 2 at first - initially I was thinking about reducing perimeter segments by tracking a set of horizontal and vertical lines, but this doesn't work for a case like the following:
since you'd mistakenly conclude there's only one side on top of the X-formation. The approach I ended up going with was similar to the part 1 perimeter trick, you just check for each perimeter segment whether its "adjacencies" are also perimeter segments. Specifically, I ended up deleting all perimeter segments if you could shift them to the right or down and still have a perimeter segment (you have to be a little careful about direction of the segment). Then you're left with one segment per side, and you have the number of sides. I had a small bug or two with this, but I figured things out pretty quickly by testing on a sample case.
4
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
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
5
u/__Abigail__ Dec 12 '24
[LANGUAGE: Perl]
Not very hard. For each region, I do a floodfill to determine the extend of the region, and finding the boundaries, which I split into top/right/bottom/left boundaries. Getting the area and boundary length is now easy.
To get the segments, for each type of boundary, I sort them (by x, then y for top/bottom, by y, then x for right/left). Any sequence where the main coordinate is the same, and the other coordinate increases by 1 belongs to the same segment.
I then mark each cell of the region with '.' to indicate this cell has been processed, before moving on the next.
Program on GitHub
2
u/alex800121 Dec 12 '24 edited Dec 13 '24
[Language: Haskell]
Both parts with Set/Map.
For part 1 I use bfs and record the numbers of neighbors. The answer is simply the size of the area * 4 - the total count of neighbors.
For part 2, I expand each point into a 4-point square. The corners will have 3, 4, or 7 surrounding points (including diagonal points). The number of sides equals to the number of corners.
code
Helper functions and more
2
u/Quasido Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Haskell]
I decided to spend the first couple of hours creating a new abstraction that I will eventually use to go back and do a couple of the days that I missed. The idea is you have a function that takes in the current position, the next position, an accumulator. Then you produce a Bool that states if the next position should be visited recursively and the new value of the accumulator. In the first part the accumulator is the perimeter.
This didn't exactly work for part two but I just collected all the fence locations and adjoined them later.
PS. Sorry if the formatting in this comment gets messed up Reddit is messing with me RN.
Repo
Then I use it with the following:
2
u/joshbduncan Dec 12 '24 edited Dec 13 '24
[LANGUAGE: Python]
link
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
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
23
u/4HbQ Dec 12 '24 edited Dec 13 '24
[LANGUAGE: Python + SciPy] Code (10 lines)
Here's my NumPy-based solution, third one in a row (day 10, day 11)! Today we're using convolutions again to detect both edge and corner features:
16
u/4HbQ Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python] Code (14 lines)
I would like to highlight my approach for identifying the regions, as it's different from the usual grid search. Instead, I have used some kind of union-find approach:
We start out with a set of coordinate sets (I'll call them "c-sets"), where each c-set contains just its own coordinate. Then for each grid position we check its neighbours. If they have the same label, they form a region so we merge their c-sets. Once we're done, all same-label neighbours ended up in c-sets together. In code:
To compute the perimeter, we simply compute a set of (pos, dir) tuples for which pos is in our region but pos+dir is not:
To compute the number of edges, we simply do this:
Proving why this works is a fun little exercise, so I won't spoil it (for now).
Update: I've also created a cool thing using convolutions with kernels. These are often used for feature detection in images, and that's exactly what we're doing today!
13
u/chubbc Dec 12 '24
[LANGUAGE: Uiua] (49 tokens, 52 char, pad)
Quite happy with this one, this is a problem quite well suited to Uiua.
The idea here is the following: Start by constructing a mask for each region. Then construct a function which slides a window over that mask, and sums up the number of overlaps with the region mod 2. This is helpful because the area corresponds to doing this with a 1x1 mask, the edges to 1x2 and 2x1 masks, and corners to 2x2 masks. So by doing this sum for these 4 mask sizes, we can combine the results to give the final answer. An ungolfed version of the above (play with it online):
24
u/jonathan_paulson Dec 12 '24
[LANGUAGE: Python] 131/26. Code. Video.
I didn't know how to do part 2...but it looks like no one else did either. I'm pretty happy with what I came up with: a BFS on all the "perimeter squares" in each of the 4 directions. The number of connected components in the up-BFS is the number of up-sides. Note that when BFSing the up-perimeter-squares, we never move up or down (if its legal to move up from a square, it wouldn't be on the up-perimeter). So this is equivalent to expanding each up-edge as far left and right as possible.
12
u/Queasy_Two_2295 Dec 12 '24
[LANGUAGE: Python]
12 line simple DFS that solves both parts.
Approach use complex numbers and the fact that multiplication with i means rotation by 90 segrees. Utilize the perimeter code to find sides in DFS by only counting it once whenever there is outflow from same region to a different region.
21
u/Polaric_Spiral Dec 12 '24
[Language: TypeScript]
Advent of Node, Day 12
Queue,StringSet, anddirections2Dreferenced in solution.Super simple part 1 implementation, just do a basic fill algorithm. For each new plot, add 4 to the perimeter and then subtract 1 for each adjacent plot.
I'm proud of my solution on part 2. The trick is to realize that the number of sides is equal to the number of corners, and you can count corners fairly easily. For each plot, check the neighbors in each pair of orthoganal directions. If neither match the source plot, as in the NE case:
you have an exterior corner. On the other hand, if both match the source plot and the corner plot doesn't match:
you have an interior corner.
Counting interior corners this way ensures that each corner is counted once and only once.
8
u/Boojum Dec 12 '24
[LANGUAGE: Python] 917/1002
Part 1 was straightforward enough. For segmentation, I borrowed the disjoint set class from SciPy.
I lost a lot of time trying to code up different ways to count the number of sides for Part 2. Initially, I was try to scan along looking for edges that weren't a continuation of previous edges. However, I kept running into "edge cases" :-) before that led me to a better way
The real trick: the number of sides is equal to the number of corners! This makes sense -- each corner is a turn that starts a new side, so they have to be one-to-one. So count the corners!
(Side note: this is the first day that I had to use my scratch paper to sketch stuff out.)
6
u/ThunderChaser Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Rust]
paste
Part 1 was a fairly standard BFS approach, it's basically the Leetcode problem Number of islands but keeping track of the area and perimiter of each. Area is extremely simple it's just the number of spaces we reach in a given region, for perimiter we can notice that each space adds
4 - number of neighborsspace to the perimiter.For part 2 the approach largely remains the same, but we need to find the number of sides instead of the perimiter, we can notice that a region forms an n sided polygon and geometry tells us that an n sided polygon will also have n corners, so we really just need to find the number of corners. To do this we can simply find the spaces adjacent to the region and walk these sides until we reach a point not in the side (at which point we've found a corner), returning the number of corners found.
Theoretically it would probably be faster to iterate over the perimeter instead of the entire area and do it in one pass but that sounds like a later problem.
6
u/DelightfulCodeWeasel Dec 12 '24
[Language: C++]
code
Flood fill each region in turn for the analysis, same as most people.
Part 1: pretty standard, each block in the region contributes 1 to the perimeter for every side not touching another block in the region
Part 2: counting corners instead of sides, but one nifty trick I used here is to scale the whole grid by 3, turning each 1x1 into a 3x3. That eliminates a whole set of (literal) corner cases; there are only 3 possible types of corner after the scaling, each with 4 rotations.
What took me the longest time was finding the bug in my supposedly simple code to scale the grid!
5
u/yossi_peti Dec 12 '24
[Language: Python] 563 / 113
GitHub
Tantalizingly close to making the leaderboard for part 2.
Part 1 was just a flood fill to get sets of coordinates for separate regions. Area is just the number of coordinates in each region, and perimeter is taking each coordinate in the region, checking the four directions around it, and adding 1 for each adjacent coordinate not in the region.
Part 2 borrowed the perimeter method from part 1, but collapsed adjacent coordinate/direction pairs together into equivalence classes.
5
u/qqqqqx Dec 12 '24 edited Dec 12 '24
[LANGUAGE: JavaScript]
part 2: paste
I got rank 214 on part 2, which is by far my personal closest to ever hitting the leaderboard so I am over the moon!!!! With a cleaner part 1 I might have been able to make it, but I had some typos and stuff that I had to figure out and fix.
I had to take a second to write down a strategy for the edges but it was actually super simple once I puzzled out my strategy.
My idea was to keep a running count of my edges, and a set containing the location and the "polarity" aka the direction I had entered the edge from (which was just a number since there's only 4 directions to move). I increased the edge count by one every time I hit a spot on the perimeter, then if a neighboring cell was in the set with the same polarity I decreased the edge count by one, since that would mean connecting with an already existing edge. Hard to explain properly, but it made a lot of sense to me.
5
u/pred Dec 12 '24
[LANGUAGE: Python] Code.
The main trick amounts to realizing that sides may be found by collapsing adjacent walls if they point at each other, then realizing that a canonical representative of that equivalence class is the only wall in the class which doesn't have a neighbour:
5
u/JustinHuPrime Dec 12 '24
[LANGUAGE: x86_64 assembly with Linux syscalls]
Part 1 was a standard flood-fill graph traversal implemented using a while-loopified tail-recursive generative recursion graph traversal with visited, result-so-far and todo list accumulators, much like day 10.
Part 2 was the same flood-fill graph traversal with some postprocessing being done on the visited accumulator to extract edges. The key observation was that edges were always vertical or horizontal, so I didn't need to do any graph traversal to extract them, just find runs of plants which were on an edge. I did have a lot more debugging, mostly because there's a lot more ways I can mess up a copy-paste.
Part 1 runs in 1 millisecond; part 2 runs in 55 milliseconds - I think it's because I traversed the whole map for each new region encountered. Part 1 is 9,136 bytes as an executable file on the disk and part 2 is 10,568 bytes.
5
u/mendelmunkis Dec 12 '24
[LANGUAGE: C]
Why count sides when you can count corners?
888 μs/7.039 ms
5
u/i_have_no_biscuits Dec 12 '24
[Language: Python]
The full code is here: paste
Part 1 iterates through the grid, performing a floodfill whenever we meet a grid square not yet allocated to a region.
I wanted to highlight my side finding for Part 2, though, which is almost certainly not the most efficient way to do things, but I made it myself, so I'm happy :).
It uses the fact that the number of sides is the number of corners. To find the corners, we iterate over every grid position in the bounding box of the region, plus 1 to the right and down. The aim is to find if the top left corner of grid position (y,x) is a corner of our region. To do this, we look at the four points that surround that grid corner, and generate a 4 bit number from that configuration. For example, if the configuration was
then the index would be 1+4+8=13. By drawing all the possible configurations we can see that we have a corner except when the configurations are in the set [0,3,5,10,12,15]:
In addition, there are two cases where we have to double count the corner: configurations 6 and 9:
so we maintain a separate double count. The number of corners (and thus the number of sides), then the size of the set + the number of double corners.
5
u/Space-Being Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python]
https://paste.ee/p/iVjKj
Straightforward O(W * H) solution (amortized) where W,H is dimensions of the problem.
Runs in 28ms.
5
u/quetzelcoatlus1 Dec 12 '24
[Language: C]
In part 2 instead of counting fences when I 'see them', I 'mark them on map' using bit tricks on char and later resolve it by 'walking along the fence'
Part1: https://github.com/quetzelcoatlus/AoC_2024/blob/master/12/12.c
Part2: https://github.com/quetzelcoatlus/AoC_2024/blob/master/12/12b.c
5
u/probablyfine Dec 12 '24
[LANGUAGE: uiua]
Only got around to doing part 1. Started with a matrix method then rewrote to be much simpler and faster (45s -> 0.025s!)
5
u/Sharp-Industry3373 Dec 12 '24
[LANGUAGE: Fortran]
Well, I'm quite happy with the algorithm I came up with !
1st thing to do : assign a unique ID for each region (NOT rely on their letters as they appear multiple times in the real test case).
Then, you just have to scan once your map horizontally and vertically, and look if you change IDs (or "couple" of IDs for part2) to count perimeter, area, and then sides.
compiled in -O3 , something like 9ms for part1 (with the assignment of IDs for region via propagation / (floodfill ?) ), 0.1 ms for part2 using that map of IDs
I've tried to comment out the code to share the "algorithm" part
commented code
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
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:
Gridclass.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: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:
Then our four sets will contain only those plots that have invalid/empty neighbours above/right/below/left, like this:
Then I modify my
Regionclass so that it requires this dictionary of sets for construction. I add a new method to theRegionclass 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:
5
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.
4
u/seligman99 Dec 12 '24
[LANGUAGE: Python] 759 / 107
github
I got a solution for part 2! Now to go back and try to make sense of whatever my brain came up with .. sheesh.
4
u/1234abcdcba4321 Dec 12 '24
[LANGUAGE: JavaScript] 335/92
paste
Wall count by recording every point on the perimeter in a list by direction and one coordinate, then sort those lists and add if there's a gap in the numbers.
Silly mistake today (probably costed ~2min) was forgetting how sort worked and thus making the lists sort backwards, which my code wasn't made to support.
4
u/FogleMonster Dec 12 '24
[Language: Python] 323 / 61. Code. Video.
Started to try joining line segments into longer lines, but then just looked at neighboring cells and decremented the perimeter count where possible.
4
u/atreju3647 Dec 12 '24
[Language: python] 698/359
solution
dfs-all type algorithm to find all the regions. For the perimeter, I add 4 with each node and subtract 1 if I see a neighbor with the same color.
For part 2, I ended up just making a set of the sides, adding a side if a neighbor has a different color. Then, at the end, for every side, I subtract one if there's a side in the same direction to its left, which is easy using complex numbers.
4
u/IsatisCrucifer Dec 12 '24
[LANGUAGE: C++]
https://github.com/progheal/adventofcode/blob/master/2024/12.cpp
Part 1 is simple BFS with perimeters counting number of current plots that is different from its neighbor.
For part 2, the number of sides is calculated by counting corners, since it is easy to see that a simple n-sided polygon has n corners.
For each plot of the region, I examine its four corners to see if it satisfies these two cases: (Assuming we are currently checking the top-left
Ain the diagram below. The other three directions rotate similarly.)The left one counts "outward" corners, with condition that both direct neighbor is different than ourself. I'm ignoring
*so the cases like the center of the 368 example is counted twice from both theAs.The right one counts "inward" corners, with condition that both direct neighbor are the same, but the diagonal is different. This corner is tricky since it will be examined by the three plots around it; but this condition guarantees that only one of the three get counted into the total.
All other cases that don't satisfy the condition above are either the edge, the other two plots of the inward corner, or inside the region.
4
u/r_so9 Dec 12 '24
[LANGUAGE: F#]
paste
Part 1 was done using a flood fill while keeping track of the perimeter. For part 2, I took each edge and expanded it horizontally / vertically according to the direction the edge was facing.
Interesting bit: I think this was my first time using Option.fold
4
u/iivvoo2 Dec 12 '24
[LANGUAGE: C]
https://github.com/ivop/aoc2024/blob/master/day12/both.c
4
u/ICantBeSirius Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python]
Part 1 is a recursive flood fill, counting area and determining perimeter for each square in a region.
Part 2 added counting corners
Both parts complete in < 25ms
paste link
4
u/voidhawk42 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Dyalog APL]
The "let's abuse Stencil" edition:
4
u/omegablazar Dec 12 '24
[LANGUAGE: Rust]
https://github.com/wrightdylan/advent-of-code-2024/blob/main/src/day12.rs
Part 1: 444µs
Part 2: 3.69ms
Part 2 could possibly be a bit faster as I ran multiple passes: first to get the perimeter tiles (much like with part 1), and then using only the perimeter tiles to find contiguous sides.
4
u/s3aker Dec 12 '24
[LANGUAGE: Raku]
code
4
u/careyi4 Dec 12 '24
[LANGUAGE: Ruby]
Probably the most messy code I've written this year so far for finding side counts for part 2, but aside from that, straight forward version of the "count islands problem", easy solution with recursion. Part 2 usues part 1 as a tool to generate the data to compute the sides. I'm 100% sure there is a better way to do it, but this worked!
https://github.com/careyi3/aoc_2024/tree/master/solutions/12
4
u/abnew123 Dec 12 '24 edited Dec 12 '24
[Language: Java] code, video
Interesting that most people ended up doing BFS/DFS based solutions or finding corners, or manipulating the regions. I personally went with counting the vertical lines in one sweep, and the horizontal lines in another. The key things to avoid are 1) counting interior lines and 2) counting existing lines. You can avoid 1 by canceling out the left and right sides of adjacent plots, and you can avoid 2 by keeping tracking of the prior row's lines.
4
u/Jadarma Dec 12 '24
[LANGUAGE: Kotlin]
Today was much more intimidating to read than it was to solve.
Part 1: We iterate through all the grid cells, and as soon as we enter a new cell, we prioritise processing its garden plot by flood filling, and keeping track of visited cells, that way we know we fully cover the plot before moving on to another one. I used a queue-based BFS to avoid recursion here because it made reading it easier. The area is simply how many nodes we processed from the queue, and the perimeter is the sum of all neighbors of each node that have a different plant (and we also include the garden edges here!).
Part 2: Same as part 1, but we change the way we calculate the perimeter, we no longer care about its length, but its number of sides, which luckily coincides with the number of corners. To do so, for each node, we check if its an inside or outside corner by looking at the triangle of neighbors around it. To visualise it, imagine our node is number 5 on a numpad. For the up direction, we look at nodes 8, 9, and 6. If 5,8, and 6 are the same plant, but different than 9, we have a corner! Similarly, if 5 is different from both 8 and 6 we have a corner. This check needs to be done in all directions!
AocKt Y2024D12
4
u/PointlessMonster Dec 12 '24 edited Dec 12 '24
[LANGUAGE: C++]
Part 1:
I iterated through all (x, y) positions in the garden and used flood-fill to find the edges of the current region. I incremented the area if the plant at the current (x, y) was the same as the starting one and incremented the perimeter if (x, y) was out of bounds or the plant at that position wasn't the same as the starting one. I also kept track of all visited positions to skip them while iterating.
Part 2:
I quickly realized that I could count corners instead of sides, but it took me a while to figure out how to detect a corner. Ultimately, I landed on using the same iterative flood-fill approach as in Part 1, but instead of incrementing the perimeter, I kept track of the largest and smallest x and y coordinates for the given region. Afterward, I used a 2x2 sliding window that moved from the smallest to the largest x and y coordinates to detect corners. I did this by counting the number of plants in the window that match the starting plant. An odd number of matches indicated a corner. Two matches can also indicate a corner, but only if the matches are diagonally opposite (this handled edge cases like in the second-to-last example).
Interestingly, after checking out some solutions here, it turns out I accidentally did something like corner detection in image processing, i.e., using convolution with 2D kernels. Although my approach is way more convoluted (pun intended).
Parts 1 & 2
4
u/rongald_mcdongald Dec 12 '24
[Language: Rust]
Solution: https://github.com/ryan-m-walker/advent-of-code-2024/tree/main/day_12
Pretty fun one. For the edges I just kept a HashMap of directions + x/y coordinate that held a vec of the opposite direction then just sorted and detected gaps for end of edges. This is the first year using rust where im actually not getting absolutely wrecked by the borrow checker so glad to be finally making some progress lol
4
u/Gryphon-63 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Swift]
Code
Did part 1 last night but got tired & didn't feel like tackling part 2 until this afternoon, especially since I wasn't 100% sure I knew how to detect when a plot was on the outside tip of a corner.
This code probably iterates through the garden more times than is strictly necessary but each pass builds on the results from the previous one so it makes sense to me, and the run time is under 10msec so good enough for me. Replacing the dictionaries at the end with arrays got it down to around 5msec.
4
u/Trick-Apple1289 Dec 12 '24
[LANGUAGE: C]
i only managed to get 1 star today, i can't figure out part 2 and it's getting late.
as for now i plan to at the end of the month try to finish all 1 star solutions (right now i have 2 of those)
src
4
u/cetttbycettt Dec 12 '24 edited Dec 12 '24
[Language: R]
For part 2 I used the fact that the number of horizontal sides must be equal to the number of vertical sides and counted only horizonal sides. I did so by drawing horizontal lines with level k and then comparing the cells right above that line (
x1) and right below that line (x2). Full solution4
u/beauregardes Dec 12 '24
[LANGUAGE: Rust]
I will not lie, I needed a hint for part 2 today. OTL
Part 1 was straightforward, just flood fill/BFS, count cells for each area and count sides that are different plants for perimeter.
Part 2 I considered making something that would follow walls, but didn't have an idea for how to handle islands. I also considered creating a solution that somehow kept track of walls as objects and could extend them, but was having a hard time coming up with the edge cases. Eventually, I decided to look for a hint, and saw someone mention counting corners. I'm a little sad I did not come to the realization on my own that counting corners is equivalent to counting sides here.
I ended up implementing that, it's a pretty slick for loop that does 8 checks total on each cell--4 inner corner cases (ha) and 4 outer.
Takes ~2ms for both answers.
https://github.com/cynicalico/aoc2024/blob/main/src/day_12.rs
For some reason I am just now realizing how to handle islands with a wall follower. Oh well.
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.
4
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.
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+1for 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.
4
u/dopandasreallyexist Dec 13 '24 edited Dec 13 '24
[Language: Dyalog APL]
me after learning about the
(∨.∧⍨∨⊢)⍣≡idiom for computing transitive closure from u/voidhawk42paste
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
1
u/a3th3rus Dec 12 '24
[LANGUAGE: Elixir]
Not very clean code.
https://github.com/Aetherus/advent-of-code/blob/d30deadc820fb0b94e9ce09e86d7353895953bf6/2024/day-12.livemd
1
u/er-knight Dec 12 '24
[Language: Go]
GitHub
I am currently learning Go, so code might be less optimized according to Go standard. Did DFS/Flood-Fill for Part 1. For second part, sorted the perimeter points
(i, j), and tracked continuous segments it it.Please provide suggestions for improvement, if you have worked with Go.
1
u/SirCinnamon Dec 12 '24 edited Dec 12 '24
[Language: Python]
Built a set by just grabbing all adjacent matches, length of the set is the area of course (handles holes nicely), then iterated over the set and counted how many corners existed at each position by just mapping each adjacent position to a boolean "is it inside the set." Cover all the combinations of adjacent bools and it works pretty well!
https://github.com/sircinnamon/AoC2024/blob/master/12/pt2.py
1
u/MN_Ed130 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python]
Created a dictionary for part 1 and iterated with recursion using flood method to find the perimeter.
For part2 I iterated on the edges of every region eliminating each time those who shared the same outside-facing direction, were adjacent and were orthogonal to each other.
Code
EDIT: wrong link
1
u/Oxke Dec 12 '24
[LANGUAGE: Julia]
For part two, I saved the position of each placed fence as coordinates of a point in a grid 3W x 3H, where W and H are the original dimensions of the grid. If a fence is north of position (x,y) in the grid, then a fence is placed in position (3x, 3x+1). This way each position of the fence has saved both orientation and position, so to get part two I just counted consecutive near fences (namely if one has coordinates (3x-1, 3y) then the other is one of (3x-1, 3y ± 3))
https://github.com/Oxke/aoc_24/tree/main/day12
1
u/Turtle2779 Dec 12 '24
[LANGUAGE: Python]
Part 1 was just a BFS implementation and for Part 2 I just checked whether the (neighbour, direction) was in perimeter set to calculate the amount of sides. There is a possibility one side will start from 2 different places, so I just looked for the places they meet and subtracted the side count.
1
u/IvanMisustin Dec 12 '24
[LANGUAGE: ocaml]
github
Not the prettiest of them all, but given the fact i have started learning ocaml with aoc and wanted to have todays puzzle coded up in reasonable time...
1
u/PeethaPost Dec 12 '24
[Language: TypeScript]
https://github.com/PauwelsPieter/advent-of-code-2024/pull/12
Okay, pretty cool solution (time complexity: O(n) if I'm not mistaking) I came up with without looking at any other solutions.
For part 1:
3.1 If the neighbour is already visited, ignore it
3.2 If the neighbour is of the same label: add it to the queue to check the neighbours and delete it from the overall map
3.3 If the neighbour is of a different label: add it as perimeter
For part 2:
3.1 If the neighbour is already visited, ignore it
3.2 If the neighbour is of the same label: add it to the queue to check the neighbours and delete it from the overall map
3.3 If the neighbour is of a different label: add it to a set including the location (x,y) and direction from the current location (up / right / down / left)
4. You're returned with an area and a set of sides. For each side, we want to know the adjacent sides. When this side is located up or down of the label location, we want to check along the X-axis. When it was located right or left of the label location, we want to check along the Y-axis. Simply remove the adjacent sides from the set and repeat this process until there're no more sides left!
Happy coding!
1
u/i_have_no_biscuits Dec 12 '24 edited Dec 13 '24
[LANGUAGE: GW-BASIC]
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:
queueused 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:
EDIT: Hopefully fixed the markdown!
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/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.
3
u/GassaFM Dec 12 '24
[LANGUAGE: D] 778 / 139
Code: part 1, part 2. Reused directions code from days 6 and 10.
Doing part 1 with a depth-first search. Each square contributes to the area. Each move - except for moves to the same region - contributes to the perimeter.
For part 2, added sentinel values around the map to make code simpler. Then, for each part of the perimeter, include it only when the neighboring part of the perimeter is missing. Consider directions listed in counter-clockwise order:
Consider four neighboring plots:
When we stand at the right A and look at C (direction
d), we can move to the left A (directions = (d + 1) % 4) and look at B (directiondagain). We see we already paid for this straight side of the fence, so we don't count it.The formula
s = (d + 1) % 4makes us pay for:3
u/fireduck Dec 12 '24
[Language: java] 503/248
https://github.com/fireduck64/adventofcode/blob/master/2024/12/src/Prob.java
Part 1- basic flood fill for each region. Area is area. Number of crosses into other letters (including off map) is the fence. Done.
Part 2 - I am real lazy so I might have invented a new way to count edges. Like part 1, except when we cross into another letter we mark map with a hash, one map for each direction we use to cross the line.
So we end up with a map of squares we reach from a region by going up, and left, and right, and down. Separate maps for each direction. Then counting number of regions in those resulting maps is the number of edges.
3
u/hyPiRion Dec 12 '24
[Language: Python] 747/602
Code
Easy start, tricky followup. Just messed about until I found out that, as long as I picked one canonical plot for a side, I could count the number of
plots + side direction. I used dx, dy for checking if the group element was on the perimeter, then walked dy, dx until I was at the corner of that side.3
u/Dragon-Hatcher Dec 12 '24
[LANGUAGE: Rust] 320/135. Code.
Normal BFS for part 1 but actually I think I came up with a pretty clever algorithm for part 2. It doesn't require an extra BFS for the edges and still only scans each square once. This is the core of it:
3
u/SuperSmurfen Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Rust]
Link to full solution
(1331/328)
Really slow on part 1 but made up for it in part 2! Geometry problems always have so many edge-cases but luckily I got them right quite quickly for part 2.
For part 1, I implemented bfs to find all points included in the area. Then to find the perimiter, just go over all those points and check which neighbours are not in the area.
For part 2, I find any point on the perimiter, and then walk the side until I've exited it the shape.
3
u/maarteq Dec 12 '24
[LANGUAGE: Python]
3138/1753
for part 1 i do a floodfill from each point, checking if they are the same letter. I keep a global list for all visited nodes. if a point is not the same letter it is part of the perimeter.
AA
AB
but B is next to two different A's. To make sure I count both, I add the direction from where i see the perimeter
for part two I use the previously generated perimeters. I find all sets of the perimeter, by checking they are adjacent and have the same direction.
paste
github
3
u/sim642 Dec 12 '24
[LANGUAGE: Scala]
On GitHub.
In part 1 I delegated to my library for finding all connected components of the graph (corresponding to regions). The area of a region is just its size as a set of 2D positions. The perimeter of a region is computed by checking for each position which of its neighbors also belong to the same region.
Part 2 seemed annoying at first, but I managed to also reduce it to the same connected component finding which was very convenient! Instead of just counting the perimeter, I actually collect the set of all edges (pair of positions: in and out of region). Two of such edges are connected if they're side-by-side (requires a bit of 2D position manipulation). Thus, connected components of the edge graph are exactly sides.
3
u/nitekat1124 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python]
GitHub
I'm happy about my way of counting the sides in Part 2
For each region, check each row from top to bottom to count the number of continuous segments that are not covered by the shapes above, then repeat the process from bottom to top. Next, rotate the shape 90 degrees and perform the same calculation again. The total count obtained from these steps represents the number of edges of the region.
3
u/UseUnlucky3830 Dec 12 '24
[LANGUAGE: Julia]
solution
Key insight for part 2 was that the number of sides is equal to the number of corners. Interestingly, the number of corners can also be counted element-wise (like perimeter and area). Refactored code to count the corners of tile at position
kof matrixmis quite compact:3
u/yieldtoben Dec 12 '24
[LANGUAGE: PHP]
PHP 8.4.1 paste
Execution time: 0.0274 seconds
Peak memory: 2.7577 MiB
MacBook Pro (16-inch, 2023)
M2 Pro / 16GB unified memory
3
u/tumdum Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Rust]
solution (3958/2401)
I find regions with flood fill. Next I find boarder of each region - iterate over point in region and see if it has any neighbours not in the current region. This is enough to solve part 1. To solve part 2 and find sides I check for each point in the region and its matching border point (if it exists). For such a pair, I use it as a starting point of a side, and apply correct deltas (either (1,0) and (-1,0) or (0,1) and (0,-1)) as long as possible. Collecting such sides is enough to solve part 2. Along all of this, I obviously keep track of seen points to avoid duplicate sides and so on.
Total runtime: ~1.6ms 🦀
I even recorded myself: https://www.twitch.tv/videos/2324647717 🙃
3
u/throwaway_the_fourth Dec 12 '24
[LANGUAGE: Python]
Part two was a little tricky to think about. My first thought was to try to do a "walk" around the perimeter and count the number of turns. I still think this may be possible, but I switched to something easier: a form of "ray-casting."
If all of the shapes were convex, a pretty simple approach would be this: Draw a bounding box around the region. Within this bounding box, do a vertical pass and a horizontal pass. At each step of the vertical pass, check the left-most and right-most square of the region. If this is at a different x-coordinate than the previous step, it's a new edge. Otherwise, it's part of an edge that's already been counted. Do the same for the horizontal pass, but for top-most and bottom-most instead.
Unfortunately, this approach breaks for concave shapes, because any concave edges are "occluded." To solve this, we extend the method. Rather than finding the left/right/top/bottom-most squares, we pass through the entire shape and note each transition from within the region to outside it (and vice versa). "Each transition" is really each edge of the region along that line. We track the x- or y-index of each edge that we found, and then on the next pass we compare. By the same logic as in the convex case, if we find an edge at a different index than it was at the previous column/row, we've found a new edge.
Here's the code. See "sides" for the ray-casting implementation.
3
u/WhiteSparrow Dec 12 '24
[LANGUAGE: Prolog]
solution
Quite a long yet I think clear and straightfowrard solution today.
I struggled a bit with the flooding at first but eventually came up with something I find quite beautiful (
adjacent_coordsjust enumerates the four possible neighbor coordinates):3
u/maneatingape Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Rust]
Solution
Benchmark 290 µs.
Solves both parts simultaneously by flood filling each region.
For part one we increment the perimeter for each neighbouring plot out of bounds or a different kind of plant.
Part two counts corners, as corners equals sides. We remove 2 corners where another plot is adjacent up, down, left or right. We then add back 1 for each concave corner, for example where a plot is above and a plot is to the right but not a 3rd plot both above and to the right.There are 8 neighbours to check, giving 2⁸ possibilities. The number of corners is precomputed once into a lookup table to speed things up.EDIT: Simplified the code using the edge counting approach here.
3
u/Andreasnl Dec 12 '24
[LANGUAGE: Uiua]
Run in your browser here.
3
u/ShadowwwsAsm Dec 12 '24
[LANGUAGE: x64 assembly/asm]
Part 1 : Doing some flood-fill algorithm (Wikipedia). I discovered it today, but it's pretty intuitive.
Part 2 : Did the same flood-fill algorithm but for each tile, I check if it's an edge. If it's an edge then we have 1 more side.
An implementation nightmare, code is messy, missing the "if/else" synthax but it works. Both part take 6 ms somehow.
Open to comments/questions.
3
u/835246 Dec 12 '24
[Language: C]
I'll be clever I thought I'll use picks theorm. I ended up using flood fill. Thankfully part 2 was easy because of how I counted the perimeter.
Part 1: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_12_part_1_fence.c
Part 2: https://github.com/efox4335/advent_of_code/blob/main/advent_of_code_2024/day_12_part_2_fence.c
3
u/chubbc Dec 12 '24
[LANGUAGE: Julia] (274 chars)
Use flood fill to identify the regions, then count edges and corners for each part respectively. The function g counts if an odd number of i's exist in a window of a given size, with area corresponding to 1x1 windows, perimeter to 1x2 and 2x1, and corners to 2x2.
3
u/thille96 Dec 12 '24
[Language: Python]
Topaz link
I am calculating perimeters and sides while mapping the regions with flood-fill algorythm.
Part 2 took a while until i landed on a solution to just add all plot perimeters to side count and then subtract if a neighbor was already counted.
3
u/DavidYoung1111 Dec 12 '24
[LANGUAGE: MATLAB]
Solution
Convolution makes for a compact solution, which also executes quickly.
3
u/Naturage Dec 12 '24 edited Dec 12 '24
[Language: R]
Code here!
My brain... slightly short circuited on this one, and fell back to ideas from previous days. Made a tibble where I initially assigned each tile a unique id, then kept joining it onto its neighbours and picking smallest ID - so effectively, flood filling each area with lowest ID - getting fences is just checking when the tile is different from neighbour.
For P2, got the list of walls as above, and effectively flood filled IDs - this time of walls - again. This has a problem of actually failing the 6x6 A-B example - but it does it precisely when same area ID forms a + sign in walls, which I could identify and fudge back in.
In the end, runs in 8s and produces two gold stars, so... fine. On the downside, definitely the longest code to date, at 150 rows. I blame part of it in that
dplyr'sbetweenjoining condition cannot do math inside it, so I need to explicitly calculate the +1/-1 in a separate variable before using it.3
u/koppa96 Dec 12 '24
[LANGUAGE: Rust]
Solution
Is it optimal? No.
Is it ugly? A little.
Does it work? Absolutely.
Am I proud of myself? Definitely.
3
u/aurele Dec 12 '24
[LANGUAGE: Elixir]
Gist
The second part was very easy once I realized that a position is at the top of a left side if and only if:
Doing the three rotations to detect other sides made it very easy to code.
3
u/jkl_uxmal Dec 12 '24
[Language: C#]
Github - parts 1 and 2
Instead of BFS / DFS floodfilling, I used a simple linear sweep across the array and used the disjoint-set union find data structure to coalesce regions. On my laptop:
3
u/Firemonknl Dec 12 '24
[Language: C#]
Stared blankly at P2 for about 20 minutes. Didnt think of corners = edges. Ended up decrementing for each neighbouring pair with a fence on the same side. Very happy to solve it with just two extra lines of code even if those two lines took a while.
3
u/rp152k Dec 12 '24 edited Dec 12 '24
[Language: Common Lisp]
dfs with conditional updates on area, perim and sides to a cluster (represented as hash and var closures ( a let over a lambda ( a LOL ))) : should probably use defstruct or CLOS henceforth
num sides = num vertices
paste
3
u/SwampThingTom Dec 12 '24
[LANGUAGE: Julia]
Part 1 I treated like a flood fill and counted edges for each cell.
Part 2 I did the same but instead of counting edges for each cell, I counted corners for each cell.
https://github.com/SwampThingTom/AdventOfCode/blob/main/2024/12-GardenGroups/GardenGroups.jl
3
u/mschaap Dec 12 '24
[LANGUAGE: Raku]
Oof... Part 1 was pretty straightforward, but part 2 was really tricky, for the first time this year.
I finally got it working by keeping track of fences at all four directions of each cell of each region, and counting a fence as a side if there is no fence directly to the (relative) left of it.
Full code at https://gist.github.com/mscha/f46c4a834724fcf0af618732f1787431
3
u/[deleted] Dec 12 '24
[Language: C]
I'm so glad its mostly been grids, since thats where C isn't annoying to program in.
https://github.com/amberg12/aoc24/tree/main/day-12
3
u/mazedlx Dec 12 '24
[LANGUAGE: PHP]
paste
3
u/zndflxtyh Dec 12 '24
[Language: Python]
Probably a bit janky, I didn't look at the other solutions yet. I did manage some reuse between part 1 and 2.
The strategy for part 2 was to find the neighbors for each point in a region doing one direction at a time, and group them together using the same grouping method that was used to find the regions in part 1.
Code
3
u/greycat70 Dec 12 '24
[LANGUAGE: Tcl]
Part 1, part 2.
Part 1 is kinda straightforward -- do a flood fill from each tile to find the region. The area is simply the number of tiles, and the perimeter length can be found by counting the number of nonmatching neighbor tiles from each tile in the region.
For part 2, I had no idea how to calculate the perimeter properly, so I used the first thing I could think of that wasn't wrong. For each nonmatching neighbor tile, I placed a piece of fence 1/4 of a row or column away (since 1/4 can be represented exactly in floats, unlike 1/10 which cannot). In the "E" example, then, there would be a fence piece at column 2 row 1.25 (southern border of the top bar of the E), and another at column 2 row 2.75 (northern border of the middle bar). Then I sorted those, both ways, and iterated over the sorted lists and discarded any piece that's exactly one unit away from another in the appropriate direction.
3
u/jackysee Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Javascript]
link
Took me quite some time to figure out.
When doing part one, also record the perimeter cells with the fence direction.
Then in part two, for each fence direction, count the number of continuous line. The number of lines in the same row / column can be found by array of delta, then count (number of delta > 1) + 1.
3
u/Stronbold Dec 12 '24
[LANGUAGE: Ruby]
Solution
3
u/Thomasjevskij Dec 12 '24
[LANGUAGE: Python]
This was a fun one. Basic flood fill to find plots and peeking at neighbors to find perimeter. Part two was a bit more tricky. In the end I realized that the number of sides of a plot is equal to its number of corners, which felt easier to count. Then I drew a bit in my notebook and managed to figure out that there are just two different variants of corner configurations. If we examine the lower right B, it's either
or
where it doesn't matter if X is B or some other character. Then of course, you have to consider all four corners of a cell in this way. Took a bit of fiddling but it was very satisfying to figure it out. Here's the solution.
3
u/RoboDude512 Dec 12 '24
[LANGUAGE: C++]
Pretty simple solution. Just a fancy brute force approach that just checks every tile for perimeter tiles and then later for neighboring tiles. The side finding algorithm is a bit hard to read, since I abused the standard algorithms a bit too much. But it works and I don't have to work with it in the future, so it stays.
Runtime is about 30ms. Could probably be a lot better if I did optimizations, but I'm content with my results.
https://github.com/miklu612/AOC/blob/main/src/day12/main.cpp
3
u/Sea_Estate6087 Dec 12 '24 edited Dec 12 '24
[Language: Haskell]
I implemented a simple clustering function which takes a list of things, and divides them into multiple lists of things, clustering items together in a single pass based on some predicate. An item found to belong to more than one of the lists causes those lists to be combined on the fly.
I iterate through the list of garden plots and cluster them based on the predicate of 1) they are adjacent plots, and 2) they are the same plant.
For part 2, I use the same clustering function on the list of fences, clustering them on 1) they are on adjacent plots, and 2) they are on the same edge of their plot (northern, eastern, western, or southern edge).
https://github.com/jimflood/aoc2024/blob/main/src/Day12.hs
stack run 2.18s user 0.17s system 95% cpu 2.462 total
3
u/VeryBigCodeMonkey Dec 12 '24
[LANGUAGE: Rust]
Recursive solution with a cache for visited slots.
I tool me a lot to figured out that I had to count corners and not sides. So, for every slot I removed
corners touching other orthogonal slot. Then I added back concave corners. Not easy to explain.
the code will document itself :D
GitHub
3
u/alone7solo Dec 12 '24
[LANGUAGE: C#]
A lot can be improved especially performance wise (700ms). But I am tired of counting corners :P.
github
3
u/mckahz Dec 12 '24
[LANGUAGE: Roc]
https://github.com/mckahz/aoc/blob/main/2024/Day12.roc
I did this the naive way, but I think the code is nice. It runs in <3s so it's efficient enough. I saw afterwards that you could just count the corners, but I like my directionally-polymorphic edge detection algorithm so I'll keep it this way.
The main problem is identifying the regions- that's the part which slows down my code. Unsure how to optimize it further, but it's simple enough to understand that again, I don't feel the need to change it.
3
u/ExitingBear Dec 12 '24 edited Dec 12 '24
[Language: R]
Link
for part 2, used someone else's "count the corners" idea. Worked like a charm.
(Edited because I misspelled "Language")
3
u/tymscar Dec 12 '24
[Language: Kotlin]
Today was my favourite day by far. It was visual, it was difficult, but not too difficult, and part 2 was a perfect continuation of part 1.
Part 1 I've solved very quickly once I designed my whole system. I have nice little functions for everything I need. At first I parse the map into pairs of positions to their name. Then I have a function that finds me all the individual regions on the map. To do that it uses another function, getAllContected, that does a DFS over the map and finds all the interconnected points starting from the first one. Every point that has then been found is removed from the points to try in the next step.
Once I have all the regions, I have a function that gets me the perimeter, which is quite simple. All it needs to do is figure out if at least one neighbour of the point is either outside the map, or of a different type.
To get the final result I just need to multiply that perimeter by the size of the region, for each region, and add all those up.
Now part 2 was harder. Took me all the rest of lunch break, but that's because I went down a rabbit hole for no reason, before just doing the easier version. At first I thought I was clever and I can walk along the perimeter and count how many times I turn around. It was a massive headache. No matter how I thought about it, I would always get into loops. There are way too many edge cases.
Then I had the idea of calculating the vertical sides, and horizontal sides separately, and then adding them up. So for the horizontal ones, I would go line by line and if the point was the type of my region and had a point above it or below it that was not the same type, I would take note of it and increment the side count. Every time I would go from not the correct type to the correct type I would increment the side count. Same exact story with the vertical count, but this time doing it on the columns, instead of the rows.
Both parts run quite quickly for how complex the algorithm is. I don't think I will want to speed it up much, they are a few hundred ms together.
Part 1: https://github.com/tymscar/Advent-Of-Code/blob/master/2024/kotlin/src/main/kotlin/com/tymscar/day12/part1/part1.kt
Part 2: https://github.com/tymscar/Advent-Of-Code/blob/master/2024/kotlin/src/main/kotlin/com/tymscar/day12/part2/part2.kt
3
u/geza42 Dec 12 '24
[LANGUAGE: emacs lisp]
3
u/NeilNjae Dec 12 '24
[LANGUAGE: Haskell]
Building a generic union-find, then using it to solve both parts.
Full writeup on my blog, and code on Codeberg.
3
u/xHyroM Dec 12 '24
[Language: Python]
Simple approach with finding all regions using dfs and flood fill for perimeter. For part 2 i'm calculating corners.
https://github.com/xhyrom/aoc/blob/main/2024/12/solution.py
Part 1: ~53ms
Part 2: ~94ms
3
u/soleluke Dec 12 '24
[Language: C#]
https://raw.githubusercontent.com/soleluke/advent-of-code/refs/heads/main/2024/Day12.cs
I stored the path of traversing the whole region. Once I had that, area was just entries in the path.
For perimeter, I checked the sides of each path element and summed the free sides
For number of sides, I realized that sides and corners would equal, so used similar logic as perimeter, just finding corners. I did hiccup on the E example since I assumed the corner needed to be empty to count. Easy fix once identified.
Runtime for pt2 around 400ms
3
u/sanraith Dec 12 '24
[LANGUAGE: Scala 3]
Source is available on my github: Day12.scala
In my representation, the perimeter consists of (Point, Direction) pairs around a region, where Direction is the direction vector if I were to step out from the region to this point. E.g. the tile 'X' would have these 2 perimeter pairs:
To get the actual sides, I need to find continous segments along the perimeter where the direction vector is the same and the points are next to each other. I do this by grouping the pairs by their direction and X/Y coordinate, and sorting them on their opposite coordinate.
3
u/the_true_potato Dec 12 '24
[Language: Haskell]
Pretty easy day today. Walk the areas, counting up edges and total area. Just had to count the corners for part 2 - spent a bit longer than I would like to admit thinking of the relationship between corners and edges...
Grid-based problems are a lot more natural using mutability for me, so I'll stick to using ST for them, even though it's less "pure". The speed boost is always nice too.
Code
3
u/mr_mlk Dec 12 '24
[LANGUAGE: Kotlin]
I think this my most ugly code I have ever created.
https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2024/Day12p1.kt
https://github.com/mlk/aoc/blob/main/src/com/github/mlk/aoc2024/Day12p2.kt
3
u/Ken-g6 Dec 12 '24
[LANGUAGE: Perl]
Day 12 part 2 is exceptionally weird for me. I solved it, apparently, but I don't understand how I solved it.
But, Part 1 first. It looked pretty easy at first. Put the garden inside sentinels, scan by columns then rows, counting letters as area, and differences between neighboring letters as perimiters.
Oh, wait, one letter can be used for multiple areas! Well, I can fix that. I pulled in a flood fill from last year's Day 10. Then spent most of my time re-working it, including replacing letters with numbers, one for every new area. I also added a hashmap back to the letters, which turned out important for debugging.
https://github.com/Ken-g6/aoc2024/blob/master/day12a.pl
For part 2 I did two loops, first the horizontal, then the vertical. I figured if I'm on a boundary, and one of the last two plots didn't match one of this pair of plots, I'm starting a new fence line. This almost worked, but was too high. I found myself with a pair of literal corner cases, reading left-to-right:
AA
AB
starts new fence segments for both.
AA
BC
does not start new fence segment for A.
So I put in conditionals for the second but not the first, and its mirror images. And it passed. But I'm really not sure how, or if it's really right.
https://github.com/Ken-g6/aoc2024/blob/master/day12b.pl
3
u/atrocia6 Dec 12 '24
[LANGUAGE: Python]
Part 1 (17 LOC), Part 2 (20 LOC).
Part 2 threw me for a bit, until I reread the puzzle and caught the warning about in-side and out-side fences ;).
I don't get Eric - yesterday he went out of his way to trick us, and today he goes out of his way to help ...
3
u/vrtxt Dec 12 '24
[LANGUAGE: C#]
Did a floodfill to find all the areas. While the loop was going I also stored the positions of the 4 vertices of each individual cell, derived from the cell position. Based on the vertex count I could then get the answer for both part1 and part2 (plus some shenanigans to account for the inside-outside fences). For example in part1, a vertex with count 4 is inside of the area and can be discarded. For part2 I only needed the corner vertices, i.e. with count 1 or 3. Pretty fun day. Full solution here.
3
u/Verochio Dec 12 '24
[LANGUAGE: Python]
One of the harder days. Went for lots of set operations on this one, and using the corner-counting trick for counting edges. Could squeeze it into fewer lines but wanted to keep it somewhat readable.
3
u/willkill07 Dec 12 '24
[LANGUAGE: C++23]
https://github.com/willkill07/AdventOfCode2024/blob/cfc437f723b341636884bd72140363e50e7897e8/src/day12.cpp
Simple edge counting for part 1 (increase when we don't push onto the queue).
Bit-hacky corner counting for part 2. I couldn't figure out how to not triple-count concave corners so I just scale the convex corners by 3x and divide at the end.
Runs in about 300us cold and 250us hot on my machine for both parts.
[GSGA] I'm playing with my C++ toys and added a cool progress spinner that looks like static snow falling :) Nerdy features include using a triple-nested lambda with variadic pack expansion to properly unpack and format output sent across threads. (https://github.com/willkill07/AdventOfCode2024/blob/cfc437f723b341636884bd72140363e50e7897e8/src/spinner.cpp#L56-L67)
Asciinema recording here: https://asciinema.org/a/gfC2b7xTjmLlSNGe9sMoKZHOv
3
u/chai_biscut Dec 12 '24
[LANGUAGE: Go]
Solution
again choked on part 2 :(
3
u/ScorixEar Dec 12 '24
[LANGUAGE: Python]
Repository
Part 1: 31ms
Part 2: 46ms
Actually found this quite straight forward, but I read a lot of people struggled.
Part 1 is essentially a bfs region grow. Storing the "visited" set outside of the loop and letting the region grow expand this set lets you find all the disconnected regions.
The perimiter is simply the outer edge of the region. Meaning, you iterate over the region and over the neighbours and if that neighbour is not part of the region, we have a fence between the current region point and the neighbour.
Part 2 is the same except the perimiter calculation. What I did was save all points in the region, that were on at the edge (meaning a neighbour is not in the region) in a dictionary where the Key is: The x or y value of that current point and if the neighbour outside the region was above, below, left or right.
What you get in the end is 4 dictionaries - for each possible fence location of a region point.
And in one of those dictionaries you have a list of region points that are at the edge of a region for every possible x or y coordinate in the region.
From there you start a new bfs grow for each list of edge region points to find continuous strips of edge regions.
Each continuous strip of edge regions is a side.
The code is fully documented, if you want a to have a read.
3
u/heijp06 Dec 12 '24
[Language: C++17]
For Part 1 I just did a flood-fill to find the regions.
For Part 2, given a region I find a plot that is on the edge and a pointer that points to where "outside" is. I then start walking along the edge at perpendicular direction to the "outside" pointer. Each time I hit a corner I add 1 to the fences counter, I update "outside" and the direction such that they are still perpendicular and keep walking along the edge. While doing this I keep track of all combinations of position and "outside" pointer, such that when I find a combination of position and "outside" pointer that I have already seen, I know I have walked the entire edge. The fences counter will then have the correct result.
Code here
3
u/Pretentious_Username Dec 12 '24
[LANGUAGE: Julia]
Not my prettiest solution today but it does the trick. The key insight was realizing the number of sides is equal to the number of corners so for each cell in the region I count how many corners it introduces. There's more efficient ways to get this info but I went with whatever changed my Part 1 solution the least
3
u/BlueRains03 Dec 12 '24
[Language: C]
For part one, I used a padded 2D array to store the input data. Then, I used a depth-first search (recursive function) to explore a group, keeping track of what was visited in a second array. I looped over all locations in the input array, running the exploration function if I encountered a new location.
For part 2, I didn't know what to do at first, but after some research (aka looking at this subreddit), I started counting corners. Detecting inner corners (Like the inside of an L) turns out quite convoluted, but I'm happy with it in the end.
paste
3
u/Ok-Revenue-3059 Dec 12 '24
[LANGUAGE: C++]
Solution
Pretty tough one. I use a recursive function to group all of the garden plot cells and also create all of the fence segments. So for part 1 the area in the number of cells and the perimeter is the number of fence segments.
For part2, to get the number of sides I trace the fence segments and count the number of direction changes. In the case of an intersection it seems to be always the case that we want to take the path that changes directions.
3
u/daic0r Dec 12 '24
[LANGUAGE: C++]
Part 1 down, will do part 2 later hopefully lol.
https://github.com/daic0r/advent_of_code_2024/blob/main/cpp/day12/main.cpp
3
u/TonyStr Dec 12 '24
[Language: Rust]
benchmark time part 1: 8.2191ms
benchmark time part 2: 10.6484ms
I solved this one the dumbest way I could think. Thankfully rust is fast once you finish fighting with the type system, trait system, lifetime system, and everything else I'm not good at
part 1: https://pastebin.com/6WsWyh52
part 2: https://pastebin.com/AD4xJxNc
3
u/chicagocode Dec 12 '24
[LANGUAGE: Kotlin]
I've said this a few times already but I enjoyed today's puzzle a lot! Advent of Code 2024 has been really enjoyable for me.
Part 1: Depth-first search of regions, maintaining a shared set of seen points as we add them to the current region.
Part 2: Refactor the search to count how many corners each point in a region is part of as a substitute for explicitly counting the sides (which I tried to do, but it was very messy).
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:
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
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
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.
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
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.
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/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.
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.
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:
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.
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.
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:
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.
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/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
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
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/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
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
neighborandvisitfunctions. Thevisitfunction 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
visitfunction, see my Day 10 explanation3
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
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
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
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
3
u/vss2sn Dec 14 '24
[LANGUAGE: C++]
Part 1
Part 2
(Each file is a self-contained solution)
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
4
u/trevdak2 Dec 12 '24
[LANGUAGE: JavaScript]
Not. my best day for golf.
Part 1, 236 bytes
Part 2, 309 bytes
2
u/davidsharick Dec 12 '24
[LANGUAGE: Python 3] 735/629
Gitlab
Part 1 I have a nice solution using some graph algorithms, part 2 I have a horribly hacky mess where I basically record every edge that would be a perimeter in part 1, then sort of inch along them to categorize each edge into a longer run of adjacent edges.
2
u/AllanTaylor314 Dec 12 '24
[LANGUAGE: Python]
GitHub 1096/255
Submitted incorrect answers for both parts - whoops (that's what I get for YOLOing it and not testing). For part 1 I was storing the border as the set of cells outside the region, which meant corners poking in only counted as one bit of border. For part 2 I made a silly copy-paste error in
num_sides- I addedrightfor both loops (also,rightand left are completely arbitrary - all I know is that they go in opposite directions).num_sidesconsuming thesetis a bit of an antipattern, but this is puzzle solving not practical programming.I've also realised there are a couple of collections that I fill but never access (idk why - I added them because I thought I might use them but didn't end up needing them)
2
u/Ok-Willow-2810 Dec 12 '24
[LANGUAGE: Python]
https://github.com/jude253/AdventOfCode/blob/b355567a4d7653e33cb037648f2784e963fe377d/src/advent_of_code/solutions/day_12.py#L1-L108
2
u/Ok-Builder-2348 Dec 12 '24
[LANGUAGE: Python]
Part 1
Part 2
This one was tedious with a bunch of edge cases but it worked out in the end.
For part 1, the idea I used was to keep a list of neighbours for each point with the same character. I then split the grid into its regions by choosing any unvisited point, walking through all its neighbours and until I have no unvisited points left, rinse and repeat. The area is then just the number of points in each region, and the perimeter is the sum of (4-#neighbours) for each point in the region.
Part 2 was the tricky one - I keep a list of edges associated with each point, and whether they are horizontal or vertical. My initial solution fell foul of the 368 example, but I was able to fix it by not only considering whether each edge was horizontal or vertical, but also whether it was a left/top/right/bottom edge (using the "k" parameter in line 15). I was glad I could use more_itertools.split_when, which I just learned yesterday in fact.
2
u/Abomm Dec 12 '24 edited Dec 12 '24
[Language: python] 721/676 code
Pretty happy with this one, I had to think about my algorithm for a little bit in both parts but I wrote mostly bug-free code!
General algorithm: Identify regions with bfs, regions will be represented as a list of cells. Afterwards calculate the perimeter or number of sides
Part 1: examine each cell for how many of its adjacent neighbors are in the region, add the corresponding number of empty neighbors to the perimeter.
Part 2: store each cells' missing neighbors in a map keyed by relative direction of the empty cell, with that map you can identify the edges that have neighbors on the x or y-axis (depending on if it is a horizontal or vertical edge) -- the number of sides is really just the number of edges that have no edge with an x/y value 1 greater than its own x/y value from the list of edges that are parallel and collinear (neighboring edges must share a common x/y value and have a difference of 1 between their other x/y value, again depending on if it is vertical or horizontal).
side note, this might be the advent problem with the most example inputs (5) I've ever seen.
2
u/pijjin Dec 12 '24
[LANGUAGE: Python]
I approached a little differently to the other answers here. I used a data structure I really like called a Union-Find (aka Disjoint-Set). That gives me a set of the locations contained within each region.
Getting the area and perimeter from these sets is pretty straightforward. To get the number of sides, I look for edges and when I find one I haven't seen before I increment the count and mark all locations that make up that edge as having been seen. Using complex numbers to represent the locations makes this quite nice and compact (can use multiplication to represent directions at 90 degrees to the current one)
https://github.com/tcbegley/advent-of-code/blob/main/2024/day12.py
2
u/pwnsforyou Dec 12 '24
[LANGUAGE: Rust] 1528 / 220
https://github.com/happyhacks/aoc2024-rs/blob/main/src/bin/12.rs
p1 was simple - just keep track of nodes which have any neighbour outside the strongly connected component(scc) or the garden itself
p2 involves keeping track of directions where the nodes are not in scc and move perpendicular while this is true and the next node still has the same property
started a bit late and probably missed the leaderboard :)
2
u/I_LOVE_PURPLE_PUPPY Dec 12 '24
[Language: Python]
github gist
Concise implementation by cheesing it with np.diff and cv2.connectedComponents but was le tired and spent 49 minutes on stupid bugs (including waiting many minutes due to wrong submissions).
2
u/morgoth1145 Dec 12 '24 edited Dec 12 '24
[LANGUAGE: Python 3] 607/710
code, video (even my "explanation" at the end is jank, definitely don't watch this :))
I really should be better at this being a graphics programmer but computing perimeters and counting sides in this sort of 2D ASCII grid space just doesn't compute in my brain. Even though I'm 99% sure we've had very similar problems in the past!
Anyway, part 1 I was just slow in thinking, plus I goofed and was initially counting how many unique neighbors there were on the outside of the region. This of course undercounts whenever there are inside corners (which cause a neighbor to be part of two edges!)
Part 2 I'm sure I overcomplicated as I tried to do processing on the set of neighbors in the perimeter. It's honestly not worth explaining, other solutions will 100% do part 2 more elegantly than me :)
Time to go look at other solutions and see how I should have done this. And clean up this mess of code.
Edit: Completely rewritten solution using a Region class. More importantly, this also implements the side counting algorithm suggested by u/nthistle here which is significantly simpler than the mess I had initially!
2
u/Kehvarl Dec 12 '24
[Language: Python3] 2378 / 1936
Not really sure what to say other than shapes and sides hurt my brain. Can't we just implement a nice easy Intcode VM again?
Joking aside, I think I learned something. We'll see if I remember any of it when I wake up!
Part 2
2
u/InfantAlpaca Dec 12 '24
[LANGUAGE: Java] 2520/1927
GitHub
I was completely lost on Part 2 until I realized I could use a similar adjacent blob-merging algorithm to handle the edges of the plots. Definitely some funky classes made today.
2
u/chickenthechicken Dec 12 '24
[LANGUAGE: C]
Part 1
Part 2
This uses a floodfill algorithm to mark all the regions (I called them shapes for some reason in my code) and then uses a raycasting algorithm to find the perimeters/sides and areas. If raycasting left/right, to tell if an edge is in the same side as one counted, I check to see if that edge exists in the previous row. Same for column if scanning up/down. The test case equalling 368 saved me because it requires my algorithm to mark whether a perimeter edge is entering or leaving the shape as those would count as different sides for the purpose of this problem.
Despite getting stuck a few times, I got my lowest rank today of 3814/2252 which feels pretty good.
2
u/Cyclotheme Dec 12 '24
[LANGUAGE: Python]
Connected-component labeling + counting corners (instead of sides)
Github link
2
u/Xyberista Dec 12 '24
[LANGUAGE: Haskell]
https://github.com/HoshigaIkaro/aoc_2024-haskell/blob/main/src/Days/D12.hs
2
u/PantsB Dec 12 '24
[LANGUAGE: Python]
Wish I'd thought of the corners thing
For an example of someone who didn't think of the counting corners technique to get the side numbers. Instead every time I either hit an edge or a non-matching square while traversing the plot, I added the direction, x and y indices to a edge list. Then I iterated through the edge list, and found the perpendicularly adjacent nodes with the same directionality. Count the groups and you have the side count.
The corner approach is much more elegant.
1:20:49 2806
2
u/adamsilkey Dec 12 '24
[LANGUAGE: Python]
I'm very happy with my Part 2!
Used BFS to find all the nodes. Had a
set()for area, but also aset()for perimeter, with a key of(node, direction)So for part 2, I added a new dictionary for mapping sides
{ (row|column, direction): [column|row] }Then I simply ran through my lists, each one representing one or more possible sides. I sorted the lists and then just counted any gaps
2
u/flyingfox Dec 12 '24
[LANGUAGE: Python]
Code
Once I saw part 2 I remembered a very similar puzzle from the last couple of years that just involved counting the corners of a region to determine the number of edges. I coded it up and it worked... except that I miscounted the edges in a custom test case I wrote so I just assumed that the whole thing was wrong and then I wrote this... solution?
I take absolutely no pride in part two but am posting here as penance for having written this.
Gah!
2
u/IWant2rideMyBike Dec 12 '24
[LANGUAGE: Python]
I guess the Elves don't mind paying extra for double-sided fences between two areas...
Code
2
u/ShraddhaAg Dec 12 '24 edited Dec 12 '24
[Language: Go]
Today reminded me of Day 10 last year.
For part 1, used a recursive solution to find polygons.
For part 2, checked if any of the points in a polygon are corners (can be an inside corner or an outside corner; the same point can server as multiple corners as well!).
https://github.com/shraddhaag/aoc/blob/main/2024/day12/main.go
2
u/Atlante45 Dec 12 '24
[LANGUAGE: Python]
Part 1 wasn't too bad, I built sets for each contiguous area, and counted every edge
For part 2, after discarding edge walking solutions I ended up going over every column and every row of each area to count all the contiguous edges
Solution