<Advent of Code 2024 day 12> (spoilers) :thread:

# advent-of-code

[Advent of Code 2023 day 12]

Advent of Code 2024 day 12 (spoilers) 🧵

[Michael de Kaste]

Very fun challenge again, especially like how the challenge of finding the initial groups can be reused again in part2 in finding the sides.

Day 12 Michael.cpp

[nkiesel]

Part 1 was pretty simple, but I struggled to compute the sides for part 2. I ended up with a working and reasonably fast solution, but will have to spend more time tomorrow to think about it more. My code is https://github.com/nkiesel/AdventOfCode_2024 in case anyone is interested.

[Jakub Gwóźdź]

20ms each part

I had fun 🙂

JakubG.kt

[Jonathan Kolberg]

I struggled with counting sides today. Just now got side counting to work

[bj0]

dang i did that one pretty fast (for me), if i hadn't started 1.5 hours late i might have had a non-terrible global rank, alas

[bj0]

i just doggedly walked using a bfs checking conditions on both p1 and p2 and it worked out

[Jonathan Kolberg]

My solution after cleaning up:
https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day12.kt

[Dan Fingal-Surma]

That took way too long

[Dan Fingal-Surma]

Part 1 was easy

[Dan Fingal-Surma]

Part 2 I kept taking wrong turns on

[Jonathan Kolberg]

I was able to solve part two after drawing one of the difficult shapes

[Dan Fingal-Surma]

Part 1 is just fill to get a region, sum (4 - count of neighbors in region) over the whole region

[Jakub Gwóźdź]

oh

[Dan Fingal-Surma]

Yeah I focused on shape C from the example, once I got that then it worked

[Dan Fingal-Surma]

For Part 2 I end up filtering the region to the perimeter. Then for each point in the perimeter, for each cardinal direction is outside the region, I check if I can draw a fence perpendicular to that direction. If I do I add the line to the set of lines for that direction (where a line is the set of constituent points). Then you can count the lines.

[Jakub Gwóźdź]

I calculated correct perimeter on part1 but indeed that was unnecessary, now you mention that 🙂

Although helpful for part2 🙂

[Dan Fingal-Surma]

Working on cleaning it up…

[Dan Fingal-Surma]

Good enough: https://github.com/dfings/advent-of-code/blob/main/src/2024/problem_12.main.kts

[Dan Fingal-Surma]

Nice @Jakub Gwóźdź, I thought about perimeter as pair of point and direction, plus doing something with turns, but didn’t quite get there

[Dan Fingal-Surma]

I think what I end up computing is isomorphic to that

[Dan Fingal-Surma]

Screenshot 2024-12-12 at 12.41.55 AM.png,Screenshot 2024-12-12 at 12.42.04 AM.png

[Luan Tran]

I took like a bit strange reasoning in Part 2: line of fences are just region that are connected only vertically or only horizontally. So I split the region into smaller horizontal and vertical regions. Then I count the number of lines that a line can merge into and I thought that the result would be 2 - that number. But then I realize that a line can also be split by another neighbour line that attach to the middle of it. So the final working formula I cooked up is 2 - merge + split. But the code look horribly unreadable and I'm not sure where to start refactoring it

[phldavies]

I spent far too long trying to debug part2 for the example input as I'd misread the expected result 🤦‍♂️
Advent-of-Reading-Comprehension strikes again!

Warming up 1 puzzles over 5s for year 2024 day 12...
Warmup finished after 5.013797500s with 182 iterations
year 2024 day 12 part 1
	 Default took 12.277708ms 👑: 1381056
year 2024 day 12 part 2
	 Default took 13.564ms 👑: 834828

Day12.kt

[Luan Tran]

Also I don't know if I discovered a bug or I did something wrong, but this code doesn't add anything

