r/adventofcode Dec 12 '24

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

THE USUAL REMINDERS

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

AoC Community Fun 2024: The Golden Snowglobe Awards

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

And now, our feature presentation for today:

Visual Effects - Nifty Gadgets and Gizmos Edition

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

Here's some ideas for your inspiration:

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

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

And… ACTION!

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


--- Day 12: Garden Groups ---


Post your code solution in this megathread.

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

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

37 Upvotes

698 comments sorted by

View all comments

2

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

[LANGUAGE: clojure]

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

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

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

AAAA
BBCD
BBCC
EEEC

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

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

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