Project Euler 165

プロジェクトオイラー
http://projecteuler.net/index.php

Q165.
与えられた疑似乱数で発生させた5000本の線分の真の交点の個数

ただ交点を求めていくだけ。同じ交点は重複して数えないので、setにaddしていく。しかし、3300本目くらいからメモリが足りなくなって、なかなか動かなくなった。分数の座標を格納するのをやめて、xの分子・xの分母・yの分子・yの分母というタプルにして格納したら、メモリを節約できて計算が終わった。



from fractions import Fraction
import time

def gen_random():
s = 290797
while True:
s = s * s % 50515093
t = s % 500
yield int(t)

def determine_true_intersect(line1, line2):
a = line1[2]
b = -line2[2]
c = line1[3]
d = -line2[3]
D = a * d - b * c
if D == 0:
return False

x = line2[0] - line1[0]
y = line2[1] - line1[1]
s = d * x - b * y
t = -c * x + a * y

if D > 0:
if 0 < s and s < D and 0 < t and t < D:
s = Fraction(s, D)
else:
return False
else:
if 0 < -s and -s < -D and 0 < -t and -t < -D:
s = Fraction(s, D)
else:
return False

return (line1[0] + s * line1[2], line1[1] + s * line1[3])

t = time.clock()
N = 5000
lines = [ ]
intersections = set()

g = gen_random()
for k in range(N):
x1 = g.next()
y1 = g.next()
l = (x1, y1, g.next() - x1, g.next() - y1)
lines.append(l)

for i in range(N - 1):
if i % 50 == 0:
print i
for j in xrange(i + 1, N):
pt = determine_true_intersect(lines[i], lines[j])
if pt:
intersections.add((pt[0].numerator, pt[0].denominator,
pt[1].numerator, pt[1].denominator))

print len(intersections)
print time.clock() - t