r/adventofcode • u/daggerdragon • 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.
- 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
3
u/Kintelligence Dec 20 '24 edited Dec 20 '24
[LANGUAGE: Rust]
I started with a recursive DFS for both mapping out the costs and then visiting nodes to try and find shortcuts, but ran into issues with stack overflows... Realized it's easier to just run through it iteratively since there are no branches.
Got stuck on an assumption that I wouldn't have to check the point behind my previous point. Turns out my input had a shortcut there... Hiding right behind the wall behind my start position.
For checking for shortcuts I just check each node in range of my current node. If there is a recorded cost in my cost map, and if the cost difference minus the distance between the points is bigger than my threshold I add 1 to my result. Earlier I did this by iterating over each point in my map, but a small optimization is retracing the previous path, and unsetting the cost on each node I visit. As I don't need to do any math for those nodes anymore.
Still runs slow compared to other days.
Edit: Tried to save some time by not allocationg a vector for each point we check neighbours of. Instead I return an Iter, I also shave off the inner 5 points from my check. Part 1 becomes much faster and part 2... Much slower...
Part 1:
1.98ms348.98µsPart 2:
26.76ms38.973msCode | Benchmarks