Advent of Code 2024 Day 12

[@CAG2]

Looks like part 2 got the better of the LLMs (:
all the people I'm used to seeing on the leaderboard (including you!) are suddenly there again

[@klif_n]

I appreciate your explanations. Hope you get better soon. That cough doesn't sound good 🙁

[@joshualee6687]

For Part 2, I worked based on the fact that the number of vertices = number of sides.
For each region:
1) I masked array into 1s and 0s.
2) I padded the full array on all four sides with 0s (in case there are vertices at the array edges).
3) Convolved a 2 x 2 box down the rows and across the cols starting from the gridbox to the top left of the upper leftmost gridbox for each region.
4) The number of vertices can be computed using the convolution (i.e., if non-zero values in 2 x 2 box is 1 or 3, then there is a vertex, if non-zero values is 2, there are two vertices only if they are diagonal placed).
Hope this is somewhat useful

[@hugocardoza3574]

Can you show the code? I did something similar but I was afraid of counting twice the cases with 3

[@joshualee6687]

​@@hugocardoza3574It won't be a double count if your 2 x 2 box is different, as the centre of the 2 x 2 box will be for a different vertex. For example:
a a a a
a b b a
a a a a
When convolving for region b you have six 2 x 2 boxes:
a a a a a a a b b b b a
a b b b b a a a a a a a
of which there are only 4 vertices, no double count.

[@umairgillani699]

Get well soon Jonathan. You are my favorite competitive programmer

[@treelibrarian7618]

I think I had a simpler method overall... still bfs/flood-fill for region discovery, but calculated both the perimeter and sides on the fly during the search.
part a perimeter was simply "if (square in direction) same as self, add to search queue, otherwise increment perimeter.
part b sides: instead of simply incrementing the perimeter length I set bits for up-down-left-right being edge in a shadow map (second array, that also acted as the "seen"). I then took the bitwise or of the left and right bits for the up and down squares, and the up and down bits for the left and right squares, and used that as an inverse mask on the bits from the current square before counting the remaining bits. basically excluding continuing edges from neighboring squares from the edge count of the current square. whoever is the first on that edge gets the count.
thinking about it, there's nothing in this method to exclude a double count if the bfs hit a side in 2 places separately, but I got the right answer so I guess it all worked out OK...

[@nitekat1124]

hey hoping you get well soon

[@gsainsbury86]

My solution involved implementing something similar to what you described towards the end of following along the edges but I got caught out when a line continued as the inside edge of one side and the outside of another. I ended up looking for a hint on the subreddit and saw the idea to count corners which is equivalent to counting sides.

[@rastislavsvoboda4363]

nice, congrats!
for p2, I did something like this:
for every row, I checked prev and current row
I counted as "edge" when only pre xor current was "in region" and if was different on prev column
similarly for cols
def get_sides(reg):
s = 0
rt = min([r for r, c in reg])
rb = max([r for r, c in reg])
cl = min([c for r, c in reg])
cr = max([c for r, c in reg])
# go by row
for r in range(rt, rb + 2):
p1 = False
p2 = False
# go by col, check cells on prev and current row
for c in range(cl, cr + 1):
x1 = (r - 1, c) in reg
x2 = (r, c) in reg
if x1 == p1 and x2 == p2:
continue
if x1 != x2:
s += 1
p1 = x1
p2 = x2
# go by column
for c in range(cl, cr + 2):
p1 = False
p2 = False
# go by row, check cells on prev and current col
for r in range(rt, rb + 1):
x1 = (r, c - 1) in reg
x2 = (r, c) in reg
if x1 == p1 and x2 == p2:
continue
if x1 != x2:
s += 1
p1 = x1
p2 = x2
return s

[@MarkMusante]

Get well soon! Wish there were some way of getting the LLMs banned from the leaderboard :(

[@h0td0g]

damn the cough sounds bad. how you get well.