day 11

1 files changed, 38 insertions, 0 deletions

diff --git a/11.py b/11.py
new file mode 100644
index 0000000..645c6c7
--- /dev/null
+++ b/11.py
@@ -0,0 +1,38 @@
+# pyright: strict
+from itertools import accumulate, combinations
+from sys import stdin
+
+
+def offsets(length: int, present: set[int]) -> list[int]:
+    return list(accumulate(1 if i not in present else 0 for i in range(length)))
+
+
+def solve(
+    points: set[tuple[int, int]],
+    x_offsets: list[int],
+    y_offsets: list[int],
+    expansion: int = 2,
+) -> int:
+    def offset(p: tuple[int, int]) -> tuple[int, int]:
+        return (
+            p[0] + x_offsets[p[0]] * (expansion - 1),
+            p[1] + y_offsets[p[1]] * (expansion - 1),
+        )
+
+    def manhattan_distance(a: tuple[int, int], b: tuple[int, int]) -> int:
+        return abs(a[0] - b[0]) + abs(a[1] - b[1])
+
+    return sum(
+        manhattan_distance(offset(a), offset(b)) for a, b in combinations(points, 2)
+    )
+
+
+points = {(x, y) for y, l in enumerate(stdin) for x, c in enumerate(l) if c == "#"}
+
+x_present, y_present = set(p[0] for p in points), set(p[1] for p in points)
+width, height = max(x for x in x_present) + 1, max(y for y in y_present) + 1
+x_offsets = offsets(width, x_present)
+y_offsets = offsets(height, y_present)
+
+print(solve(points, x_offsets, y_offsets))
+print(solve(points, x_offsets, y_offsets, 1000000))