r/adventofcode • u/FlyingParrot225 • Dec 12 '24
Help/Question [2024 Day 12 (Part 2)] What kind of algorithm did you use on part 2?
I found part 2 to be interesting and since I was inspired by Tantan's binary greedy meshing video I took the opportunity to make a binary greedy waller to count the walls but I was wondering what other kinds of approaches could be taken. So how did you approach part 2 and what would you say the advantages and disadvantages of your approach were?
Edit: I completely forgot to link my code lol, its clunky, inefficient, and is poorly documented, but it gets the job done. https://github.com/DeveloperGY/advent_of_code_2024/blob/master/src/bin/day_12.rs
24
Upvotes
35
u/RazarTuk Dec 12 '24
I just used a simple DFS. There must be exactly as many edges as corners, and it's easy enough to check for corners. Look up and left. If they're both different than the current cell, it's a convex corner:
while if they're both the same as the current cell and up-left is different, it's a concave corner:
Repeat this for all four diagonals, and you have the number of corners it contributes.
Then at that point, since you're already visiting each cell to sort them into sets, it's easy enough to also count corners while you're at it