https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2023 day 21> :thread:
# advent-of-code
a
advent of code intensifies 3
j
Part 1 was pretty easy, but part 2 is cycles over cycles
Also the elfs reach brutal step counts, I'm not sure if that number is feasible for humans
t
I hate these cycle-finding tasks 😕
I found the number of steps after which the cycle starts + the cycle length (in terms of steps). But I'm having trouble calculating it into number of plots.
d
Isn’t it either on/off with a cycle of 2 for most inner positions at some point? I.e. once reached the next step exits the point again, but the step after you can be back at your original position. So once marked it’s either on/off % 2 and we only have to calculate the points with the largest Manhattan distance which can be reached with 
26501365
steps… (Just thinking out loud)
after-50-steps.txt
after-50-steps.txt
Looks like it… (☝️ is after 50 steps on the example input)
My head hurts 🤯
p
I found a clue! 💡
😵‍💫
d
It’s a repeating diamond?
p
Yes! I don’t know how exactly we can utilize that but I’m super sure we can
d
Nice!
See at what step it is saturated?
b
is it centered on S?
p
Yep
d
I don’t think the two diamonds are exactly the same though… 🤔
p
Wait, two diamons? where is the second?
d
Well, the one in the middle, and the one you can construct from the four corners… are they the same?
They’re not, because of the blank lines on top/bottom, left/right. Maybe just the fact that there’s a nice chasm in-between is all we need.
w
So my reasoning is all locations which are reachable within (stepCount % 2) == (targetStepCount % 2) are part of the result set. Haven’t found a way to translate that insight into a solution for part 2 yet. (it does work for small sample sizes). I’m not really sure about the cycle part since the space is not really restrained. It feels like there should be some N number of grids that will be completely filled with some left overs. Using the above odd/even rule you know for sure which spaces can be filled and which can not.
d
Yeah, so maybe calculate after how many steps a block (or these diamond shapes) are fully saturated with flip/flopping blocks. The hard part is the outer points of course. There must be a max shock wave, with all n % 2 steps behind also being reached at that step.
bloody hell 🤯 need ☕
w
Definitely hardest one thus far for me.
d
The expanding shape of course is also a diamond shape…
What if we detect after how many steps it crosses the NSEW barrier…
I.e. the repeating diamonds create a larger set of diamonds which composite is also diamond shaped again (after 
26501365
steps)
Also notice that the line with S is completely free of 
#
east/west.
My input size is 131x131
26501365 % 131 = 65
So after 26501365 steps we are exactly on the border…
I’ll do 65 steps on the input, see what that looks like (i.e. if the north/south borders are also reached and the main exit points)
Yes it does!!!
✅ 1
That’s it!
after-65-steps-of-real-input.txt
after-65-steps-of-real-input.txt
Trying to find deduce answer manually first 😉
m
I found a logical cycle that repeated in a sense, but I couldn't get my head what state I needed to keep track off to deduce my information from
alas its worktime, so gotta finish it later
d
So close…
t
I actually managed to calculate some answer (by tracking all "cloned" fields and checking point count in every such field after every full cycle). It's like a numerical sequence so I prepared a formula for it but the answer turns out to be wrong 😞
e
The more important observation is not the line of S is empty, but that there is a diamond of free cells at a distance of 65. After every 65 + 131*n steps we reach larger and larger diamond, and that number is how the target number of steps looks like.
d
Exactly
I’ve got another hint, but don’t want to spoil it
e
At every 65 + 131*n steps the structure is very regular. It is composed of just 4 different kinds of small diamonds. Their distribution depends on the parity on n. The target n is even.
👍 1
So, once you simulate to step 65 + 131*2 you have all info to extrapolate it to the answer.
m
Interestingly, I did find an alligned solution to this math. My state was a set of points as if they were in the original grid (if x = 20 on width = 15 -> x = 5) I then found a point when this state aligned, and also found a point when this state aligned again. For the example input this was iirc 39 -> 50 -> 61 Since the score of the output is itself + the previous, the result is quadratic, I then did some manual math and found the correct solution
👍 1
t
I did it! blob smile happy It turns out my approach of finding the sequence was correct but I had a bug elsewhere (when checking if it's a rock for negative points). But my solution is not versatile - I prepared a math formula out of console outputs 😬
m
now to code it out at some point
d
I.e. I’m inspecting 3 points in time: • Step 65: The size of the full diamond shape (depicted here) • Step 65 + 131: The flip-size of the full (initial) block • Step 65 + 131 + 1: The flop-size of the full (initial) block With that information, and some deduction about the number of blocks, you can calculate the result.
e
26501365 steps -> 20194.040 km very impressive
kodee walking 5
m
In the end pretty straight forward, but took me a while to get there: https://github.com/fabmax/aoc-2023/blob/main/src/main/kotlin/day21/Day21.kt I took a less sophisticated approach and simply compute the counts for each possible map configuration (there are 14 of them) and multiply them by their number of occurrences
m
finally got around finishing this up after doing wolfram shenanigans this morning: https://github.com/mdekaste/AdventOfCode2023/blob/master/src/main/kotlin/day21/Day21.kt My code works for any index request, not just those perfectly round ones.
c
Part 1 I used Dijsktras to calculate shortest paths and return the count of them that were an even number. Nice and easy. Part 2 nope.
b
yea i definitely needed help for p2, but i've since found 3 separate solutions. they're all geometry/math based
r
Part 2 - 🤯
e
very ugly but I have no time or energy left to clean it up now. maybe later
skimming through the conversation, I seem to have taken a totally different approach than everybody above
🤯 1
e
@ephemient what is your different approach?
e
assuming that the input has non-
#
around the entire perimeter (`require`d by my code): • that forces all the horizontal and vertical edges extending away from the origin to have strictly linearly increasing distances from 
S
, fully determined by the corners of the origin tile, e.g.
Copy code
#.#..#.#..#.#      #.#76#.#67#.#
           .............      98765...56789
.....      .............      87654...45678
.#.#.      #.#..#.#..#.#      #.#..#.#..#.#
..S..  =>  ......S......  =>  ......S......
.#.#.      #.#..#.#..#.#      #.#..#.#..#.#
.....      .............      87654...45678
           .............      98765...56789
           #.#..#.#..#.#      #.#76#.#67#.#
• which in turn forces the distances in the tiles in each quadrant to be strictly determined by their offsets • the tiles along the X and Y axes are not so convenient, but eventually their contents also converge to being a linear increase • if I know that a particular plot in a particular tile is at distance d, and the same plot in the next tile is at distance d+x, then d+2x, and so on, I can calculate how many tiles will contain this plot on a walk of distance N (easier with the additional assumptions that the tiles are square and have odd side-length)
I also just realized that this uncovered a bug in my custom PriorityQueue implementation, which I only use on non-JVM platforms, while I do most of my testing on JVM… oops. at least that wasn't too hard to fix
I think I did a better job of structuring my Haskell code than my Kotlin above, https://github.com/ephemient/aoc2023/blob/main/hs/src/Day21.hs
d
You’re doing all puzzles in Kotlin, Haskell, Python and Rust?! 😳 Where do you find the time Daniel?
n
I had hoped to do all of this year's AOC spoiler-free, but this problem defeated me. Even after looking at the solutions here I was still flummoxed. If you are having trouble and are ready to be spoiled, I highly recommend reading this explanation that breaks it down to high school-level math. It's amazingly clear. https://github.com/villuna/aoc23/wiki/A-Geometric-solution-to-advent-of-code-2023,-day-21
Before I started cheating I did not see the clear path through the middle (I thought we had to beeline to the edges). Also, I saw the diamond shapes when I printed the layout, but I was so far zoomed out that I assumed they were aliasing artifacts of my display!
e
yeah I finally had a chance to look at some other peoples' solutions. it turns out I solved a slightly more general problem than "necessary"
b
That solution is pretty neat, but the simplest one i've seen so far is just doing a polynomial fit to a quadratic equation with points on the boundaries
e
yes, the given inputs (and constant) are constructed such that it works, but not in general, and not for the example given either
n
That solution is pretty neat, but the simplest one i've seen so far is just doing a polynomial fit to a quadratic equation with points on the boundaries
Simplest maybe in the sense of most direct or most elegant, but I don't understand it, and this certainly doesn't help me.
52 Views
Open in Slack
PreviousNext
Powered by