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)