Days 16 & 17 - My Brain Hurts
Subscribe to Monday Morning Haskell!
The last couple days (Day 16 & Day 17) have been extremely rough. I finally got working solutions but my code is still quite messy and inefficient, especially for Day 16 part 2. So I won't be doing detailed write-ups until I get a chance to try optimizing those. I'll share some insights for each problem though.
Day 16 Insights
This is a graph problem, and my immediate thought was, of course, to use Dijkstra's algorithm. It's a bit odd though. I treated the "cost" of each step through time as the sum of the unreleased pressure. Thus our search should be incentivized to turn off higher pressure valves as quickly as possible.
At first, I tried generating new graph states for each timestep. But this ended up being waaay too slow on the larger input graph. So I simplified to pre-calculating all distances between nodes (using Floyd Warshall) and limiting the search space to only those nodes with non-zero flow. This worked well enough for Part 1.
However, this solution appears to break completely in Part 2, where we add a second actor to the search. Each actor takes a different amount of time to reach their nodes, so running a simultaneous search is extremely difficult; there are dozens of cases and branches because of the possibility of an actor being "in between" nodes while the other reaches its valve, and I wasn't confident I could make it work.
What ultimately got me the answer was the suggestion to bisect the nodes into two disjoint sets. Each actor will then try to maximize their score on one of the sets, and we'll add them together. This sounds problematic because we need to then consider an exponential number of possible bisections. However, the number of non-zero flow nodes is only 15.
We can then exclude half the bisections, because it doesn't matter which player goes after which set of nodes. For example, if we divide them into {A, B} and {C, D}, we'll get the same result no matter if Player 1 is assigned {A,B} or if Player 2 (the elephant) is assigned {A, B}.
This leaves about 16000 options, which is large but not intractable. My final solution ran in about 30 minutes, which is very far from ideal.
On reddit I saw other people claiming to do exhaustive searches instead of using Dijkstra, which seemed strange to me. Perhaps I missed certain opportunities to prune my search; I'm not sure.
This is also a very reward-driven problem, so machine learning could definitely be used in some capacity.
Day 17 Insights
This problem involved writing a sort of Tetris simulator, as blocks fall and are blown by jets until they land on top of one another. The first part was tricky, with lots of possible logic errors, but I eventually got it working, correctly simulating the height of 2022 blocks falling.
Then in part 2, we need the height for one trillion blocks. Not only is this too many iterations to run through a simulator doing collision checking, it's too many to iterate through in any sense.
The trick is to look for some way to find a cycle in the resulting structure. Then you can use some math to figure out what the final height will be. I naively thought that the structure would be kind enough to reset at some point to a "flat" surface like the beginning in conjunction with a reset of the pieces and a reset of the jet directions (a trillion iterations seemed like a lot of opportunities for that to happen!).
However, the secret was to look for the pattern in the delta of the maximum height with each block. So I ran about one hundred thousand iterations, got all these values, and deployed a cycle finding algorithm on the results. This algorithm is a variation on the "tortoise and hare" approach to finding a cycle in a link list. Within the first few thousand iterations, it found a cycle that lasted about 1900 blocks. So I ended up getting the right answer after a lot of math.
Conclusion
As I said, I'll try to do more detailed write-ups once I take another look at optimizing these problems. But for now I have to focus my time on solving the newer problems!