# pyright: strict from collections.abc import Callable, Iterable, Iterator from dataclasses import dataclass from itertools import accumulate, combinations, starmap from sys import stdin from typing import Self @dataclass(frozen=True, slots=True) class Point: x: int y: int def distance(self, other: Self) -> int: return abs(self.x - other.x) + abs(self.y - other.y) def __add__(self, other: Self) -> Self: return self.__class__(self.x + other.x, self.y + other.y) 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 dists(points: Iterable[Point]) -> Iterator[int]: return starmap(Point.distance, combinations(points, 2)) def offsetter( x_offsets: list[int], y_offsets: list[int], factor: int = 2 ) -> Callable[[Point], Point]: scale = factor - 1 def f(p: Point) -> Point: return p + Point(x_offsets[p.x] * scale, y_offsets[p.y] * scale) return f points = {Point(x, y) for y, l in enumerate(stdin) for x, c in enumerate(l) if c == "#"} x_present, y_present = set(p.x for p in points), set(p.y 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(sum(dists(map(offsetter(x_offsets, y_offsets), points)))) print(sum(dists(map(offsetter(x_offsets, y_offsets, 1000000), points))))