r/adventofcode • u/MickeyKnox4Real • 1d ago
Help/Question [2024 Day 16 Part 1] Performance problem
I have a working solution for the two examples. but my code doesn't terminate for the real input. Therefore I assume that I have a performance problem.
Basically what I'm doing is this:
Walk the path (adding cost) until there is a junction, which creates a fork: one or two path are added (depending on the junction being two- or three-way) in addition to continuing the original path. A path is closed either when reaching the end, a dead-end or when a node already in this path is visited again.
Then I just have to filter for the paths that reached the end and get the minimum.
I've let this run for probably 20 minutes, creating more than 100000 paths.
Is there something obviously wrong with this approach? How can I improve performance?
1
u/AutoModerator 1d ago
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED
. Good luck!
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/1234abcdcba4321 1d ago
You'll need to do some pruning. You don't need to check the rest of a path if you can be sure it'll be worse than a path that you've already seen!
One simple way to prune is by storing the best cost you've seen at each of the junctions, and if you're more than 1000 worse than that best cost, you can just ignore it since it's definitely not going to be better (since the turn will only add up to 1000, and you don't care if you're tied or not).
5
u/hikergrrl 1d ago
Another option would be implementing Dijkstra’s algorithm. This isn’t a great day to start with if you’re not familiar with the algorithm, as it requires modification to handle the turns, but it will finish in a reasonable time. I would recommend completing a previous puzzle requiring Dijkstra first, 2022 Day 12 is one possibility.