import re
import functools
from geometry import Point

def get_bbox(points):
    left, right, top, bottom = [f(getattr(p, d) for p in points) for d in "xy" for f in (min, max)]
    return left, right, top, bottom

def width(points):
    left, right, _, _ = get_bbox(points)
    return right - left

def display(points):
    left, right, top, bottom = get_bbox(points)
    matrix = [["." for i in range(left, right+1)] for j in range(top, bottom+1)]
    for p in points:
        matrix[p.y-top][p.x-left] = "#"
    print("\n".join("".join(row) for row in matrix))

def find_local_min(f, appx_x):
    """search around the general region of appx_t for a local minima."""
    f = functools.lru_cache()(f)
    #decide which direction to climb by examining the neighboring values of appx_t
    l = g(appx_x-1)
    m = g(appx_x)
    r = g(appx_x+1)
    if m <= r and m <= l:
        return appx_x
    elif r < m:
        delta = +1
    elif l < m:
        delta = -1

    x = appx_x
    while True:
        if f(x) < f(x+delta):
            return x
        x += 1

points = []
velocities = []
with open("input10") as file:
    for line in file:
        #can't use extract_digit_sequences here because some digits are negative
        x,y, dx, dy = [int(x) for x in re.findall(r"-?\d+", line)]
        points.append(Point(x,y))
        velocities.append(Point(dx,dy))

#gives the coordinates of each point at time t
f = lambda t: [p + v*t for p,v in zip(points, velocities)]

#heuristic 1: choose two points with different x velocities. Calculate the time at which these points have the same x coordinate. The solution is near this time.
p0, v0 = min(zip(points, velocities), key=lambda t:t[1].x)
p1, v1 = max(zip(points, velocities), key=lambda t:t[1].x)
assert v0.x != v1.x, "heuristic fails when all points have identical x velocities"
appx_t = int((p0.x - p1.x) / (v1.x - v0.x))

#heuristic 2: the solution occurs when the bounding box has the smallest width.
g = lambda t: width(f(t))
t = find_local_min(g, appx_t)
display(f(t))
print(t)