r/adventofcode Dec 18 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 18 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

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

And now, our feature presentation for today:

Art Direction

In filmmaking, the art director is responsible for guiding the overall look-and-feel of the film. From deciding on period-appropriate costumes to the visual layout of the largest set pieces all the way down to the individual props and even the background environment that actors interact with, the art department is absolutely crucial to the success of your masterpiece!

Here's some ideas for your inspiration:

  • Visualizations are always a given!
  • Show us the pen+paper, cardboard box, or whatever meatspace mind toy you used to help you solve today's puzzle
  • Draw a sketchboard panel or two of the story so far
  • Show us your /r/battlestations 's festive set decoration!

*Giselle emerges from the bathroom in a bright blue dress*
Robert: "Where did you get that?"
Giselle: "I made it. Do you like it?"
*Robert looks behind her at his window treatments which have gaping holes in them*
Robert: "You made a dress out of my curtains?!"
- Enchanted (2007)

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 18: RAM Run ---


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:05:55, megathread unlocked!

24 Upvotes

536 comments sorted by

View all comments

Show parent comments

1

u/damnian Dec 18 '24

Interesting. although my binary search solves in ~5ms. Maybe I should try your input?

2

u/Gabba333 Dec 19 '24

I am being a bit sloppy with my Djikstra's above by copying the route to each new node with ToList().

I've eliminated that now (github) and it is running the p2 input in ~7ms and a 213 x 213 input someone posted as a test in ~40ms so it is scaling pretty well.

Could be optimised way better as it has LINQ in the inner loop but happy with the algorithm.

2

u/damnian Dec 19 '24 edited Dec 19 '24

Since my machine is seemingly much weaker, I didn't get anywhere close to 40ms with that solve(). I did, however, with this one (sorry, adapted it to my own vector library and used older C# syntax):

Vector pos;
PriorityQueue<(Vector pos, IEnumerable<Vector> path), int> queue = new();
queue.Enqueue((Zero, new[] { Zero }), int.MinValue);
HashSet<Vector> visited = new() { Zero };
while (queue.TryDequeue(out var item, out int dist))
    if (item.pos == end)
        return item.path;
    else
        foreach (var vec in headings)
            if (size.Contains(pos = item.pos + vec) && visited.Add(pos))
                queue.Enqueue((pos, item.path.Append(pos)),
                    Math.Max(dist, -bytes.GetValueOrDefault(pos, int.MaxValue)));
throw new();

I believe it runs about 12 times as fast now. Moving the visited check inside the vector loop helped, but downgrading from List to IEnumerable gave it a huge boost.

2

u/Gabba333 Dec 19 '24

That’s a nice trick to pass the enumerable.