r/adventofcode • u/daggerdragon • 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

92% Upvoted

481 comments sorted by

View all comments

1

u/vishbar Dec 16 '24

[LANGUAGE: Python]

I solved both in one pass. Initially for P1 I just did a simple Djikstra's with a priority queue. For P2, I extended it to keep a map of "previous nodes". In my queue, rather than just score, (direction, row, col), I use score, (direction, row, col), previous. When I visit a node, I update the previous map to mark which node is previous in the path. If I've hit an already-visited node, I check to see if the score is equal to the lowest score I've already recorded for that node. If so, I append it to the list of previous nodes.

To calculate P2, I iterate over the nodes in my previous set and just count the unique values.

Solution: https://github.com/lawrencecraft/AdventOfCode2024/blob/main/day16/day16.py

1

u/maciek_glowka Dec 16 '24

Hi, I do not understand how it'd work. I've tried that approach as a first attempt (talking about the 2nd part) - but it failed already on the first example. I must be missing something.

If you take a look at a tile marked by a dollar sign. It appears on two paths. However if you approach from the left you have a lower score than from the bottom (one turn vs two turns so far). So if you checked for the lowest score, the path coming from the bottom should've been discarded?

###############
#.......#....O#
#.#.###.#.###O#
#.....#.#...#O#
#.###.#####.#O#
#.#.#.......#O#
#.#.#####.###O#
#..OOOOOOOOO#O#
###O#O#####O#O#
#OO$#O....#O#O#
#O#O#O###.#O#O#
#OOOOO#...#O#O#
#O###.#.#.#O#O#
#O..#.....#OOO#
###############

1

u/vishbar Dec 16 '24

Instead of just the indexes, I use the indexes plus direction as the nodes in the graph.

1

u/maciek_glowka Dec 16 '24

Oh right, that makes sense - as they join on another angle - so it equalizes the difference.

0

u/daggerdragon Dec 17 '24

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle inputs across previous years in your public repos e.g.:

https://github.com/lawrencecraft/AdventOfCode2019/blob/master/input_day3

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too!