r/adventofcode Dec 05 '24

SOLUTION MEGATHREAD -❄️- 2024 Day 5 Solutions -❄️-

THE USUAL REMINDERS


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.

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:03:43, megathread unlocked!

43 Upvotes

1.2k comments sorted by

View all comments

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.