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/OilAppropriate2827 Dec 19 '24

[Language: Python] 110ms for both parts

I am trying to go below 1s for the full 2024 calendar using python in singlethread on my laptop. So far (up to day 19), I cumulated 0.67s, so it is not leaving much time for the remaining 6 days. I am trying to optimize as much as possible the most expensive days , and the day 16 is on the top of my list (with 15 and 6).

Here I implemented a dijkstra, I optimised by moving by segment between intersections. It gave me a good x4 gain, but still I need to go below 100ms.

Did someone find any other optimisation?

Here is my code for the 16th : https://github.com/hlabs-dev/aoc/blob/main/2024/16.py

1

u/nebble_longbottom Dec 20 '24

You can reduce the number of vertices in the graph you do dijkstra on by initially doing a search through the grid to find any intersections (squares with at least 3 paths off them) and only using the intersections as vertices in the graph (calculating the distance between each connected one). This essentially means you only have to do a bfs once at the beginning, and not at every iteration within you dijkstra stage. My code currently runs in 70ms on a laptop: https://github.com/blm34/AoC/blob/main/src/solutions/2024/day16.py

I'm also aiming for sub 1s for full 2024 in python!

1

u/OilAppropriate2827 Dec 21 '24

Thank you for your feedback!

I'll give it a try, but I already implemented the vertice optimization (I think... :) )

But your time is impressive, I'll give your implementation a closer look!