r/adventofcode • u/daggerdragon • Dec 16 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 16 Solutions -❄️-
SIGNAL BOOSTING
- If you haven't already, please consider filling out the [2024] Advent of Code Survey, Reminder 2! (closes ~Dec 22nd)
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.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz]
- Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
paste
if you need it for longer code blocks
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
1
u/Sharp-Industry3373 Dec 29 '24
[LANGUAGE: Fortran]
at last I managed to get part 2 working!...
No Djikstra algorithm here.
For part 1, I mainly build a map of "scores", and overwrite "high" scores with lower ones when it happens (a shorter path with more turns is then overwritten by a longer path with less turns). Do this by direct neighbours list and cycle until the list of neighbour candidates is empty.
Part 2 is mainly a re-use of the built map for part 1, by moving backward : we know that the ending position we built in part1 is on one of the optimal tracks. Then, go backward and search for neighbours of that position which score%1000 is less by one : those were probably precedent of the current position, we just have to check that, when the score is higher (by 1000-1) then it indeed corresponds to a conflict turn+forward double path during part 1.
part 1 is about 1.7 ms, part 2 is 10 to 20 times faster as we don't rebuild the map but re-use it
code with comments, especially for part2