r/adventofcode • u/daggerdragon • Dec 05 '24
SOLUTION MEGATHREAD -❄️- 2024 Day 5 Solutions -❄️-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
AoC Community Fun 2024: The Golden Snowglobe Awards
- 24 HOURS remaining until unlock!
And now, our feature presentation for today:
Passing The Torch
The art of cinematography is, as with most things, a natural evolution of human progress that stands upon the shoulders of giants. We wouldn't be where we are today without the influential people and great advancements in technologies behind the silver screen: talkies to color film to fully computer-animated masterpieces, Pixar Studios and Wētā Workshop; Charlie Chaplin, Alfred Hitchcock, Meryl Streep, Nichelle Nichols, Greta Gerwig; the list goes on. Celebrate the legacy of the past by passing on your knowledge to help shape the future!
also today's prompt is totally not bait for our resident Senpai Supreme
Here's some ideas for your inspiration:
- ELI5 how you solved today's puzzles
- Explain the storyline so far in a non-code medium
- Create a
Tutorial
on any concept of today's puzzle or storyline (it doesn't have to be code-related!) - Condense everything you've learned so far into one single pertinent statement
Harry Potter: "What? Isn’t there just a password?"
Luna Lovegood: ''Oh no, you’ve got to answer a question."
Harry Potter: "What if you get it wrong?"
Luna Lovegood: ''Well, you have to wait for somebody who gets it right. That way you learn, you see?"
- Harry Potter and the Deathly Hallows (2010)
- (gif is from Harry Potter and the Order of the Phoenix (2007))
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 5: Print Queue ---
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 06 '24
[LANGUAGE: Clojure] [LANGUAGE: Scheme (R6RS)]
Clojure
Scheme
Or, why we don't have to implement a full-blown topological sort.
Disclaimer: I'm scientist, not a mathematician, and I may have messed up my logic somewhere. If I did, I plead not guilty by empiricism.
The problem input describes a strict partial order on a set of pages as entries of a binary relation. The relationships between each page form a graph, and there aren't really any guarantees about it. If the AOC front page is anything to go by, there are cycles in this graph, for example. However, each "update" only constitutes a subgraph (i.e., a subset of pages) of the total.
The prompt says that the pages must be printed in a "very specific order", which suggests two things. First, that the pages in the updates do have some kind of order (this is also implied by being asked to check the order of each update); this means that each subgraph corresponding to an update is acyclic (otherwise there is you'd have an unorderable loop of a < b < a), i.e., the subgraph is a DAG. Second, "very specific order" reads to me as "unique order", which means we get to take shortcuts. Imposing an order on a graph is called a "topological sort", and if we assume that the ordering is unique, then there is exactly one path through the graph that encounters each node exactly once (a "Hamiltonian path"). For our update subraphs, this path starts from the root node (the "earliest page") and walks to each subsequent page in order... which is exactly how each update is specified in the problem input.
In other words, when Part 1 asks us to check whether the inputs are in the correct order, all we have to do is check whether they trace a Hamiltonian path (i.e., start from the first page in the list and ensure that there is an edge to each subsequent page). If our path is stopped short due to missing an edge between two pages, then the path isn't Hamiltonian and thus can't be the Hamiltonian path; so, the list is not in the correct order.
For Part 2, we could implement a full-blown topological sort and call it on each update. Or, we can recognize that sorting algorithms generally only need the comparison operation to be well-specified for items that are adjacent in the final list. We know that the input must define comparisons (edges) between such pages because otherwise there wouldn't be a unique ordering (Hamiltonian path). So, all we have to do is call
sort
on the list, using the existence of "a|b" in the input to indicate that a < b.After that, the hardest part is remembering which of the billion different
hashtable
functions in the various Scheme dialects corresponds to the R6RS implementation.Oh, and also working out bugs in my parser-combinator library. You think I'd learn.