Note: This topic is to talk about Day 20 of the Advent of Code.
For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.
1 Like
Today was fun. My solution is available here. It runs in about 1s. I have a feeling that the input is not exercising all of the possible edge cases. My first version actually had some errors, but still got me the correct result. I only noticed possible issues when I was tidying up the code. I hope that this final version covers all possible scenarios.
It wasn’t really needed, but for fun I decided to hand-roll a recursive descent parser (see this part).
2 Likes
Today was fun for me, too. I managed to use streams for the path finding part of the problem (loosely based on/inspired by @sasajuric’s code for Day 15) .
When I have got the program working for the examples, it didn’t finish for the real problem. It turned out that I had implemented a slightly more general solution than needed for the actual input (there was discussion in the subreddit about this), and my implementation was too slow. After some optimisation of the algorithm, I got the answer.
Here is my solution. It runs in well under a second.
1 Like
Yeah, I also didn’t assume anything about the input (as it wasn’t mentioned in the text). My first take was somewhat messy, but I quite like how the solution turned out after some refactoring.
Disregarding the parsing, I do it in the single pass, keeping the collection of current positions as the state, and the map with current shortest distances of visited rooms. Every time I encounter a choice, I execute each branch separately, merging the resulting positions and the map of all the branches. Additionally, if the choice is optional, I also merge the positions I was at before the conditional. So the state after a choice contains the (unique) positions after all the branches and the updated map (room_position => shortest_distance).
Day 20 was a nice challenge!
That was key for solving the problem. I feared the possible exponential explosion but in the first approach just went straight with exercising all paths. Cutting off duplicate paths that would result from various branches landing at the same point was good enough to make this run in an instance.
I hand-rolled a parser too. I couldn’t resist writing down a small grammar for the regex and implementing that with pattern matching. I also love the ε-production thrown there just for good measure. That was fun!
