70 lines
1.7 KiB
Python
70 lines
1.7 KiB
Python
|
from pprint import pprint
|
||
|
|
import fileinput
|
||
|
|
import itertools
|
||
|
|
import numpy
|
||
|
|
|
||
|
|
def distance(a, b):
|
||
|
|
ax, ay = a
|
||
|
|
bx, by = b
|
||
|
|
return abs(ax - bx) + abs(ay - by)
|
||
|
|
|
||
|
|
coordinates = []
|
||
|
|
for line in fileinput.input():
|
||
|
|
x, y = line.strip().split(", ")
|
||
|
|
coordinates.append((int(x), int(y)))
|
||
|
|
xs, ys = numpy.transpose(coordinates)
|
||
|
|
|
||
|
|
def nearest_neighbor(x, y):
|
||
|
|
closest = -1
|
||
|
|
dist = 10000
|
||
|
|
for i, coord in enumerate(coordinates):
|
||
|
|
d = distance((x, y), coord)
|
||
|
|
if d < dist:
|
||
|
|
closest = i
|
||
|
|
dist = d
|
||
|
|
elif d == dist:
|
||
|
|
closest = -1
|
||
|
|
|
||
|
|
return closest
|
||
|
|
|
||
|
|
def calc_farthest(padding):
|
||
|
|
|
||
|
|
xmin, xmax = min(xs) - padding, max(xs) + padding
|
||
|
|
ymin, ymax = min(ys) - padding, max(ys) + padding
|
||
|
|
w, h = xmax - xmin, ymax - ymin
|
||
|
|
|
||
|
|
grid = numpy.zeros((h + 1, w + 1), dtype=numpy.int16) - 1
|
||
|
|
for y, row in enumerate(grid):
|
||
|
|
for x in range(len(row)):
|
||
|
|
nn = nearest_neighbor(x + xmin, y + ymin)
|
||
|
|
if nn is not None:
|
||
|
|
grid[y, x] = nn
|
||
|
|
|
||
|
|
flat = grid.flatten()
|
||
|
|
flat = flat[flat >= 0]
|
||
|
|
|
||
|
|
return numpy.bincount(flat)
|
||
|
|
|
||
|
|
def part1():
|
||
|
|
small = calc_farthest(0)
|
||
|
|
big = calc_farthest(10)
|
||
|
|
print(small[small == big].max())
|
||
|
|
|
||
|
|
def part2():
|
||
|
|
padding = 5
|
||
|
|
max_dist = 10000
|
||
|
|
|
||
|
|
xmin, xmax = min(xs) - padding, max(xs) + padding
|
||
|
|
ymin, ymax = min(ys) - padding, max(ys) + padding
|
||
|
|
w, h = xmax - xmin, ymax - ymin
|
||
|
|
|
||
|
|
grid = numpy.zeros((h + 1, w + 1), dtype=numpy.int16) - 1
|
||
|
|
size = 0
|
||
|
|
for y, row in enumerate(grid):
|
||
|
|
for x in range(len(row)):
|
||
|
|
s = sum(distance((x + xmin, y + ymin), c) for c in coordinates)
|
||
|
|
if s < max_dist:
|
||
|
|
size += 1
|
||
|
|
|
||
|
|
print(size)
|