From 0ef867a34e8dd3d042f003f50ad8ea012549993e Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Mon, 11 Dec 2023 12:51:20 +0000 Subject: day 11 --- 11.py | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) create mode 100644 11.py 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)) -- cgit v1.2.3-54-g00ecf