Day 24 - Advent of Code 2023

""" day_24_01.py """

# usage: python3 day_24_01.py 200000000000000 400000000000000 < input

import sys
from collections import namedtuple
from itertools import combinations
from math import isclose


Vector3 = namedtuple('Vector3', 'x, y, z')
NULL = Vector3(None, None, None)


def parse(text):
    """ extract coordinate and velocity """
    coordinate, velocity = text.split(' @ ')
    return (Vector3(*map(int, coordinate.split(', '))),
            Vector3(*map(int, velocity.split(', '))))


def line(coordinate, velocity):
    """ calculate coefficients ax + by + c = 0 """
    if velocity.x == 0:
        return (1, 0, -coordinate.x)
    gradient = velocity.y / velocity.x
    return (-gradient, 1, gradient * coordinate.x - coordinate.y)


def future_intersection(u, v):
    """ future intersection of u and v ignoring z axis """
    p1, v1 = parse(u)
    a1, b1, c1 = line(p1, v1)
    p2, v2 = parse(v)
    a2, b2, c2 = line(p2, v2)

    if b1 == 0 and b2 == 0:
        return NULL  # parallel vertical lines

    if b1 != 0:
        m1, y1 = -a1 / b1, -c1 / b1
    if b2 != 0:
        m2, y2 = -a2 / b2, -c2 / b2

    if b1 == 0:  # u is vertical
        x, y = p1.x, m2 * p1.x + y2
    elif b2 == 0:  # v is vertical
        x, y = p2.x, m1 * p2.x + y1
    else:
        if isclose(m1, m2):
            return NULL  # parallel lines
        x = (y2 - y1) / (m1 - m2)
        y = m2 * x + y2

    if (y - p2.y) / v2.y < 0 or (y - p1.y) / v1.y < 0:
        return NULL  # occurs in past for at least one hailstone

    return Vector3(x, y, None)


coord_min, coord_max = int(sys.argv[1]), int(sys.argv[2])
hailstones = sys.stdin.read().splitlines()

answer = 0
for i, j in combinations(hailstones, 2):
    p = future_intersection(i, j)
    if p == NULL:
        continue
    if coord_min <= p.x <= coord_max and coord_min <= p.y <= coord_max:
        answer += 1

print(answer)