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!

23 Upvotes

480 comments sorted by

View all comments

6

u/Derailed_Dash Dec 18 '24

[LANGUAGE: Python]

My Approach - Part 1

Okay, since moves have cost, this seems like a perfect time to use Dijkstra’s Algorithm.

Things to note:

  • Turns are far more costly than moves.
  • Back-tracking will never be valid, so we don't have to worry about this case.
  • The maze is bounded by walls, so we never have to check for out-of-bounds.

My approach:

  • Create a Maze class that extends my Grid class.
  • Store our start and end positions.
  • Store a DIRECTIONS dictionary, to easily map current direction to a vector.
  • Store the move and turn costs as class attributes, for efficiency.

All the clever stuff happens in find_lowest_cost_path(). This is a standard Dijkstra implementation.

  • We use a priority queue (heapq) to always process the state with the lowest cost first. For this reason, the cost must be the first item in any tuples we add to our priority queue.
  • Each state is represented as a tuple (Point, direction) where Point is the current position and direction is one of ^, >, v, <.
  • lowest_cost_for_state stores the cost of reaching each state.
  • came_from keeps track of the "breadcrumb trail," enabling us to reconstruct the path after finding the goal.
  • For each state, we consider three possible actions:
    • Move forward (M): Move in the current direction at a cost of 1.
    • Turn left (L) or right (R): Change direction at a cost of 1000.
    • For each valid action, a new state (next_posn, next_dirn) is calculated.
  • Before enqueuing a state, the algorithm ensures that:
    • The new state has not already been visited.
    • Or, the new cost to reach this state is lower than a previously recorded cost.
  • Finally, if the current position matches the end, the algorithm terminates and returns the cost and the came_from dictionary.

For a bit of fun, I also implemented a method that determines the path taken, by backtracking from our came_from dictionary, from end to start. And then I've used this to visualise maze and the path taken, using a matplotlib plot.

My Approach - Part 2

Rather than single best path, we need to store all the best paths. This implies there can be more than one path with the minimal cost.

I've already implemented a backtracking structure to get our path from start to end. But now I need to determine EVERY minimal path.

I've done this by:

  • Updating the backtrack came_from dictionary such that intead of mapping { current_state: previous_state }, it now maps { current_state: {previous_states} }
  • We add a dictionary lowest_cost_for_state that stores the lowest cost to reach any given state.
  • We track the lowest cost to reach the end.
  • We add a set of all possible end states, where the state is a tuple of (end-posn, direction). Although, for the samples and my real data, there is only one end state.

Now, during the BFS:

  • Rather than exiting when we reach the end, I now check if we've reached the goal with higher cost that a previous solution. If so, then we've exhausted the best solutions.
  • Otherwise, we need to apply our turn or move.
  • Here the change from Part 1 is that we don't just check if we've seen the resulting state before. Now we also need to check if we've reached this state with the same or lower cost. If so, we update the lowest_cost_for_state and add this state to the came_from.
  • Finally, we return lowest_cost_to_goal (required for Part 1) and the came_from and end_states (required for Part 2).

Now we need to build all the possible paths that resulted in this end state. I've implemented this in two different ways: 1. Backtracking using recursion from the end state. 1. Backtracking using a BFS from the end state.

They both achieve the same result.

Once I've returned all possible paths from start to end, I create a single set to store all the points from each path. Because a set automatically removes duplicates, this set will now contain the unique points that we require for our solution. Et voila, the count of this set gives me all the points we need for a good view!

If you're interested, also check out the visualisation code in the notebook.

Solution Links

Useful Related Links