Day 22
I’m still working on part 2, but before I go down the path of intersecting cuboids, etc., I wanted to see if there is a simpler approach :) Normally I solve the puzzle before looking at spoilers, but the above approach seems like a fair amount of work, so if I’m missing a “trick”, I don’t mind a spoiler :)
I haven’t done part 2 yet, today’s crazy and not sure when I’ll get to it. Maybe there’s some wildly trivial trick out there, but - coming from game dev - this is a pure CSG problem which is simple since all the solids are AABBs.
The real question is how many of the edge cases are present in the input data.
But, basically you can think of it as a binary tree of + and - expressions:
(+ A (- X Y)) Where + is the union of two volumes and - is the difference in the volumes.
The trick is realizing that the union of the two volumes is really: V = (A ∪ B) - (A ∩ B) since you only want to count the overlap once. Likewise, the difference between two the two volumes is going to be V = A - (A ∩ B), since you only care about subtracting the overlapping volume.
So, pop the first command (always a +) and create a root node. For each subsequent command you find the overlapping AABBs it intersects with and add to the tree based on what the command is.
When done, just recursively calculate the volume of the root node.
It’s also to go another route which is a bit more work, but doesn’t need to keep a whole tree in memory. This route is basically about keep a list of all the AABBs with cubes turned on. Each command, loop over all the AABBs (ideally an oct-tree) to find the first intersecting one. When you find one…
• For a + you take the overlapped box and break it up into one of 26 AABBs (the 26 AABB volumes that surround the one you’re intersecting with) and then recursively add each of those (up to) 26 new AABBs the same way. If there’s no overlap, just append to the list/oct-tree. • For a - you loop over all the AABB volumes in your list and find all the overlaps. When you find one, you subdivide the existing volume into N volumes and add each of those to the list (they won’t overlap anything, so you can just prepend them), removing the original. This is actually easy once you’ve coded + because it’s the same operation, just with the operands flipped. All of this will be really fast. I just haven’t sat down to do it yet. Maybe I should start? :slightly_smiling_face:
The above is recollection from doing CSG code years ago, though.
@massung using the tree method, don’t you still need to do a lot of cube splitting?
only under certain circumstances, which may or may not exist with the input data
<sigh> :)
i have the latter version coded up and works for part 1 just fine. part 2 is off, but only by a little bit, so it’s likely some stupid edge case i forgot or a typo
bah.. stupid array management, i know where the issue is… now just to figure out a fix
and done :slightly_smiling_face:
There’s a decent chunk of code in there. Solution runs in ~1.5s. The partitions function may save you a little time if you end up going down that route
Funnily, since I use the same code, part 1 is slower than part 2 (due to the range limit being applied at the end)
A total aside, this puzzle did give me some flashbacks. I was the lead programmer on this game: https://store.steampowered.com/app/20500/Red_Faction_Guerrilla_Steam_Edition/ - lots of CSG and other “destruction” code in the Red Faction series
@massung I just couldn’t bare the thought of doing all the cuboid splitting, etc., so I thought about just using only intersection and just keep adding either positive or negative intersections, etc. - I gave it a 50/50 chance of working, but it paid off. Runtime is 105 ms on part 2. <https://github.com/lojic/LearningRacket/blob/master/advent-of-code–2021/solutions/day22/day22-part2.rkt|Day 22>
I spent hours thinking about this puzzle!
NICE!