#!/usr/bin/env python3

# import numpy as np
from functools import reduce
from re import findall
from copy import deepcopy
import sys

# filename = "in/day15.ref"
filename = "in/day15.pzl"
data = open(filename).read()
lines = [line for line in data.rstrip('\n').split('\n')]

max_x = 0
min_x = 99999999

B = dict()
D = list()
for line in lines:
    w = line.split(' ')
    a = list()
    for i in [2,3,8,9]:
        a.append(int(w[i].split('=')[-1].rstrip(',').rstrip(':')))
    sx = a[0]
    sy = a[1]
    bx = a[2]
    by = a[3]
    B[(by,bx)] = 1
    dx = bx - sx
    dy = by - sy
    r = abs(dx) + abs(dy) + 1
    D.append((sy,sx,dy,dx, r))
    max_x = max(max_x, sx, bx)
    min_x = min(min_x, sx, bx)

# print(D)

def too_close(y, x):
    if (y,x) in B.keys():
        return False

    is_to_close = list()
    for sy,sx,dy,dx,r in D:
        if abs(y-sy) + abs(x-sx) <= abs(dy) + abs(dx):
            return True
    return False

# print('max_x', max_x)
# print('min_x', min_x)

def part1(y, tol):
    num = 0
    for x in range(min_x-tol, max_x+tol):
        ret = too_close(y,x)
        # if x % 10000 == 0:
        #     print(x, ret)
        if ret == True:
            num += 1
    return num

def part2(therange):
    counter = 0
    for (sy,sx,dy,dx,r) in D[::-1]:
        # print('range', r)
        for i in range(r):
            counter += 1
            # if counter % 100000 == 0:
            #     print('count', counter)
            for y,x in [(sy-i, sx+r-i), (sy-r+i, sx-i), (sy+i, sx-r+i), (sy+r-i, sx+i)]:
                if 0 <= x <= therange and 0 <= y <= therange:
                    ret = too_close(y,x)
                    if ret == False:
                        if (y,x) not in B.keys():
                            # print(y,x, ret, x*4000000+y, sy, sx)
                            return x*4000000+y
                            break

# res1 = part1(y=10, tol=20)
# res2 = part2(therange=20)

res1 = part1(y=2000000, tol=2000000)
res2 = part2(therange=4000000)

print('res1:', res1)
print('res2:', res2)