from dataclasses import dataclass from itertools import islice from sys import stdin from typing import Self, Type @dataclass(frozen=True, slots=True) class Pos: x: int y: int z: int def __add__(self, other: object) -> Self: if not isinstance(other, Pos): return NotImplemented return self.__class__(self.x + other.x, self.y + other.y, self.z + other.z) @classmethod def from_str(cls: Type[Self], s: str) -> Self: return cls(*map(int, s.split(",", maxsplit=2))) def min_max_pos(a: Pos, b: Pos) -> tuple[Pos, Pos]: minx, maxx = min(a.x, b.x), max(a.x, b.x) miny, maxy = min(a.y, b.y), max(a.y, b.y) minz, maxz = min(a.z, b.z), max(a.z, b.z) return Pos(minx, miny, minz), Pos(maxx, maxy, maxz) @dataclass(frozen=True, slots=True) class Brick: a: Pos b: Pos def xy_overlaps(self, other: Self) -> bool: return ( self.a.x <= other.b.x and self.b.x >= other.a.x and self.a.y <= other.b.y and self.b.y >= other.a.y ) def collides(self, other: Self) -> bool: return ( self.xy_overlaps(other) and self.a.z <= other.b.z and self.b.z >= other.a.z ) def __add__(self, other: object) -> Self: if not isinstance(other, Pos): return NotImplemented return self.__class__(self.a + other, self.b + other) @classmethod def from_str(cls, s: str): return Brick(*min_max_pos(*map(Pos.from_str, s.split("~", maxsplit=1)))) inp = [Brick.from_str(line.rstrip("\n")) for line in stdin] def simulate(inp: list[Brick]) -> int: motion = True fallen = set() inp.sort(key=lambda b: b.a.z) while motion: motion = False for i, b in enumerate(inp): if b.a.z <= 1: continue max_dz = b.a.z - 1 for other in islice(inp, 0, i): if not other.xy_overlaps(b): continue for dz in range( max(b.a.z - other.b.z, 1), min(max(b.a.z - other.a.z, 0), max_dz) + 1, ): if other.collides(b + Pos(0, 0, -dz)): max_dz = dz - 1 break if max_dz == 0: break if max_dz == 0: continue fallen.add(i) inp[i] = b + Pos(0, 0, -max_dz) motion = True return len(fallen) simulate(inp) print("settled") p1 = p2 = 0 for i, _ in enumerate(inp): copy = inp.copy() copy.pop(i) fallen = simulate(copy) if fallen == 0: p1 += 1 else: p2 += fallen print(f"{i} / {len(inp)}") print(p1) print(p2)