1  from lib import *
 2  
 3  input = read_input(2021, 22)
 4  
 5  lines = input.splitlines()
 6  
 7  
 8  def line_intersection(a1, a2, b1, b2):
 9      if a2 < b1 or b2 < a1:
10          return None
11  
12      return max(a1, b1), min(a2, b2)
13  
14  
15  @dataclass
16  class Cuboid:
17      x1: int
18      x2: int
19      y1: int
20      y2: int
21      z1: int
22      z2: int
23      off = None
24  
25      def get_intersection(self, other):
26          x = line_intersection(self.x1, self.x2, other.x1, other.x2)
27  
28          y = line_intersection(self.y1, self.y2, other.y1, other.y2)
29  
30          z = line_intersection(self.z1, self.z2, other.z1, other.z2)
31  
32          if None in [x, y, z]:
33              return None
34  
35          return Cuboid(*x, *y, *z)
36  
37      def subtract(self, other):
38          if intersection := self.get_intersection(other):
39              if not self.off:
40                  self.off = []
41  
42              for o in self.off:
43                  o.subtract(other)
44  
45              self.off.append(intersection)
46  
47      def volume(self):
48          return (self.x2 - self.x1 + 1) * (self.y2 - self.y1 + 1) * (self.z2 - self.z1 + 1) - sum(
49              o.volume() for o in self.off or []
50          )
51  
52  
53  cuboids = []
54  for line in lines:
55      match = re.match(r"^(on|off) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)$", line)
56      if any(x not in range(-50, 51) for x in map(int, match.groups()[1:])):
57          continue
58  
59      on = match.group(1) == "on"
60      cuboid = Cuboid(*map(int, match.groups()[1:]))
61  
62      for c in cuboids:
63          c.subtract(cuboid)
64      if on:
65          cuboids.append(cuboid)
66  
67  print(sum(c.volume() for c in cuboids))
68  
69  
70  cuboids = []
71  for line in lines:
72      match = re.match(r"^(on|off) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)$", line)
73      on = match.group(1) == "on"
74      cuboid = Cuboid(*map(int, match.groups()[1:]))
75      for c in cuboids:
76          c.subtract(cuboid)
77      if on:
78          cuboids.append(cuboid)
79  
80  print(sum(c.volume() for c in cuboids))