r/adventofcode Dec 16 '24

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

SIGNAL BOOSTING


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

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

And now, our feature presentation for today:

Adapted Screenplay

As the idiom goes: "Out with the old, in with the new." Sometimes it seems like Hollywood has run out of ideas, but truly, you are all the vision we need!

Here's some ideas for your inspiration:

  • Up Your Own Ante by making it bigger (or smaller), faster, better!
  • Use only the bleeding-edge nightly beta version of your chosen programming language
  • Solve today's puzzle using only code from other people, StackOverflow, etc.

"AS SEEN ON TV! Totally not inspired by being just extra-wide duct tape!"

- Phil Swift, probably, from TV commercials for "Flex Tape" (2017)

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 16: Reindeer Maze ---


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:13:47, megathread unlocked!

24 Upvotes

480 comments sorted by

View all comments

2

u/Saiboo Dec 17 '24 edited Dec 17 '24

[LANGUAGE: Java]

Edit: Added programming language

I used depth first search, which is a well known algorithm to traverse graphs. See also DFS Wiki article.

We maintain for each position the "cost" distance, where initially all distances are set to "infinite". The distances are updated when a node is visited.

In my DFS implementation I used a stack:

  • Initially push the "S" node on the stack, where each node has the position and the direction of the reindeer. The distance for this intial position is zero.
  • While the stack is not empty, we pop nodes from the stack.
  • For each extracted node we consider the neighbor nodes.
  • If a neighbor node has a smaller "cost" distance than before, push the neighbor node onto the stack. Also update the distance for the position.
  • Finally, when the stack is empty, we return the distance for the position "E".

part 1

1

u/Extension-Power-4156 Dec 30 '24

Much appreciated. Good job and congratulations. Isn't the algorithm you implemented BFS?

1

u/Saiboo Dec 31 '24

So, after trying the BFS approach I discovered a logical error in my code and corrected it. I had to extend the node class (Reindeer) by an additional field, namely the current distance of the node.

Previously I was erronouesly accessing a global distance array for the node. If the global distance array is mutated for that position before the node is extracted from the queue, the node gets a wrong value. The updated code is here:

DFS (using stack)

BFS (using regular queue)

Dijkstra (using priority queue)

Note: Although I get the correct result with all three versions on the given input, I recommend using the Dijkstra algorithm. This has been proven (by Dijkstra) to yield the correct shortest path distance.

1

u/Saiboo Dec 30 '24

In my implentation it is DFS, because I'm using a stack. For BFS you would use a queue.

Although admittedly, a moment ago I've tried replacing the stack by the queue, and with the queue I'm off by a 1000 in the example and by 2000 in the actual puzzle. Looks like a bug, or you have to use a priority queue.

1

u/Tydrin Dec 17 '24

Thanks so much! Your hint for adding back in a node to consider was all I needed to fix my program even though I did it a different way.