Advent of Code 2023 part 5
Intro
From now on, I’ll be doing the problems one day at a time, as the difficulty of these last few days was quite high, and there’s more to explore. Also continuing the trend of showcasing other cool AoC works, https://golfcoder.org/2023 is a code golf site where the goal is to minimize the number of tokens your solution uses to solve a given day. Interestingly, some language seem impossible to judge by this standard though, e.g. parsing Perl is equivalent to solving the Halting Problem.
As a reminder, if you wish to reference my solution, you can find all my solutions at https://github.com/abnew123/aoc2023 .
Day 21 (Step Counter)
I debated a bit on whether to release this in order as I actually relatively dislike my current solution (it works, and likely works on all Day 21 inputs, but it’s relatively slow). However, I did place quite well this day, so I feel there still is quite a bit of AoC theory to discuss at least, even if the code isn’t the most pristine thing in the world.
But before all that, let’s talk about the day itself. The plot is that the elf starts off in a small garden, and wants to walk 64 steps. Then suddenly, that is actually his perfect square + perfect cube list (can’t fault him, as a math nerd I don’t know why I don’t have one). Casually he then pulls out the fact he needs to walk over 25 million steps today, which is truly impressive as I believe that’s more steps than I’ve walked for the past decade.
From the problem description alone, this is clearly a graph problem. For part 1, I set up a very simple loop to get to 64 steps, where I manually calculate via BFS all squares reachable and what squares those are in a 2d array. The solution is then a simple for loop.
However for part 2, two issues arise. One is that the grid repeats infinitely so there’s no longer a clear (0,0) point, and arrays hate negative indices (at least in Java, Python lists seem to be perfectly content). The other is that any array would need to be at least 25 million by 25 million, which gets you very fun Out Of Memory Errors (if every square is a single byte, we’re at 625 terabytes for the array…). So, the solution I generally use is to switch from an array to using a list of coordinates (this also tends to be my solution for things like flood fill, where the max number of coordinates to iterate is fixed, but the number of passes through an array is not as simply bounded).
The key here is that the grid is square (131x131), and the input has no blockages in either it’s outer ring or the row and column that the elf starts at. This means that the elf can always reach the next copy of his garden in 131 steps, so things repeat at a similar rate. Due to the fact that parity matters (you can never reach a odd parity square in an even number of steps), you actually need 262 steps to repeat, but that’s not too bad (262x262 is only around 70k vs the 625 trillion from before). If you are curious, here is my chicken scratch as I tried to find the pattern:
Definitely a lot of misfires between trying some incorrect cycle sizes early and then mixing up first and second derivatives, but I think that’s a pretty truthful image of later AoC days. It can take some initial wrong ideas before landing on the right track, and even spending over an hour on this, I was still on of the first few dozen to successfully implement the idea. It’s often not the most brilliant single stroke of genius that cracks a tough problem, but repeatedly wearing it down by methodically trying different thoughts.
A final thought, like other days, some people were upset that you can do rely on properties of the input to solve the problem. I think it’s definitely debatable how much that adds vs having everything in the problem description, but this is not a rare AoC thing. Basically every year, there will be certain problems that rely on the input being specifically crafted to be solvable. So as a general tip, on harder days, I’d always recommend at least briefly scanning the given input for special properties that you can exploit in your code.
Times
To read this, left to right is “Day”, “Part 1 time”, “Part 1 rank”, “Part 1 global points”, “Part 2 time”, “Part 2 rank”, “Part 2 global points”.
My best day of the whole year! I already tend to do better on part 2s, and the fact this was quite math heavy definitely played to my strength. Very happy to get another leaderboard placement after day 5.
Run time:
Part 2 is unfortunately still very slow despite not being a brute force to 25 million steps. It’s still simulating a large number of steps (262 * 2 + 65), so there’s definitely a lot of room for improvement here. Currently clocks in around 1.7 seconds, bringing to total to 3.5 seconds.