6
votes
Day 22: Reactor Reboot
Today's problem description: https://adventofcode.com/2021/day/22
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python
with any of the "short names" listed in this page of supported languages):
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
After reading and expecting part 2, I think I'll skip it for now and come back to it later. I have vague recollections of how to do this from studying graphics.
Part 1, Rust
The
hashbrown
crate seems to be doing a lot of heavy lifting here. Running this using the standard hashset and thedifference
call gives a runtime of ~15 seconds.hashbrown
's hashset takes 6 seconds, and the current solution with the drain filter takes slightly more than 1 second.Elixir
Part 1 was easy-peasy, but those huge numbers in the puzzle input definitely struck fear into my heart.
I did some thinking on paper for part 2, and I think I know what I need to do for an optimized solution, but... yikes, it seems like actually doing it will be really challenging. Here's what I've got for part 1, at least. Also a small hint at how I'm planning to implement part 2 from the function stubs/argument names.
My naive solution for part 1 runs in about 1.4s.
Part 1
Part 2 thoughts
Whenever these optimization problems come up, the solution is usually to find a way to model the problem with numbers alone. I think this one is no different.
It looks like instead of using a set or similar structure to track every single 3d point that is currently "on", we need to keep the representation closer to how it's represented in the puzzle input—a list of groups of 3 ranges, each representing a cuboid.
I'm trying to figure out how to decompose the result of each action into a list of non-overlapping cuboids. Keeping them from overlapping is the important part—it makes calculating the total volume at the end as simple as summing the volumes of each cuboid. I found this SO question on the topic, and it looks pretty involved in two dimensions, let alone 3...
Edit: This problem is slightly more manageable than the SO post I linked because if you set it up right, you're only ever checking the overlap of two cuboids at a time and every operation starts and ends with non-overlapping cuboids. There are still a lot of different cases to consider in checking each pair of cuboids, though.
I got part 2! It runs in about 2.6s. Switching to the optimized function for part 1 also cuts down the runtime from 1.4s to 78ms. I absolutely melted my brain trying to get the logic right—visualizing this stuff is a challenge. The code you see is the result of starting with some longer pseudo-code that considers all the possible ways two cuboids can intersect and boiling it down to one function that works on every possible intersection.
Part 2 (and part 1 using the optimized cuboid-intersecting function)
Rust
Like many, I've only done part 1 so far because it was trivial. Part 2 seems relatively straightforward but non-trivial to implement (some spoiler thoughts & link below).This'll be my last day-of attempt this year as I'll be busy over the next few days. It's been fun working on these simultaneously with the rest of you.
EDIT: Finished! Updated code posted.
Rust