var lineCount = 0
lineCount += horizontalLines.sumOf { line ->
    2 - horizontalLines.count { other ->
        other.first().x - line.first().x in listOf(-1, 1)
            && other.first().y <= line.first().y && other.last().y >= line.last().y
    }
    + horizontalLines.count { other ->
        other.first().x - line.first().x in listOf(-1, 1)
            && other.first().y < line.first().y && other.last().y > line.last().y
    }
}

while this one work normally

var lineCount = 0
lineCount += horizontalLines.sumOf { line ->
    val merge = horizontalLines.count { other ->
        other.first().x - line.first().x in listOf(-1, 1)
            && other.first().y <= line.first().y && other.last().y >= line.last().y
    }
    val split = horizontalLines.count { other ->
        other.first().x - line.first().x in listOf(-1, 1)
            && other.first().y < line.first().y && other.last().y > line.last().y
    }
    2 - merge + split
}

[Luan Tran]

Although in my mind I just do the same thing in both versions. I compute the count, then add/minus them to 2

[Max Thiele]

@Luan Tran In your first snippet you have a newline before the '+', which probably makes it a unary plus instead of adding the values together

[Luan Tran]

@Max Thiele ah thank you, that fix it!

[kingsley]

Spent too many hours on day 12 and needed some help with the perimeter function as my original logic wasn't passing with my input. I managed to tidy everything up nicely, but it's sure not my best day

[Luan Tran]

Instead of listing all the fences, I think we can do the math: all plot has 4 fences unless they are adjacent to another plot. So, we can count the number of adjacent plots for each plot and the number of fence that plot has is 4 minus the the number of adjacent plots.

[ephemient]

Day12.kt I didn't have enough time before sleep to finish, but it went pretty well after I woke up early

[ephemient]

I was very confused when one of my test cases kept spitting out the wrong answer… turns out I accidentally used .trimIndent() instead of .trimMargin() in one place

[ephemient]

my part 1: every square has 4 edges ((0,0) = {(-0.5, 0), (0, -0.5), (0.5, 0), (0, 0.5)}) which I represent with doubled coordinates to avoid fractions. any duplicate edge across the group is interior, the perimeter is all the rest

[ephemient]

my part 2: also track whether the edge was encountered on the northeast or southwest side. only merge consecutive edges into one longer one if that is the same

[ephemient]

hacked a bit with using odd keys for vertical lines and even keys for horizontal lines to avoid some duplicate code

[Neil Banman]

This one was tough for me, had to sleep on it, and as per usual I suddenly had the answer to my problem.

[phldavies]

Warming up 2 puzzles for 10s each for year 2024 day 12...
	Default warmed up with 1014 iterations
	FenceWalker warmed up with 1136 iterations
year 2024 day 12 part 1
	 FenceWalker took 3.768015ms 👑: 1381056
	 Default took 3.777930ms (1.00x): 1381056
year 2024 day 12 part 2
	 FenceWalker took 4.885262ms 👑: 834828
	 Default took 5.412263ms (1.11x): 834828

about as fast as I can (be bothered) to get it

Day12Updated.kt

[phldavies]

for some reason, do statement while() without braces surprised me

[bj0]

its interesting how many different ways people found to get sides in part2. i just recursively walked all the things: https://github.com/bj0/aoc-kotlin/blob/main/src/year2024/day12.kt

[phldavies]

@bj0 just had a glance around your repo - seems familiar 🤣

[bj0]

yea, i pulled some of your infrastructure last year, but didn't want to deal with ksp so kinda gutted it 🙂

[phldavies]

makes sense - I just used it as an excuse to play with KSP

[bj0]

i'd like to learn it at some point but haven't had any use cases for it yet so haven't gotten around to it

[bj0]

i also keep making changes based on random conviniences, so i'm sure what i have now is much messier than your original that it started at

[Reece H. Dunn]

Part 2 was tricky but it helped that I kept a track of the walls in part 1. https://github.com/rhdunn/aoc-2024-kotlin/blob/master/src/main/kotlin/io/github/rhdunn/aoc/y2024/Day12.kt

[Reece H. Dunn]

