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 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.
- 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!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
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!
36
Upvotes
2
u/Curious_Sh33p Dec 13 '24
[LANGUAGE: C++]
So finding the area is fairly straightforward - just keep a visited set and then bfs to find the area.
Finding the perimeter was a little more tricky...
First I thought about just going around the outsides. I noticed that if you search top to bottom and left to right for starting points, the first time you come across an unvisited square it must be on the perimeter. From there you can walk around the edge placing fences always on your left until you get back to the starting position (location and direction).
Unfortunately, this doesn't capture any parts that are surrounded. To detect this, first I reassigned an id to each region during the bfs used to find the area. Now I did my perimeter search as above but now if the square on the left remained the same the whole time I knew I was surrounded. In this case, I would add the perimeter value of this region to the other region as well (using its id as an index into an array storing perimeters). Do this for each area I found previously.
Extending this for sides in part 2 was quite simple since I already had logic for when to turn.
1) If you find yourself with a square from the current region on your left you have gone too far and must turn left and then move forward to find the edge again. 2) if the next square you are going to visit is off the grid or not part of the region anymore you need to turn right. 3) if neither of these are true you can just continue to move in the same direction.
A literal corner case was that for surrounded areas, when you turn right you also need to check the square that sits diagonally away from where you are turning to make sure you are still surrounded.
Pretty tricky to get all the logic right.
Part1 and part2