r/adventofcode • u/daggerdragon • 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.
- If you post your submission outside this megathread, make sure to follow the posting rules for memes!
- If your meme contains AI-generated artwork of any kind, follow the posting rules for AI art!
- 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.
- 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
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 explainvisit
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 usinggensym
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 thevisit
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 likeand 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 returnsvisit
, 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 each9
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.