Day 22, can you believe it? Only 3 more days until Christmas! But first, we have to find the friend of someone who may or may not be Santa inside a deep, rocky, narrow, and wet cave system. But do we charge in there blindly and without a plan? No! We are programmers! We need to do some analysis first to evaluate the risk of the area.
This weekend is the last chance to make up some ground against this relentless onslaught of code challenges! Or, depending on your priorities, this weekend might be a perfect chance to get caught up on eating tons of cookies and drinking eggnog. Or both! π
Good luck with this one! Let's see how you do.
Top comments (3)
Ah, a proper coding puzzle again after the last couple of days of drudge-work.
Firstly a data model.
Some might suggest the input data format is so simple you can just use string splits and regular expressions. But if I want to make one point in this Advent Of Code it's that parser combinators always result in simpler, better code.
Previous solutions with 2D arrays have resulted in slightly messy code. Let's factor out the 2D array stuff.
There's one simple insight to part 1, which is that the calculated value for each position depends on the positions above and to the left. So the whole grid can be calculated in a right-then-down or down-then-right order. Let's do the whole thing in an object initialiser:
The descriptions of erosion level, region type and risk level could all be collapsed since there is a 1:1 relationship. But in my experience of building software, if the customer felt the need to describe these things separately, then model them independently. It's lower cost to have each representation in the code and live with the simple mappings than have to mentally remember the equivalences. And it pays off immensely when the requirements change subtly in the future.
Part 1
Part 1 is answered simply by computing the sum risk level for the entire cave.
Part 2
A meaty part 2 today, which introduces a whole new algorithmic requirement. We have to find the shortest path from the start to the trapped friend. Like Day 15 this can be solved with an application of Dijkstra's algorithm. The difference here is that the cost of moving from region to region varies depending on the equipped tool, and indeed in some cases transitions are not possible due to incompatible tools.
First we'll model the tools, the mappings to region types:
Dijkstra's algorithm needs a "current best" value for each position in the graph. This is a product of time and equipped tool. We'll also make some helpers for deriving new states:
The Dijkstra algorithm follows the same basic structure as before:
The difference today is that the cost of moving to a neighbour position is considerably more complex and must take the transition of tools into account. Firstly, we must match the tools available at the current position with the tools available at the neighbour position. Then:
The final aspect of part 2 is that the optimal route may extend beyond the target position. We have no idea how far, but changing tools takes eight times longer than just moving, so the furthest beyond the direct route to the target we might go without changing tools is approximately eight times more. Fudging it a bit and waiting a good old time for the answer:
Sadly this doesn't get me an answer that Advent of Code is happy with. I am seeing a longer path for scale=4 than scale=3, which is strange, and points to the path being dependent on the order that the positions are visited rather than the intrinsic properties of the positions. I'll keep working on this one.
Part1 was easy: translate the definitions into python code and let the memoization decoration do catching for efficiency.
Part2 is an application of the A* algorithm, which I ended consulting in Wikipedia because my recall was wrong and, although I solved the given example, I fail at the problem.
Part 1 wasn't so hard, I basically just followed the description.
Part 2, on the other hand, was quite a challenge. I implemented kind of a priority queue (not the real one, but I knew there wouldn't be almost any gaps between the priorities). I also memoized the geologic index and level functions to speed it up, but it still took a bit over 1 minute.