I wasn't able to find an easy sequence way of saying "group by adjacent values", otherwise I could have simplified part of the side logic.

[todd.ginsberg]

Solved Day 12 this morning US time but had a busy day and didn't get a chance to write it up until just now. Part 1 is a Breadth-First Search and Part 2 modifies that to count the number of corners each point is in, as a substitute for the number of sides. Pretty happy with how this turned out. The "how many corners is this spot in" code might could use a bit of a tune-up.

• Blog
• Code

[Dan Fingal-Surma]

Ah yes, side count = vertex count!

[Paul Woitaschek]

I had to draw in order to come up with a solution for part 2 🤯
https://github.com/PaulWoitaschek/AdventOfCode/blob/main/2024/src/main/kotlin/aoc/year2024/Day12.kt

[Josh Soberg]

I'm going down a rabbit hole with this one - has anyone written a solution that detects corners? I was going this route since corners should equal sides, so I thought I could just detect corners (deconflicting matching corners) and return the count; but the last A/B test example is failing for me: https://github.com/jsoberg/2024-Kotlin-Advent-Of-Code/blob/main/src/Day12.kt

[Neil Banman]

Todd Ginsberg 3 comments up said he did just that, plus wrote up a blog post explaining it.

[Josh Soberg]

lol I somehow missed that, thank you!

[Paul Woitaschek]

IMG_20241212_231937.jpg

[Paul Woitaschek]

Make a test case out of this and check if your corner logic screws up on these intersections

[Dan Fingal-Surma]

Looking at Todd’s logic. IIUC the way it works is: Examine each point in the region. For each of the 4 area-4-squares that contains that point, check if either (a) both adjacents are non-matching (outer corner), or (b) the diagonal is non-matching but the adjacents are matching (inner corner).

[Dan Fingal-Surma]

That looks like it computes it correctly (mental computation):

202
0 2
22

[Josh Soberg]

it turns out my corner recognition logic was fine - the issue came in when I was trying to deconflict matching corners. For the A/B example I got a 12 total count (originally thought I'd get many more matches, but 12 is the expected output), but when I flattened the results to a Set it ended up with a count of 11. So I could have just counted detected corners all along haha. Pushed up the changes but it ends up being much simpler. Thanks for the tips!

[Dan Fingal-Surma]

In the pattern:

XXX
XXX
XX

The inner corner gets assigned to (1,1) even though it is not on the perimeter per se

[Dan Fingal-Surma]

basically when you bisect the corner what square is that line pointing at

[Dan Fingal-Surma]

Implemented and verified

[Dan Fingal-Surma]

Much nicer impl

[Dan Fingal-Surma]

Screenshot 2024-12-12 at 2.54.45 PM.png

[Reece H. Dunn]

My solution doesn't use corner detection. My approach is:
1. do a pass that removes touching walls when the plant is the same for two adjacent plots;
2. calculate the plots in a region from part 1;
3. filter the plots in a region that have a given wall direction;
4. group 3 by the primary axis (y for up/down, x for left/right);
5. map values in 4 by the secondary axis and sort;
6. sum adjacent values in 5 for each wall direction (3-5).
The idea here is that considering a given wall face/direction, plots on different rows are in different sides and for the same row any non-adjacent columns form a different side.

[Neil Banman]

My (terrible) method was after the regions are identified, go back and reexamine each plot. Something is a side if a) the facing plot is not in the region; b) either 1) there are no adjacent plots in the region, 2) there are adjacent plots but they have not been recorded during this pass, or 3) there are adjacent plots but there is also an in-region plot diagonally. Complicated, right? I'm not done, unfortunately. This double counts in the case where the search wraps around from both ends and meets in the middle. So any "junction" pieces need to reduce the side count.

Currently refactoring on the corners approach. I had considered it but glibly rejected it based on a concern for a same-plant/different region scenario which is actually impossible when I think it through now.

[Jakub Gwóźdź]

some more fun with Java/Swing/AWT

Day12.mov

[phldavies]

Very fency!