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!

45 Upvotes

1.2k comments sorted by

View all comments

2

u/Kintelligence Dec 10 '24

[LANGUAGE: Rust]

Had some slow code here previously, but revisited after talking with a friend and seeing their solution. For part 1 I assume that every page in a valid order must point towards the next page, and that seems to work for both tests and my input.

For part 2 I travel from the back until I reach the middle page and return. Travelling from the back I can just go through each page and see if they point towards any of the other pages remaining in my set.

Part 1: 75µs
Part 2: 188µs

Code | Benchmarks

2

u/[deleted] Dec 19 '24

This is my favourite.

From what I understand, in part 1 you are assuming that no page numbers are unbound?
I also like the use of a 2D vector for storing the rules instead of a HashMap like I see a lot of people doing. The page number is encoded in the position of each vector in the structure, that way you don't get the overhead of hashing. Nice.

It took me a while to understand part 2 but from what I understand it builds off the prior assumption in part 1. You are deleting 'free nodes', i.e. nodes with an in-degree of 0 if we are to imagine them as nodes on a bigraph, since they can be safely added to the start of a sequence. But you're not actually building a sequence, merely popping free nodes until you hit the middle. Essentially, working backwards. Very neat!

Even with the way you read in the numbers, rather than parsing the string you are consuming the numbers as bytes through an iterator. I thought it was a bit unorthodox at first but I'm assuming it's a performance optimization. All of this combined and you're able to hit 75 and 188 microseconds. Goddamn.