https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2022 day 17> :thread:
# advent-of-code
a
d
I guessed there would be some memoization in this one. Glad that hunch paid off!
s
Anyone else getting 3010 instead of 3068 in the test example? The results I get seem to be in line with the example, as far as it goes, but at some point they seem to diverge.
j
oh man had to debug so much, still not done with part1
m
Finally finished part 2, I kept getting a wrong answer, turns out I had an off by 1 error the entire time, the correct solution was just 1 higher than I was submitting. 😄
b
wild, I made it this far just to have a wind issue 😄
Copy code
[ ,  , #,  ,  ,  , #]
[ , #, #, #,  ,  , #]
[ ,  , #,  , #, #, #]
[ , #, #, #, #,  ,  ]
[ ,  ,  ,  , #, #,  ]
[ ,  ,  ,  , #, #,  ]
[ ,  ,  ,  , #,  ,  ]
[ ,  , #,  , #,  ,  ]
[ ,  , #,  , #,  ,  ]
[#, #, #, #, #,  ,  ]
[ ,  , #, #, #,  ,  ]
[ ,  ,  , #,  ,  ,  ]
[ ,  , #, #, #, #,  ]
j
I'm confused by the stop condition for part1 are the elephants asking for after x of the shapes landed or x of the single rocks the shapes are made out of?
s
x of the shapes landed
r
PART 1: I keep getting 
2569
for the given example, not 
3068
like it says, but looking at a visualization, it matches theirs. Anyone else getting the same?
j
found my problem for part1 instead of only stoping a shape simulation when it landed i stop it immediatly after going down 😅
s
@rkechols I had a similar issue. The bug I had was, when I tried to move the figure down, I only checked if its last line overlaps with what's already in the bucket. You need to always check the whole figure for overlapping.
r
Turns out my problem was that I was taking the height of the top of the just-landed shape as if it were the highest point on the canvas. However, it's totally possible to drop in a piece down the side, falling much lower than the actual highest piece
s
For part 2 my only idea so far is to remove lower parts of the tower once they are completely covered up by the higher parts. But running the full simulation is apparently too slow anyway.
j
@Sergei Petunin yeah it smells like some cycle detection
s
If we have x figures and y different values in the jet pattern, then after 
gcd(x, y)
the process might seem to repeat itself. However, the state of the bucket might be different at that point, so I still don't see how we could reuse the results.
j
I'll take a walk to clam down and maybe get an better idea for part2
n
would be nice if we would get a solid line after a shape landed. Then we would have found a pattern. However, so far I did not find such a case.
actually not true: the gas must be sync'ed as well at that point. So likely not a working idea.
s
Yep, theoretically you know when you've found a cycle when you have the same figure, the same position in the gas array and the same state of the bucket underneath down to some level.
Actually a bit easier, you have a cycle when the same figure has landed at the same horizontal position and you're at the same position in jet array
d
there’s got to be a cycle but haven’t found it yet
e
I failed at basic arithmetic so many times… but I got it in the end
j
At least I managed to get part1 done some time ago: Day17 uses Chamber.
p
s
Done with part 2. The idea is to 1) remove lower parts of the tower once they become inaccessible (via BFS) and 2) make a snapshot of the current state and skip the loop once we see the same snapshot again. Also, BFS on bitmaps was fun 😄 https://github.com/forketyfork/aoc-2022/blob/main/src/main/kotlin/year2022/Day17.kt
j
Btw is there a good graph library for kotlin, so I do not have to implement my own Graph every time. Would be nice if it had bfs, dfs, and dijkstra too
p
Well that was fun. Went for a cycle-detection approach for Part 2, then just calculate the full height from the height increase of each cycle, the base of the tower and any extra rocks thrown on top. https://github.com/tKe/aoc-22/blob/main/kt/src/main/kotlin/year2022/Day17.kt
I had to create a key from the top 8 rows of the cavern to detect the cycles, but luckily I was using bytes for each row so it became a simple case of turning the top into a long and tracking that with the offset through the gas cycle.
Writing a 
parseGas
function made me giggle.
n
How do you know how many rows from the top of the chamber you have to look at for cycle detection? I am thinking that if the leftmost column is never filled until the very last shape and very last gas, it could fall though the bottom. So the camber height to snapshot seems huge. I guess I'm missing something here...
e
I did similar to Sergei: DFS (or any other search) and only include the bits that could potentially be touched from above
n
ok, so you snapshot the top-of-the chamber outline instead of the whole content. That could potentially still be big if e.g. the rightmost side forms a zig-zag where a L shape could be pushed into every opening. So how did others get away with only looking at the top 8 rows?
j
I have working solution, but my period is 19001 * 7 * 5 * 5 * 5 * 2. The first (19001) is a winds count, second (7) is width of the chamber, third (5) is the number of shapes, but where the rest 5*5*2 comes from? I don’t get it, even if it works and this bugs me…
s
Generally there might be no loop at all, but the inputs are constructed in such a way that there’s always a loop, and it’s not very large. That’s why just looking at the fixed number of previous rows could be enough.
n
So this "8 is enough" is basically a lucky guess that works for the given input? How was this number found then? Trial and error?
p
For me it was a lucky guess that panned out based on double the height of the tallest shape.
d
8 doesn’t work for my input. I put in a check whether the rock y goes below 0, it fires until I retain the top 32 rows.
Well, or I may have a bug. We will see
Yeah, advent of bugs
9 rows works for me. Found by pruning the chamber and seeing at which point rocks stopped falling through y=0
actually on my input I had to increase it to 64 rows. Still worked though, got the answer.
9 was for the test input
ends up simulating 2357 falls total (before and after cache skip)
Copy code
do {
                rock.tryMove()
                check(rock.points.all { it.y >= 0})
            } while (rock.tryFall())
Is how I probed the number
n
for my input (and sample data), just fingerprinting the top 3 rows is enough to produce the correct results. Still feel bad that I don't have a proper reason for picking the threshold.
d
I am not fingerprinting, I’m taking all points (post-normalization), still works
n
what would happen if the bottom of the chamber contains some initial pattern which never repeats? My understanding is that your code would then never find a cycle, would it? Actually also not sure if that could even happen with an empty start chamber.
t
Today was busy for me, but I managed to finish it. It’s more side-effecy that I’m used to writing, but it works. I sure hope you like extension functions! • Blog • Code
r
My cycle detection code works for testInput(both parts) but not for real input (both parts) 😬
I was passing wrong number of max rocks!! Sorry, for the noise.
e
rubber duck
j
the sample input has a cycle within the first 2022 which makes it helpful for testing cycle detection without trying to calculate a trillion
10 Views
Open in Slack
PreviousNext
Powered by