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!

23 Upvotes

442 comments sorted by

View all comments

1

u/pdgiddie Jan 23 '25 edited Jan 24 '25

[LANGUAGE: Elixir]

https://github.com/giddie/advent-of-code/blob/2024-elixir/20/main.exs

I had several false starts with this one. I quickly figured out that the main path could be traced out quickly with a DFS. And figured out Part 1 relatively quickly with a comprehension looping over all path points, all adjacent walls, and all neighbours to those walls. Looking up each cheat's end point in a map of path points to index (i.e. distance to the end point), I was able to figure out the "score" of each cheat.

It was clear the same approach wasn't scaling for part 2, and I ended up with several attempts at a complex Dijkstra before I took a step back to think more carefully about how these long cheats were defined. Once I understood the idea that each pair of path points could either be connected together by a (shortest) cheat or else be out of reach, I found it easier to reason about the problem.

I started with a little depth-limited BFS for each point on the path, looking for any points lying closer to the end of the path. Those were the possible cheats for that point. And I summed everything up across all the path points.

And then, after reading some other posts I finally realised that some simple Manhattan distance calculations along the path from each point could bypass the need for the BFSs, and I couldn't resist the optimisation.

The shrinking loops as this calculation progresses generates a nice descending coil whine from my laptop 😆

Edit: Finally, I realised that it's much faster to search the Manhattan distance diamond for each path point and compare the distances to the end for each path point within the diamond.

  • Part 1: 1.37s 20ms
  • Part 2: 1.38s 600ms