Hello everyone, after completing this year’s day 16 puzzle, I decided to take a break on this for a couple of days. This Monday, I finally got on it. Without further ado, let me tell you all through my Advent of Code 2022 Day 17 cruise log.
What was I doing on December 17th instead of coding? Respawning after a fun poker night at a friend’s birthday brunch that ended up lasting the whole day. That was fun but each of these days I kept remembering that I delayed my completion of the Advent of Code more and more. Not only complexity grew, but also I fell more behind by skipping days. Now here I am, instead of enjoying a chill evening reeling in with a 25-days completioner I am still playing catch up.
Where do I begin this one? Oh yes, Monday afternoon.Since I still want to take things easy, I waited until after my working day to start. As it turns out, my fiancee was feeling pretty tired and went for a nap before our evening together. This gave me at least 30 minutes to take on the puzzle.
From there, it took me a bit to write some code that felt right. Since I didn’t want to spend much time on it, I went and ran the validation test for the first part. No exception thrown but it’s all red. You know the drill, time for some visualisation. Pretty quickly I had code that visually represented the state I should get for each rock drop. In order to make it clearer, I decided to replace the generic #
hash characters with I wrote some code to visually represent what I got but enhanced it to make it clearer than the example by using digits to distinguish rock shapes.
I used that to clearer view to debug what was wrong and eventually got a solution. The first part test passed after 20mn more minutes on this problem. Then, strong with confidence, I went and submitted my answer after executing the code against the real input. No luck here
From there I had a hunch that my side collision detection was not on point so I added a small test that would allow me to detect where a side slide should occur but doesn’t due to my flawed logic. After a few more minutes of this, I got something that passed the test. But my input answer was too low at 3091.
Now I know the range of my answer, it’s between 3091 and 3114. While I could cheat and get the answer by submitting a new one every minute from my lowest bound answer to the highest bound, that would defeat the purpose of doing these puzzles. As a result, I went back to the metaphorical coding board. And yes it has been way over thirty minutes at that point and my fiancee is awake but I decided to complete at least part one before taking a break.
Now determined to wrap this quick, I scrolled through my pretty visualisation and realised that there is a floating rock. Instantly I realise it floats because of my falling condition. As it turns out, I didn’t consider that a rock could fall in a shallow area after sliding into a cavity. From there my validation test passed and I captured that first star.
At that point, I still had plenty time to enjoy the evening and decided to do just that. I figured I would return to do part two in the morning. In the end I didn’t and only returned the next evening, last night.
Then I remembered that I saw a similar shape in that second part. In 2019, December 22nd, on the 22nd day of the Advent of Code. Hoping that I would find a solution in my old code I felt betrayed by past me for giving up. I didn’t not complete that day. I went on the 2019 Reddit and spotted that people mentioned that they solved that problem with a cycle detection algorithm.
What is cycle detection? While I can guess the idea I never, as far as I can tell, implemented such algorithm. At least I had a place to start from, I googled and went on Wikipedia where I found pseudo code examples. From there, I needed to figure out how to represent the data to fit it in a cycle detection algorithm. This bit was tricky but I’ll probably find it easier next time I face a similar problem.
After about an hour, I finally got some code ready to run. And surprisingly, it passed the part two validation test. Unfortunately, when running the code against the real input it hangs. Looks like I need to figure another way. Still, my gut tells me to wait just in case it doesn’t take that long to execute.
My guess is that my rock dropping logic is the bottleneck and takes too long to execute. As I was about to admit defeat just like in 2019, the code returned a result.
Sure it took almost three minutes but I had a good feeling about this. I was right, I captured the star number 34 on that fateful night. I was curious about cycle detection and people saying that it drops every year during AoC.
There is one problem I tackled in the past which feels like it could have used some cycle detection to speed things up. Day 22 from 2020, I even wrote about it. It was that one year where I completed every puzzle by December 25th.
I went back to check that code but no cycle detection in there. Now I wonder if I didn’t need it because the puzzle didn’t require it or because Golang is that much more powerful than Java which I use this year. Maybe I’ll write about that later on.
Thank you for reading my Advent of Code 2022 Day 17 log, I will see you when I see you. If you want to check out my previous entry, you can do so here. You can even read my entries from last year there. As usual, I will push the code to my repo for this year on Github. Also, if you want to test yourself against my AoC 2022 run, I’ve created a private leaderboard. The invite code is 382952-d065ee7a
. Join, if you dare. I say dare but since I’m playing catch up, if you completed everything on time you’re way ahead.
Photo by Pixabay