1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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))
|
