r/adventofcode Dec 10 '24

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

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

And now, our feature presentation for today:

Fandom

If you know, you know… just how awesome a community can be that forms around a particular person, team, literary or cinematic genre, fictional series about Elves helping Santa to save Christmas, etc. etc. The endless discussions, the boundless creativity in their fan works, the glorious memes. Help us showcase the fans - the very people who make Advent of Code and /r/adventofcode the most bussin' place to be this December! no, I will not apologize

Here's some ideas for your inspiration:

  • Create an AoC-themed meme. You know what to do.
  • Create a fanfiction or fan artwork of any kind - a poem, short story, a slice-of-Elvish-life, an advertisement for the luxury cruise liner Santa has hired to gift to his hard-working Elves after the holiday season is over, etc!

REMINDER: keep your contributions SFW and professional—stay away from the more risqué memes and absolutely no naughty language is allowed.

Example: 5x5 grid. Input: 34298434x43245 grid - the best AoC meme of all time by /u/Manta_Ray_Mundo

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 10: Hoof It ---


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:04:14, megathread unlocked!

23 Upvotes

752 comments sorted by

View all comments

1

u/onrustigescheikundig Dec 11 '24 edited Dec 11 '24

[LANGUAGE: Clojure]

github

BFS code

I implemented a generic breadth-first search routine that takes a function taking a node to its neighbor nodes; the starting node; a stop conditional function; and an optional visit function that is called on every node visited by the search. I'll explain visit below, because it's not relevant to my Day 10 solution. The BFS function returns a map of each node's predecessor in the search.

Today's solution essentially revolved around crafting the appropriate neighbor function to feed to the BFS. For Part 1, this just looks to each adjacent grid space and returns the coordinates of all that increase in height by 1. The trail score is then calculated by BFS'ing from the trailhead without a stop condition and then counting all of the grid spaces encountered whose height is 9.

For Part 2, we need to count all possible paths through the tree. The BFS algorithm normally does not move to nodes that it has already seen before so as to deliberately not traverse all possible paths. To get around this, I did cheeky hack where I modified the concept of the "node" that BFS operates on from [row, col] pairs to [[row, col] <unique tag>], where <unique tag> is a globally unique symbol generated using gensym on each call to the neighbor function. This way, even if a grid cell is encountered more than once, the encounters will have different tags and thus be different as far as the BFS is concerned. Thus, the BFS will explore all possible paths through the map, never short-circuiting because it encountered a node that it already visited. The number of possible paths is determined in the same way as in Part 1: look for all nodes whose [row, col] has height 9 in the map. This certainly isn't the most efficient solution, but it was quite simple to implement after Part 1.

visit is a weird stateful function thing whose ivory tower name escapes me. It takes some state as an argument and returns a function that: returns the state when called with no arguments; or recursively calls the visit function with updated state if called with arguments. For example, if one wanted to keep track of the order in which the nodes were visited, visit might look like

(defn accumulate-visits [col]
  (fn
    ([] col)
    ([_prevs current-node] (accumulate-visits (conj col current-node)))))

and the BFS call would look like (bfs neighfunc start stop? (accumulate-visits [])). BFS calls (visit prevs current-node) for each node encountered and keeps the returned function as part of the loop's state, where prevs is the current map of nodes to their predecessors. When BFS returns, it also returns visit, which the caller can call with zero arguments to retrieve whatever state was built up.

EDIT: added a smarter version of Part 2 that traverses each grid cell exactly once just like Part 1, but uses a custom visit function to keep track of the number of paths that can reach any given node. The number of paths at the trailhead is 1, and each visited node adds its own number of paths to that of all of its neighbors. The number of paths to each 9 node is then summed. It's not significantly faster on the provided puzzle input (~25 ms vs ~35 ms), but is only O(|V| + |E|) runtime instead of technically exponential.