import re
from functional import seq
import numpy as np
import time

f = open("in15.txt", "r", encoding="utf-8")
input = f.read().split("\n")
f.close()
input

start_time = time.time()

# Input formatting
points = seq(input)\
            .map(lambda line: re.findall("-?\d+", line))\
            .flatten()\
            .map(int)\
            .grouped(2)\
            .grouped(2)

man_distance = lambda p1,p2: abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
distances = points.map(lambda pair: man_distance(pair[0], pair[1]))

# Returns the lower and upper bound of blocked indices for a given y
def calculate_blocked_range(point, distance, y):
    distance_to_row = abs(point[1]-y)
    if distance_to_row > distance:
        return []
    remaining = distance-distance_to_row
    return[point[0]-remaining, point[0]+remaining]

# Actual work being done
find_blocked = lambda y: points\
                            .map(lambda pair: pair[0])\
                            .zip(distances)\
                            .map(lambda x: calculate_blocked_range(x[0], x[1], y))\
                            .filter(lambda x: len(x) != 0)

#Works because they overlap, too lazy to make a proper overlap combination
blocked = find_blocked(2000000).reduce(lambda x, y: [min(x[0], y[0]), max(x[1], y[1])])

print(abs(blocked[0]-blocked[1]))
print("--- %s seconds ---" % (time.time() - start_time))


start_time = time.time()

points_to_vector = lambda p1, p2: [p2[0]-p1[0], p2[1]-p1[1]]

# Build 4 vectors that run along the edges of the diamond-shaped areas
# Attach a base point to the vectors to be able to solve line equations
# [vector, solution]
def build_vector_solutions(sensor, distance):
    outer_edge_distance = distance+1
    right = [sensor[0]+outer_edge_distance, sensor[1]]
    left = [sensor[0]-outer_edge_distance, sensor[1]]
    up = [sensor[0], sensor[1]-outer_edge_distance]
    down = [sensor[0], sensor[1]+outer_edge_distance]
    vectors = [[points_to_vector(right,up), right],
               [points_to_vector(right,down),right],
               [points_to_vector(left,up),left],
               [points_to_vector(left,down),left]]
    return vectors

vectors = points\
    .map(lambda pair: pair[0])\
    .zip(distances)\
    .map(lambda s_d: build_vector_solutions(*s_d))


# Solve matrix using linear algebra with numpy
# Returns the intersection of two lines
calculate_solution = lambda point, vector: vector[0]*point[0] + vector[1]*point[1]
def solve(v_p1, v_p2):
    [v1, p1] = v_p1
    [v2, p2] = v_p2
    s1 = calculate_solution(p1,v1)
    s2 = calculate_solution(p2,v2)
    solution = []
    try:
        solution = np.linalg.solve(np.array([v1,v2]), np.array([s1,s2]))
    except:
        pass
    return solution


check_limits = lambda x ,y:  0 <=x and x<=4000000 and 0<=y and y<=4000000

# Create the list of every line intersections
#Keep only those within range and actual solutions
intersections = vectors\
    .flatten()\
    .cartesian(vectors.flatten())\
    .map(lambda p: solve(*p))\
    .filter(lambda x: len(x) !=0 and check_limits(*x))\
    .map(np.ndarray.tolist)

sensor_distances = points\
                    .map(lambda pair: pair[0])\
                    .zip(distances)

check_outside = lambda inter, sensor, distance: man_distance(inter, sensor) > distance

# For every intersection found, check if it's a solution
for intersection in intersections:
    is_outside = True
    for s_d in sensor_distances:
        is_outside = is_outside and check_outside(intersection, *s_d)
    if is_outside:
        print(intersection[0]*4000000+intersection[1])
        break
print("--- %s seconds ---" % (time.time() - start_time))