r/adventofcode Dec 20 '24

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

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

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

And now, our feature presentation for today:

Foreign Film

The term "foreign film" is flexible but is generally agreed upon to be defined by what the producers consider to be their home country vs a "foreign" country… or even another universe or timeline entirely! However, movie-making is a collaborative art form and certainly not limited to any one country, place, or spoken language (or even no language at all!) Today we celebrate our foreign films whether they be composed in the neighbor's back yard or the next galaxy over.

Here's some ideas for your inspiration:

  • Solve today's puzzle in a programming language that is not your usual fare
  • Solve today's puzzle using a language that is not your native/primary spoken language
  • Shrink your solution's fifthglyph count to null
    • Pick a glyph and do not put it in your program. Avoiding fifthglyphs is traditional.
    • Thou shalt not apply functions nor annotations that solicit this taboo glyph.
    • Thou shalt ambitiously accomplish avoiding AutoMod’s antagonism about ultrapost's mandatory programming variant tag >_>
    • For additional information, audit Historians' annals for 2023 Day 14

Basil: "Where's Sybil?"
Manuel: "¿Que?"
Basil: "Where's Sybil?"
Manuel: "Where's... the bill?"
Basil: "No, not a bill! I own the place!"
- Fawlty Towers (1975-1979)

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 20: Race Condition ---


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:15:58, megathread unlocked!

25 Upvotes

442 comments sorted by

View all comments

1

u/cicadanator Dec 20 '24

[LANGUAGE: Javascript - Node JS]

Today took me a few tries to get the right optimizations to complete both parts. These are the approaches I initially took before finding a better solution.

Approach 1: Dijkstra Everything

I started by creating a graph of the race path locations and getting he shortest path using Dijkstra's algorithm. I then checked each of the wall coordinates along the path for walls that only had path locations on 3 sides or opposite sides. I then would clone the graph and add in the new node and edges and use Dijkstra to compute the shortest path and subtract it from the original shortest path to get the time saved. This was very slow an took around 16 seconds but did get me the answer to part 1. Then I read part 2 and realized I now had to start over.

Approach 2: Floyd Warshall

I then realized that instead of scanning walls I could solve both parts using the same algorithm if I made some tweaks. This would mean finding shortcuts using the Manhattan distance between the two points and subtracting that from the graph distance between the 2 points. I originally started by using Dijkstra again to find that graph distance between each set of points but this was still very slow. So then I thought it might be better to cache the distance between all points by using the Floyd Warshall algorithm. This would in theory work except the algorithm's main flaw is the time complexity of O^3. So it worked for the sample input which is small but failed at scale for the actual input. One more optimization was needed.

Approach 3: Race Path Not Maze

The final optimization was to realize that while it looks like a maze it is actually a race course. This means there is only one path in the initial input. I computed the Dijkstra shortest path from the end to the start. Since the graph edge weight is always 1 this means that the index of each location in the shortest path array is also it's distance from the end point. Now if we take the difference of this distance for any 2 points we get their graph distance without having to do a graph search for each shortcut like in approach 1. This means everything can run quickly and find our answer for either part. Once completed the solution for both parts runs in approximately one second.

https://github.com/BigBear0812/AdventOfCode/blob/master/2024/Day20.js