In [1]:

    

import numpy as np
from itertools import product


    

In [2]:

    

l = ! cat input.txt | tr '\n' ';'
l = l[0].rstrip(';').split(';')
l = list(map(lambda v: np.array(list(map(lambda x: int(x), v.split(', ')))), l))


    

In [18]:

    

def find_infinite(points):
    infinite = []
    for p in points:
        if has_empty_flank(p, points):
            infinite.append(p)
    return infinite

def has_empty_flank(p, points):
    flank_empty = False
    for gamma, omega in product([-1, 1], repeat=2):
        s = in_flank(p, points, gamma, omega)
        if len(s) == 0:
            flank_empty = True
            break
    return flank_empty

def in_flank(p, points, gamma, omega):
    gammav = np.array([1, -1])
    omegav = np.array([1, 1])
    flanking_set = []
    for q in points:
        if not np.all(q == p):
            eq1 = gamma * np.dot(gammav, q - p)
            eq2 = omega * np.dot(omegav, q - p)
            if (eq1 >= 0) and (eq2 >= 0):
                flanking_set.append(q)
    return flanking_set


    

In [24]:

    

def largest_finite_area(points):
    largest = 0
    infinite = list(map(tuple, find_infinite(points)))
    for p in points:
        if tuple(p) not in infinite:
            area = len(find_closest_set(p, points))
            if area > largest:
                largest = area
    return largest + 1

def find_closest_set(p, points):
    acc = []
    r = 1
    is_ball_empty = False
    while not is_ball_empty:
        is_ball_empty = True
        for x in ball(p, r):
            if is_closest(x, p, points):
                acc.append(x)
                is_ball_empty = False
        r += 1
    return acc
            
def ball(center, radius):
    for i in range(-radius, radius + 1):
        for j in set([radius - abs(i), abs(i) - radius]):
            yield center + np.array([i, j])

def dist(a, b):
    return np.sum(np.abs(a - b))
            
def is_closest(x, p, points):
    d = dist(x, p)
    draw = False
    for q in points:
        if not np.all(q == p):
            if dist(x, q) < d:
                return False
            elif dist(x, q) == d:
                draw = True
    if draw:
        return False
    return True


    

In [28]:

    

t = [np.array([1, 1]), np.array([1, 6]), np.array([8, 3]), 
     np.array([3, 4]), np.array([5, 5]), np.array([8, 9])]
largest_finite_area(t)


    

    
Out[28]:





17

In [29]:

    

largest_finite_area(l)


    

    
Out[29]:





3687

In [32]:

    

def is_within(p, points, thresh):
    acc = 0
    for q in points:
        acc += dist(p, q)
        if acc >= thresh:
            return False
    return True

def all_within(points, thresh):
    acc = []
    for p in points:
        r = 0
        is_ball_empty = False
        while not is_ball_empty:
            is_ball_empty = True
            for q in ball(p, r):
                if (tuple(q) not in acc) and is_within(q, points, thresh):
                    acc.append(tuple(q))
                    is_ball_empty = False
            r += 1
    return len(acc)


    

In [33]:

    

all_within(t, 32)


    

    
Out[33]:





16

In [34]:

    

all_within(l, 10000)


    

    
Out[34]:





40134