python-max-collinear-points-gcd
The full solution is at ~/solution.py. Core algorithm (per-anchor O(n²), gcd-normalized direction vectors, no floats):
import math
from collections import defaultdict
def max_points(points):
"""Max number of points on a single line (duplicates allowed)."""
n = len(points)
if n <= 2: # empty -> 0, single -> 1, pair -> 2
return n
best = 1
for i in range(n):
if n - i <= best: # even all remaining points can't beat best
break
xi, yi = points[i]
dup = 1 # anchor itself
slopes = defaultdict(int)
for j in range(i + 1, n):
dx = points[j][0] - xi
dy = points[j][1] - yi
if dx == 0 and dy == 0:
dup += 1 # duplicate coordinate of the anchor
continue
g = math.gcd(abs(dx), abs(dy))
dx //= g; dy //= g
if dx < 0 or (dx == 0 and dy < 0): # canonical sign
dx, dy = -dx, -dy
slopes[(dx, dy)] += 1
cur = dup
for c in slopes.values():
cur = max(cur, c + dup) # duplicates count on every slope
best = max(best, cur)
return best
Key design points
- Per-anchor with j > i only: each ordered pair is examined once from the smaller index. The max line is fully counted when the smallest-index point on it is the anchor (all other points on the line have larger indices).
- gcd normalization + canonical sign: (dx,dy) divided by gcd(|dx|,|dy|), then flipped so the first component is ≥ 0 (vertical lines → dy > 0). This makes (1,-1)/(-1,1) and (0,-1)/(0,1) collide in one bucket — no floating point anywhere.
- Duplicates: points identical to the anchor increment dup, added to every slope bucket (a duplicate is on any line through the anchor). Duplicates of other points are counted normally since they satisfy the line equation.
- Vertical/horizontal/single-point: handled naturally — vertical gives (0,1) buckets; n ≤ 2 returns n directly.
- Early exit n - i <= best: anchor i can never beat best using only points j ≥ i (those with smaller index were already accounted for by earlier anchors). Turns all-collinear inputs into O(n) and bounds constant overhead elsewhere.
main() validates in this order:
1. 3000 random small cases (n ≤ 14, tiny coordinate ranges to force duplicates/collinearities) vs an O(n³) brute force.
2. Exhaustive sweep: all 512 subsets of a 3×3 grid + 300 random 4×4 subsets, vs brute force.
3. 13 targeted edge cases (empty, single point, all-duplicates, vertical+dup, horizontal, both direction signs, duplicates inside the line, coordinate extremes ±10⁴).
4. Medium sanity (n=2000, must finish quickly).
5. Worst-case timeout: 10⁵ random points run under a 3 s SIGALRM/ITIMER_REAL budget — run_with_timeout raises TimeoutExpired inside the deep loop, main catches it, prints a message, and exits 0 (no hang, no crash).
def run_with_timeout(func, arg, seconds):
old = signal.getsignal(signal.SIGALRM)
signal.signal(signal.SIGALRM, _alarm_handler) # raises TimeoutExpired
signal.setitimer(signal.ITIMER_REAL, seconds)
try:
return func(arg)
finally:
signal.setitimer(signal.ITIMER_REAL, 0)
signal.signal(signal.SIGALRM, old)
Verified by executing `python3 solution.py` plus an independent stress run: | Check | Result | |---|---| | Random small vs brute (3000 trials, seed 0xC0FFEE) | 0 mismatches | | Exhaustive 3×3 grid, all 512 subsets | 0 mismatches | | Random 4×4 subsets (300) | 0 mismatches | | Targeted edge cases (13) | all pass | | Extra stress: 5000 trials, n ≤ 20, ranges up to 30, seed 424242 | 0 mismatches | | Medium n=2000 (random) | best=3 in 1.01s | | Worst case n=10⁵ | **timed out cleanly after 3.00s**, exit 0 | **O(n²) scaling evidence** (random points, best≈2 → no early exit): ``` n= 500 best=2 time=0.038s n= 1000 best=3 time=0.153s (×4.0 for ×2 n) n= 2000 best=3 time=0.615s (×4.0) n= 4000 best=4 time=2.757s (×4.5) ``` This extrapolates to ~1500 s for n=10⁵, confirming the 3 s budget tripping is genuine O(n²) behavior, not a bug. Notable edge cases covered: all-identical points → n; vertical line with duplicate anchor → 4; `[(0,0),(1,1),(1,1),(2,2)]` → 4 (duplicate inside the line); `[(0,0),(2,2),(1,1),(-1,-1),(-2,-2)]` → 5 (both direction signs); `[(7,7)×3,(8,8),(6,6),(5,5)]` → 6 (cross-checked: all 6 lie on y=x, confirmed equal to brute force).
{"model": "deepseek-v4-flash", "problem_class": "python-max-collinear-points-gcd", "result": "passed", "tests": 8826}The full solution is at ~/solution.py. Core algorithm (per-anchor O(n²), gcd-normalized direction vectors, no floats):
import math
from collections import defaultdict
def max_points(points):
"""Max number of points on a single line (duplicates allowed)."""
n = len(points)
if n <= 2: # empty -> 0, single -> 1, pair -> 2
return n
best = 1
for i in range(n):
if n - i <= best: # even all remaining points can't beat best
break
xi, yi = points[i]
dup = 1 # anchor itself
slopes = defaultdict(int)
for j in range(i + 1, n):
dx = points[j][0] - xi
dy = points[j][1] - yi
if dx == 0 and dy == 0:
dup += 1 # duplicate coordinate of the anchor
continue
g = math.gcd(abs(dx), abs(dy))
dx //= g; dy //= g
if dx < 0 or (dx == 0 and dy < 0): # canonical sign
dx, dy = -dx, -dy
slopes[(dx, dy)] += 1
cur = dup
for c in slopes.values():
cur = max(cur, c + dup) # duplicates count on every slope
best = max(best, cur)
return best
Key design points
- Per-anchor with j > i only: each ordered pair is examined once from the smaller index. The max line is fully counted when the smallest-index point on it is the anchor (all other points on the line have larger indices).
- gcd normalization + canonical sign: (dx,dy) divided by gcd(|dx|,|dy|), then flipped so the first component is ≥ 0 (vertical lines → dy > 0). This makes (1,-1)/(-1,1) and (0,-1)/(0,1) collide in one bucket — no floating point anywhere.
- Duplicates: points identical to the anchor increment dup, added to every slope bucket (a duplicate is on any line through the anchor). Duplicates of other points are counted normally since they satisfy the line equation.
- Vertical/horizontal/single-point: handled naturally — vertical gives (0,1) buckets; n ≤ 2 returns n directly.
- Early exit n - i <= best: anchor i can never beat best using only points j ≥ i (those with smaller index were already accounted for by earlier anchors). Turns all-collinear inputs into O(n) and bounds constant overhead elsewhere.
main() validates in this order:
1. 3000 random small cases (n ≤ 14, tiny coordinate ranges to force duplicates/collinearities) vs an O(n³) brute force.
2. Exhaustive sweep: all 512 subsets of a 3×3 grid + 300 random 4×4 subsets, vs brute force.
3. 13 targeted edge cases (empty, single point, all-duplicates, vertical+dup, horizontal, both direction signs, duplicates inside the line, coordinate extremes ±10⁴).
4. Medium sanity (n=2000, must finish quickly).
5. Worst-case timeout: 10⁵ random points run under a 3 s SIGALRM/ITIMER_REAL budget — run_with_timeout raises TimeoutExpired inside the deep loop, main catches it, prints a message, and exits 0 (no hang, no crash).
def run_with_timeout(func, arg, seconds):
old = signal.getsignal(signal.SIGALRM)
signal.signal(signal.SIGALRM, _alarm_handler) # raises TimeoutExpired
signal.setitimer(signal.ITIMER_REAL, seconds)
try:
return func(arg)
finally:
signal.setitimer(signal.ITIMER_REAL, 0)
signal.signal(signal.SIGALRM, old)
Verified by executing `python3 solution.py` plus an independent stress run: | Check | Result | |---|---| | Random small vs brute (3000 trials, seed 0xC0FFEE) | 0 mismatches | | Exhaustive 3×3 grid, all 512 subsets | 0 mismatches | | Random 4×4 subsets (300) | 0 mismatches | | Targeted edge cases (13) | all pass | | Extra stress: 5000 trials, n ≤ 20, ranges up to 30, seed 424242 | 0 mismatches | | Medium n=2000 (random) | best=3 in 1.01s | | Worst case n=10⁵ | **timed out cleanly after 3.00s**, exit 0 | **O(n²) scaling evidence** (random points, best≈2 → no early exit): ``` n= 500 best=2 time=0.038s n= 1000 best=3 time=0.153s (×4.0 for ×2 n) n= 2000 best=3 time=0.615s (×4.0) n= 4000 best=4 time=2.757s (×4.5) ``` This extrapolates to ~1500 s for n=10⁵, confirming the 3 s budget tripping is genuine O(n²) behavior, not a bug. Notable edge cases covered: all-identical points → n; vertical line with duplicate anchor → 4; `[(0,0),(1,1),(1,1),(2,2)]` → 4 (duplicate inside the line); `[(0,0),(2,2),(1,1),(-1,-1),(-2,-2)]` → 5 (both direction signs); `[(7,7)×3,(8,8),(6,6),(5,5)]` → 6 (cross-checked: all 6 lie on y=x, confirmed equal to brute force).
{"model": "deepseek-v4-flash", "problem_class": "python-max-collinear-points-gcd", "result": "passed", "tests": 8826}