There are too many cuboids in a reactor being turned on or off to use a matrix model, even sparse, to track. Even with the limited 100x100x100 problem size of part 1 you'd need to track the state of millions of cubiods.
We can limit ourselves to just tracking volume. For any given 'on' cube, the volume that remains at the end is the volume not contained in later cuboids that overlap it, wether they are 'on' or 'off'; that's because later 'on' cuboids are themselves counting for their whole volume minus following overlapping cuboids.
The challenge really then, is to determine how much to subtract; if two subsequent cubes themselves overlap, you need to make sure you don't subtract the volume of that overlap twice. Or, thinking about it another way, you would need to add back that overlap, just for the instersections that intersect:
+-----------+
| 1 |
+---+---+---+---+---+
| | A | B | D | |
| +---+---+---+ |
| 2 | C | 3|
+-------+---+-------+
We start with cubes 1 and 2, and the intersection represented by A + B, which would need to be removed from the volume of those two cubes. Then when cube 3 comes into play, the sections B + C and B + D complicate matters some more; you'd subtract too much for the 'B' cube unless we also treat A + B and B + C as new, negative ('off') cubes, and their intersections as new positive ('on') cubes.
So we keep a list of processed cubes and intersections, and each cube from our list of instructions is first intersected with that list, adding the resulting intersections as inverted cubes, and then add the current cube itself if it itself an 'on' cube. At the end, we sum the volumes of all the processed cubes and intersections, treating 'off' cubes as negative.
from __future__ import annotations
import re
from dataclasses import dataclass
from enum import Enum
from functools import cached_property, reduce
from itertools import chain
from operator import mul
from typing import Callable
LINE: Callable[[str], re.Match] = re.compile(
r"(on|off)\s*x=(-?\d+)\.\.(-?\d+),y=(-?\d+)\.\.(-?\d+),z=(-?\d+)\.\.(-?\d+)"
).fullmatch
class Operation(Enum):
on = 1
off = -1
def __invert__(self) -> Operation:
return Operation(-self.value)
@dataclass(frozen=True)
class Cube:
operation: Operation
x1: int
x2: int
y1: int
y2: int
z1: int
z2: int
@cached_property
def volume(self) -> int:
sign = self.operation.value
return reduce(mul, (c2 - c1 + 1 for c1, c2 in self.coords)) * sign
@cached_property
def coords(self) -> tuple[tuple[int, int], tuple[int, int], tuple[int, int]]:
return (self.x1, self.x2), (self.y1, self.y2), (self.z1, self.z2)
@classmethod
def from_line(cls, line: str) -> Cube:
op, *coords = LINE(line).groups()
return cls(Operation[op], *map(int, coords))
def within(self, low: int, high: int) -> bool:
coords = self.coords
return all(c1 >= low and c2 <= high for c1, c2 in coords)
def __sub__(self, other: Cube) -> Cube:
"""New cube from the intersection"""
if not isinstance(other, Cube):
return NotImplemented
sc, oc = self.coords, other.coords
if any((sc1 > oc2 or sc2 < oc1) for (sc1, sc2), (oc1, oc2) in zip(sc, oc)):
# no intersection
return None
return Cube(
~other.operation,
*chain.from_iterable(
(max(sc1, oc1), min(sc2, oc2)) for (sc1, sc2), (oc1, oc2) in zip(sc, oc)
),
)
@dataclass
class Reactor:
cubes: list[Cube]
@classmethod
def from_lines(cls, lines: list[str]) -> Reactor:
return cls([Cube.from_line(line) for line in lines])
def clamp(self, min: int, max: int) -> Reactor:
return type(self)([cube for cube in self.cubes if cube.within(min, max)])
def reboot(self) -> int:
intersections: list[Cube] = []
for cube in self.cubes:
new = (cube - other for other in intersections)
intersections += [intersection for intersection in new if intersection]
if cube.operation is Operation.on:
intersections.append(cube)
return sum(c.volume for c in intersections)
test_instructions = {
(
"on x=10..12,y=10..12,z=10..12\non x=11..13,y=11..13,z=11..13\n"
"off x=9..11,y=9..11,z=9..11\non x=10..10,y=10..10,z=10..10"
): 39,
(
"on x=-20..26,y=-36..17,z=-47..7\non x=-20..33,y=-21..23,z=-26..28\n"
"on x=-22..28,y=-29..23,z=-38..16\non x=-46..7,y=-6..46,z=-50..-1\n"
"on x=-49..1,y=-3..46,z=-24..28\non x=2..47,y=-22..22,z=-23..27\n"
"on x=-27..23,y=-28..26,z=-21..29\non x=-39..5,y=-6..47,z=-3..44\n"
"on x=-30..21,y=-8..43,z=-13..34\non x=-22..26,y=-27..20,z=-29..19\n"
"off x=-48..-32,y=26..41,z=-47..-37\non x=-12..35,y=6..50,z=-50..-2\n"
"off x=-48..-32,y=-32..-16,z=-15..-5\non x=-18..26,y=-33..15,z=-7..46\n"
"off x=-40..-22,y=-38..-28,z=23..41\non x=-16..35,y=-41..10,z=-47..6\n"
"off x=-32..-23,y=11..30,z=-14..3\non x=-49..-5,y=-3..45,z=-29..18\n"
"off x=18..30,y=-20..-8,z=-3..13\non x=-41..9,y=-7..43,z=-33..15\n"
"on x=-54112..-39298,y=-85059..-49293,z=-27449..7877\n"
"on x=967..23432,y=45373..81175,z=27513..53682\n"
): 590784,
}
for test, expected in test_instructions.items():
assert Reactor.from_lines(test.splitlines()).clamp(-50, 50).reboot() == expected
import aocd
reactor = Reactor.from_lines(aocd.get_data(day=22, year=2021).splitlines())
print("Part 1:", reactor.clamp(-50, 50).reboot())
Part 1: 589411
For part 2, the breaks are off and we just run the same process over the larger set of cubes, not just those that fit within the 100x100x100 cube.
This does show that my approach is not the most efficient; it takes a few seconds to complete the full puzzle input.
test_full_reboot = Reactor.from_lines(
"""\
on x=-5..47,y=-31..22,z=-19..33
on x=-44..5,y=-27..21,z=-14..35
on x=-49..-1,y=-11..42,z=-10..38
on x=-20..34,y=-40..6,z=-44..1
off x=26..39,y=40..50,z=-2..11
on x=-41..5,y=-41..6,z=-36..8
off x=-43..-33,y=-45..-28,z=7..25
on x=-33..15,y=-32..19,z=-34..11
off x=35..47,y=-46..-34,z=-11..5
on x=-14..36,y=-6..44,z=-16..29
on x=-57795..-6158,y=29564..72030,z=20435..90618
on x=36731..105352,y=-21140..28532,z=16094..90401
on x=30999..107136,y=-53464..15513,z=8553..71215
on x=13528..83982,y=-99403..-27377,z=-24141..23996
on x=-72682..-12347,y=18159..111354,z=7391..80950
on x=-1060..80757,y=-65301..-20884,z=-103788..-16709
on x=-83015..-9461,y=-72160..-8347,z=-81239..-26856
on x=-52752..22273,y=-49450..9096,z=54442..119054
on x=-29982..40483,y=-108474..-28371,z=-24328..38471
on x=-4958..62750,y=40422..118853,z=-7672..65583
on x=55694..108686,y=-43367..46958,z=-26781..48729
on x=-98497..-18186,y=-63569..3412,z=1232..88485
on x=-726..56291,y=-62629..13224,z=18033..85226
on x=-110886..-34664,y=-81338..-8658,z=8914..63723
on x=-55829..24974,y=-16897..54165,z=-121762..-28058
on x=-65152..-11147,y=22489..91432,z=-58782..1780
on x=-120100..-32970,y=-46592..27473,z=-11695..61039
on x=-18631..37533,y=-124565..-50804,z=-35667..28308
on x=-57817..18248,y=49321..117703,z=5745..55881
on x=14781..98692,y=-1341..70827,z=15753..70151
on x=-34419..55919,y=-19626..40991,z=39015..114138
on x=-60785..11593,y=-56135..2999,z=-95368..-26915
on x=-32178..58085,y=17647..101866,z=-91405..-8878
on x=-53655..12091,y=50097..105568,z=-75335..-4862
on x=-111166..-40997,y=-71714..2688,z=5609..50954
on x=-16602..70118,y=-98693..-44401,z=5197..76897
on x=16383..101554,y=4615..83635,z=-44907..18747
off x=-95822..-15171,y=-19987..48940,z=10804..104439
on x=-89813..-14614,y=16069..88491,z=-3297..45228
on x=41075..99376,y=-20427..49978,z=-52012..13762
on x=-21330..50085,y=-17944..62733,z=-112280..-30197
on x=-16478..35915,y=36008..118594,z=-7885..47086
off x=-98156..-27851,y=-49952..43171,z=-99005..-8456
off x=2032..69770,y=-71013..4824,z=7471..94418
on x=43670..120875,y=-42068..12382,z=-24787..38892
off x=37514..111226,y=-45862..25743,z=-16714..54663
off x=25699..97951,y=-30668..59918,z=-15349..69697
off x=-44271..17935,y=-9516..60759,z=49131..112598
on x=-61695..-5813,y=40978..94975,z=8655..80240
off x=-101086..-9439,y=-7088..67543,z=33935..83858
off x=18020..114017,y=-48931..32606,z=21474..89843
off x=-77139..10506,y=-89994..-18797,z=-80..59318
off x=8476..79288,y=-75520..11602,z=-96624..-24783
on x=-47488..-1262,y=24338..100707,z=16292..72967
off x=-84341..13987,y=2429..92914,z=-90671..-1318
off x=-37810..49457,y=-71013..-7894,z=-105357..-13188
off x=-27365..46395,y=31009..98017,z=15428..76570
off x=-70369..-16548,y=22648..78696,z=-1892..86821
on x=-53470..21291,y=-120233..-33476,z=-44150..38147
off x=-93533..-4276,y=-16170..68771,z=-104985..-24507
""".splitlines()
)
assert test_full_reboot.reboot() == 2758514936282235
print("Part 2:", reactor.reboot())
Part 2: 1130514303649907