82 lines
2.7 KiB
Python
82 lines
2.7 KiB
Python
#!/usr/bin/env python3
|
|
# -*- coding: utf-8 -*-
|
|
import re
|
|
from time import time
|
|
import numpy as np
|
|
|
|
start_time = time()
|
|
file = "./input.txt"
|
|
XY_MIN = 200000000000000
|
|
XY_MAX = 400000000000000
|
|
#file = "./ex.txt"
|
|
#XY_MIN = 7
|
|
#XY_MAX = 27
|
|
|
|
|
|
def berechne_schnittpunkt(p1, v1, p2, v2):
|
|
"""
|
|
Berechnet den Schnittpunkt zweier Strahlen.
|
|
:param p1: Startpunkt des ersten Strahls (x, y)
|
|
:param v1: Richtungsvektor des ersten Strahls (vx, vy)
|
|
:param p2: Startpunkt des zweiten Strahls (x, y)
|
|
:param v2: Richtungsvektor des zweiten Strahls (vx, vy)
|
|
:return: Schnittpunkt als (x, y) oder None, wenn kein Schnittpunkt existiert
|
|
"""
|
|
# Umwandeln in NumPy-Arrays für einfachere Berechnungen
|
|
p1, v1, p2, v2 = map(np.array, [p1, v1, p2, v2])
|
|
# Matrix A für das Gleichungssystem
|
|
m_a = np.column_stack((v1, -v2))
|
|
# Vektor b für das Gleichungssystem
|
|
b = p2 - p1
|
|
try:
|
|
# Lösen des Gleichungssystems
|
|
t = np.linalg.solve(m_a, b)
|
|
# Überprüfen, ob die Lösungen positiv sind (Strahlen, nicht Geraden)
|
|
if t[0] >= 0 and t[1] >= 0:
|
|
# Berechnung des Schnittpunkts
|
|
schnittpunkt = p1 + t[0] * v1
|
|
return tuple(schnittpunkt)
|
|
else:
|
|
return None # Kein Schnittpunkt im positiven Bereich der Strahlen
|
|
except np.linalg.LinAlgError:
|
|
# Falls das Gleichungssystem nicht lösbar ist (parallele Strahlen)
|
|
return None
|
|
|
|
def read_input(filename:str)->list[list[int]]:
|
|
result = []
|
|
input_file = open(filename, "r")
|
|
for line in input_file:
|
|
line = line.strip()
|
|
if line == "":
|
|
continue
|
|
else:
|
|
pat = r'^(-?\d+), +(-?\d+), +-?\d+ +\@ +(-?\d+), +(-?\d+), +-?\d+$'
|
|
match = re.match(pat, line)
|
|
result.append(list(map(int,[match.group(1), match.group(2), match.group(3), match.group(4)])))
|
|
input_file.close()
|
|
return result
|
|
|
|
if __name__ == "__main__":
|
|
sol = 0
|
|
''' # Beispielaufruf
|
|
p_1 = (18, 19)
|
|
v_1 = (-1, -1)
|
|
p_2 = (12, 31)
|
|
v_2 = (-1, -2)
|
|
schnitt_punkt = berechne_schnittpunkt(p_1, v_1, p_2, v_2)
|
|
if schnitt_punkt:
|
|
print(f"Der Schnittpunkt liegt bei: {schnitt_punkt[0]} {schnitt_punkt[1]}")
|
|
else:
|
|
print("Die Strahlen schneiden sich nicht.")
|
|
'''
|
|
|
|
d = read_input(file)
|
|
for i in range(len(d)):
|
|
for j in range(i+1, len(d)):
|
|
s = berechne_schnittpunkt((d[i][0],d[i][1]), (d[i][2],d[i][3]),
|
|
(d[j][0],d[j][1]), (d[j][2],d[j][3]))
|
|
if s and XY_MIN < s[0] < XY_MAX and XY_MIN < s[1] < XY_MAX:
|
|
sol += 1
|
|
print(f"Solution Part1: {sol}")
|
|
print(f'Runtime: {time()-start_time:.2f} s')
|