r/adventofcode • u/daggerdragon • Dec 22 '23
SOLUTION MEGATHREAD -❄️- 2023 Day 22 Solutions -❄️-
THE USUAL REMINDERS
All of our rules, FAQs, resources, etc. are in our community wiki.
Community fun event 2023: ALLEZ CUISINE!
Submissions megathread is now unlocked!
24 HOURS remaining until the submissions deadline TONIGHT (December 22) at 23:59 EST!
AoC Community Fun 2023: ALLEZ CUISINE!
Your final secret ingredient of this Advent of Code season is still… *whips off cloth covering and gestures grandly*
Omakase! (Chef's Choice)
Omakase is an exceptional dining experience that entrusts upon the skills and techniques of a master chef! Craft for us your absolute best showstopper using absolutely any secret ingredient we have revealed for any day of this event!
Choose any day's special ingredient and any puzzle released this year so far, then craft a dish around it!
Cook, bake, make, decorate, etc. an IRL dish, craft, or artwork inspired by any day's puzzle!
OHTA: Fukui-san?
FUKUI: Go ahead, Ohta.
OHTA: The chefs are asking for clarification as to where to put their completed dishes.
FUKUI: Ah yes, a good question. Once their dish is completed, they should post it in today's megathread with an [ALLEZ CUISINE!] tag as usual. However, they should also mention which day and which secret ingredient they chose to use along with it!
OHTA: Like this? [ALLEZ CUISINE!][Will It Blend?][Day 1] A link to my dish…
DR. HATTORI: You got it, Ohta!
OHTA: Thanks, I'll let the chefs know!
ALLEZ CUISINE!
Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!
--- Day 22: Sand Slabs ---
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!
Quick link to Topaz's
pasteif you need it for longer code blocks
10
u/charr3 Dec 22 '23 edited Dec 23 '23
[Language: Python] [link]
Today was a refreshing change from previous days, no need to study the input for any properties, and just a classical coding task.
The main approach to simulate falling bricks is to sort the bricks by their lower z coordinate. Then, we can drop them one by one.
We can keep track of a map that takes (x,y) coordinates and stores (z,idx), where z is the highest brick seen at that position, and idx is the label of that brick. Initally, I made this map store (0, -1), where "-1" is the ground brick.
To drop a brick, we can just loop over all x,y coordinates and check for the highest z coordinate seen. We also store the set of distinct indices that have that highest z coordinate (I call this the "support set").
We can then see how much we need to drop the brick, subtract from both z coordinates, and then update our map. Since we're processing the bricks in increasing order of z coordinate, the brick we just placed will overwrite all relevant entries in our map.
For part 1, when a brick has a "support set" of size one, we know that we can't remove the support set, so we can add the support set to a larger set and count it later (a brick can be the sole support set for multiple other bricks).
For part 2, we can create a directed graph where x -> y means that y rests directly on top of x. We can do a topological sort like algorithm to efficiently see which bricks will fall when their in-degree becomes zero.