Module aoc::year2021::day22

Reactor Reboot

The key to solving this problem efficiently is the inclusion-exclusion principle .

Looking at a two dimensional example

   ┌──────────────┐A            Volume of A: 144
   │              │             Volume of B: 66
   │ ┌─────────┐B │             Volume of C: 18
   │ │         │  │
   │ │ ┌────┐C │  │
   │ │ │    │  │  │
   │ │ └────┘  │  │
   │ └─────────┘  │
   └──────────────┘

Using the inclusion-exclusion principle the remaining size of A is:

144 (initial size) - 66 (overlap with B) - 18 (overlap with C) + 18 (overlap between B and C) = 78

If there were any triple overlaps we would subtract those, add quadruple, and so on until there are no more overlaps remaining.

The complexity of this approach depends on how many cubes overlap. In my input most cubes overlapped with zero others, a few with one and rarely with more than one.

Structs

• Cube
  Technically this is actually a rectangular cuboid but that was longer to type!
• RebootStep
  Wraps a cube with on/off information.

Functions

• parse
• part1
  We re-use the logic between part one and two, by first intersecting all cubes with the specified range. Any cubes that lie completely outside the range will be filtered out.
• part2
• subsets 🔒