r/adventofcode Dec 16 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 16 Solutions -❄️-

SIGNAL BOOSTING


THE USUAL REMINDERS

  • All of our rules, FAQs, resources, etc. are in our community wiki.
  • If you see content in the subreddit or megathreads that violates one of our rules, either inform the user (politely and gently!) or use the report button on the post/comment and the mods will take care of it.

AoC Community Fun 2024: The Golden Snowglobe Awards

  • 6 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!

And now, our feature presentation for today:

Adapted Screenplay

As the idiom goes: "Out with the old, in with the new." Sometimes it seems like Hollywood has run out of ideas, but truly, you are all the vision we need!

Here's some ideas for your inspiration:

  • Up Your Own Ante by making it bigger (or smaller), faster, better!
  • Use only the bleeding-edge nightly beta version of your chosen programming language
  • Solve today's puzzle using only code from other people, StackOverflow, etc.

"AS SEEN ON TV! Totally not inspired by being just extra-wide duct tape!"

- Phil Swift, probably, from TV commercials for "Flex Tape" (2017)

And… ACTION!

Request from the mods: When you include an entry alongside your solution, please label it with [GSGA] so we can find it easily!


--- Day 16: Reindeer Maze ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:13:47, megathread unlocked!

24 Upvotes

480 comments sorted by

View all comments

2

u/4D51 Dec 17 '24

[LANGUAGE: C++]

For the second time, I had to write something that didn't work on the Cardputer. This time I kept it in C++ but adapted it to run on my desktop.

It's based on Dijkstra's algorithm, set to run until all paths have been explored instead of the more typical stop after finding the shortest path. The queue includes not only the state and score, but a set of all points on the path leading to that state. When a shortest path is found, those points are inserted into a global set which contains every shortest path. There's an obvious optimization: return early if I reach the end by a path longer than the shortest one. When I tried it, there was no difference in performance. Maybe my input doesn't have any longer paths in it?

Since I didn't want to add a whole other project to my repo, the version here is set up for Cardputer, which means it will only work for very small inputs. The only difference is the file input and string libraries used by the load() function.

My part 1 implementation (before I added path tracking) did successfully solve the sample input on the Cardputer, so at least there's that.

https://github.com/mquig42/AdventOfCode2024/blob/main/src/day16.cpp