I thought I was making a really inefficient algorithm for this, but then it ends up I was getting the answer in less than 5 seconds. The challenge thus was not the algorithm or the math, but actually in how I was going to deal with possible floating point arithmetic. I first submitted my answer by actually calculating the float values of the slope and y-intercept. However, this got me the wrong answer. I tried again using Python’s Decimal module. This yielded a different result, but it was still wrong. Instead I decided to go the route of reduced fractions. I implemented a quick greatest common divisor function and used that to reduce the fractions. I was worried this would be really inefficient, but it wasn’t.
def points(n):
s0 = 290797
i = 0
pnts = []
while i < n:
s1 = (s0 ** 2) % 50515093
t0 = (s1 % 2000) - 1000
s2 = (s1 ** 2) % 50515093
t1 = (s2 % 2000) - 1000
pnts.append((t0, t1))
s0 = s2
i += 1
return pnts
def gcd(x, y):
while y:
x, y = y, x % y
return x
def reduce(a, b):
d = gcd(a, b)
return a // d, b // d
def equation(p0, p1):
rise = p0[1] - p1[1]
run = p0[0] - p1[0]
if run == 0:
return (1, 0, p0[0], 1)
rise, run = reduce(rise, run)
y_num = (p0[1] * run) - (p0[0] * rise)
y_den = run
y_num, y_den = reduce(y_num, y_den)
return (rise, run, y_num, y_den)
def equations(n):
equ = {}
pnts = points(n)
while pnts:
pnt = pnts.pop()
for p in pnts:
equ[equation(pnt, p)] = True
return equ
def solve(n):
slopes = {}
for rise, run, _, _ in equations(n):
slopes[(rise, run)] = slopes.get((rise, run), 0) + 1
counts = list(slopes.values())
total = 0
summ = sum(counts)
while counts:
count = counts.pop()
summ -= count
total += count * summ
return total * 2
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve, points
_test_solve = (
(3, 6),
(100, 24477690),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)
_test_points = (
(3, [(527, 144), (-488, 732), (-454, -947)]),
)
@pytest.mark.parametrize('n,expect', _test_points)
def test_points(n, expect):
assert expect == points(n)