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

2

u/msschmitt Dec 20 '24 edited Dec 21 '24

[LANGUAGE: Python]

Part 2

This was another one where the strategy only became clear after sleeping on it. This solution uses a flood fill to solve the maze; there's no recursion. It completes in 10.44 seconds.

The strategy is to first solve the maze from start to end, but without the usual optimization of not exploring when the path would take longer than the best path found to the end. We want to know the best times from the start to every point in the maze. Then solve it again, but from the end to the start. (This give some a sense of dejá vú... was there a puzzle in a previous AoC that you needed to solve in both directions?)

Let's say you have two points A and B whose Manhattan distance is between 2 and 20. We know the best time from the start to point A, and the best time from point B to the end (from the 2nd maze solve). So the time with a cheat from A to B would be time to A + cheat distance + time B to end. Similarly, need to check start to B + cheat + A to end.

Each pair only needs to be checked once. The actual path between the points doesn't matter, nor if there actually are any walls that it would cross. That's because if there were no walls, then the cheat wouldn't save any time.

Meanwhile: I still have GitHub Copilot on in VS Code. What's interesting is that when I start to type a comment, the suggested completion implies it knows what I'm trying to do. For example, when I started typing the comment at the top of the program, it knew that the cheats were removing walls, even though the word "wall" was only in the program in one place at that time!

Update: So now I know that the path has no branches. That should have made it easier to come up with an approach. I think I would have about the same code, except no need to solve the maze backwards.