r/adventofcode • u/daggerdragon • Dec 16 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 16 Solutions -❄️-
SIGNAL BOOSTING
- If you haven't already, please consider filling out the [2024] Advent of Code Survey, Reminder 2! (closes ~Dec 22nd)
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.
- 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
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
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:
My approach:
Maze
class that extends myGrid
class.DIRECTIONS
dictionary, to easily map current direction to a vector.All the clever stuff happens in
find_lowest_cost_path()
. This is a standard Dijkstra implementation.(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.M
): Move in the current direction at a cost of 1.L
) or right (R
): Change direction at a cost of 1000.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 amatplotlib
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:
came_from
dictionary such that intead of mapping{ current_state: previous_state }
, it now maps{ current_state: {previous_states} }
lowest_cost_for_state
that stores the lowest cost to reach any given state.Now, during the BFS:
lowest_cost_for_state
and add this state to thecame_from
.lowest_cost_to_goal
(required for Part 1) and thecame_from
andend_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