#2024 AoC Day 12
somber harbor
254/51
I had a couple of false starts on the second half
but clearly it was nontrivial for a lot of people
shell pulsar
i know how to do this but im too tired to start implementing part 1
see ya tomorrow
quaint sigil
well, today's was interesting
1790/1008
I love how for both parts, I managed to ||forget to handle the outside border (at the edge of the map) the first time||
shell pulsar
actually ykw if i dont solve it now im not gonna get any sleep at all
quaint sigil
uh oh
shell pulsar
this happened on day 6
i woke up in the middle of the night when i figured out an optimization
narrow mortar
quaint sigil
oh, that's ||a reasonable way to extend part 1||
dusk current
|| i'm very happy they include a sufficient number of test cases to cover the requirements these days; on the other hand they need to because why are these the requirements, this is stupid 😛 ||
quaint sigil
and certainly not what I did 😛
narrow mortar
oh, that's ||a reasonable way to extend part 1||
||yeah, I was just starting to think of ways to group the edges together into combined sides, thinking it was going to be a big pain, might have come up with something like your solution, or something else similarly complicated, but then I realised, we don't need to identify all of the sides, where they are, how long they are... just need to make sure each side only counts once. That realisation was the "seeing through time" feeling I mentioned earlier.||
quaint sigil
nice
I figured ||well, this is an extension of a side (in the obvious way)|| would get me there (and it did)
but I did much more rework
narrow mortar
honestly, if I hadn't seen that trick I probably would've tried something like ||walk around the perimeter to put all the fences in "order", and then count how many times it changes direction... but then I would've gotten caught up on regions with floating enclaves, and it would've been a whole mess||
quaint sigil
||that does sound really annoying||
slim shale
Hmm, part 1 fairly simple.
Part 2, no idea
It feels like something I should know how to do, but I can't think of it
Guess I'll just let it marinade for a while
zinc brook
Part 1: came up with a really great way of doing it ||Graphs, with connected components||
...no idea how to apply that to Part 2...
dusk current
||i calculated the perimeter by doing separate horizontal and vertical passes of going through each line and counting the edges between region and not-region; for part 2 it was a fairly straightforward extension of recording the edge location and direction pairs for the line and not counting ones again if in the same place and direction as on the previous line||
shell pulsar
well i solved part 1
part 2 has completely stumped me though
now i think i'll sleep
coarse escarp
Yeah, I sat back and thought about it for a while, then realized that for part 2 I could ||count samples of each side, so long as I threw out all but one piece on each side.||
That struck me as a lot easier than ||trying to merge pieces into coherent sides||
dusk current
||<https://github.com/mrphlip/aoc/blob/master/2024/12.py>||
|| let's say that list literal in your perimeter2 there has a very somebody-saw-through-time look to it 😛 ||
somber harbor
||<https://github.com/mrphlip/aoc/blob/master/2024/12.py>||
ooh, that's a cool solve
shell pulsar
now i think i'll sleep
okay i figured out a solution for part 2
i absolutely have to sleep now though its 12:35
somber harbor
Nice
broken quarry
Well, that took a couple false starts, which is a little sad because I used to technically work in ||computational geometry. Or at least the rectangle-heavy part of it.|| Still, got there eventually.
broken quarry
That struck me as a lot easier than ||trying to merge pieces into coherent sides...
I took more of this approach, but it's not as bad as it seems because ||you can effectively cancel neighboring sides during the search. The trick is that you then have to account for non-contiguous runs of coordinates which is where I went wrong on my first attempt, using a set.||
I feel like there's probably some elegant ||sweep line|| solution, but I can't recall the details of any of those from memory at all...
slim shale
Ok, got there. Feels a bit brute forcey, but it worked
Time to check what obvious thing I missed in other people's answers 😄
My solve was ||to generate all the fences, then basically doing the same thing I did to search for regions, only grouping fences into sides, rather than plots into regions||
I swear there has to be better way
grim gate
[part 1] This feels like a problem that there is some nice theory to which I know nothing about. ||My first instinct was to try and cut down info by for each region recording where it appeared on the previous and current rows, and accepting stuff based on that doing a l->r,t->b scan, but that breaks the moment you encounter .C CC with the idea being that it can also count fences based on gaps in a row (vertical fences) and differecnes to the row above (horizontal fences)||
zinc brook
oh, the main map is ||a giant 10!||
unique grail
I wasn't confident in a ||trying to identify fence corners|| solution like phlip's, too worried about edge (ha ha) cases.
Instead I did a conceptually simpler (to me) thing where ||I pick a point on the perimeter, then "walk" the side that point is on forwards and backwards, removing all points on the same side from the pool. Then count how many times I did that.||
dull sparrow
part 2 seemed straightforward enough until I realized ||my input has holes in the regions|| and now I'm devastated
it doesn't sound like that was an issue for anyone else?
haven't solved it yet but I have an idea
obsidian olive
I enjoyed today's. Part 1 was pretty standard, but I ran into edge cases with part 2, and I should have looked at the examples more closely because my algorithm failed on one of the examples but since it worked with the other, more complex-looking examples I didn't think about it. Specifically, ||I tried to find all walls facing the same direction, but I did it without taking direction into account, just position and orientation, so it failed on the AB example while passing all of the other examples. To fix it I didn't just sort walls into north/south vs east/west orientations, but instead sorted them by which direction they're facing.|| Then I had a bug in that implementation, where I just got my directions mixed up: ||if a wall is facing north, its neighbours will be east or west, not north or south||. That bug was much easier to find and solve.
My solution is the same as ekimekim's, by the sounds of it.
warm sonnet
Welp I wasted time thinking if there was a mathematical way to do Part 2 ||using the area, perimeter, and number of edges around each point||, then decided to || traverse again around the perimeter, before realising my solution didn't account for holes||. As a last resort || I decided to just collect all the edges during my traversal, promptly forgot about the entire border||, and finally got my second star. What a cursed day.
Also, I had the same idea of ||counting corners, but I still don't get how phlip reduced it to those boolean operations||
shell pulsar
i haven't implemented it yet
it is morning and i have implemented the part 2 solution and it works like a charm
shell pulsar
||i went with a horzontal / vertical edge sweep. apparently corner counting was also a solution and i feel silly because i thought of that but then couldnt figure out how to handle the edge cases||
dull sparrow
I wound up ||ditching maze solving due to holes, and found out that corner counting does work, as long as you account for overlapping corners.|| I hate problems like this, what a pain! glad to have it done
shell pulsar
||i went with a horzontal / vertical edge sweep. apparently corner counting was ...
||for every possible horizontal edge: check if the edge exists, then only increment side count if not the same as previous edge checked (reset after finishing a line)
then do the same for vertical||
definitely not optimized but it works
unique grail
My solution is the same as ekimekim's, by the sounds of it.
I'm not so sure - mine doesn't involve any ||sorting||. I just ||grab an arbitary point, work out what direction it's in (and which side is inside) then walk that edge until it stops||.
obsidian olive
I'm not so sure - mine doesn't involve any ||sorting||. I just ||grab an arbitar...
I often say "sort" when I mean "categorize" or "group". There was no sorting in the computer science sense, only in the colloquial sense.
deep flare
I solved p1 yesterday, but I had to sleep on p2. I like how ||sides()|| turned out but I feel like there was probably a better way to do it.
||I use the visited set of a BFS to find all the plots in a region. That set is passed into sides(), and for each plot I check if its neighbours are within the region or outside it. If outside, I record that edge in a dict of {facing_direction: [edges]}. Next I sort that list of edges by either the x or y coordinate depending on the facing direction.||
||With all my edges collected and sorted, I then loop over each list of edges pairwise, and if any two edges are not directly next to each other I increment the number of sides.||
||https://github.com/StarlitGhost/Advent-of-Code/blob/main/2024/12/script.py||