Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Normalize every direction from one anchor: The Collinear Stars.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Maximum points on a line matches the clues
- 2Keep this true after every move: each slope key counts exactly the points sharing that directed line from the anchor
- 3Reach the result within O(n squared log coordinate) time
Rules and pressure
- Target cost: O(n squared log coordinate) time
- State rule: each slope key counts exactly the points sharing that directed line from the anchor
Lesson 1 of 3
Live algorithm trace
Maximum points on a line
Complete execution1 of 5
Choose point 1,1 as the current anchor.
1
choose each point as anchor2
compute dx and dy to every later point3
divide direction by gcd(abs(dx),abs(dy))4
normalize sign and vertical/horizontal forms5
count equal direction keys6
return largest count plus anchoranchor = 1,1
Truth to preserve / Cost target
Truth to preserve
each slope key counts exactly the points sharing that directed line from the anchor
Cost target
O(n squared log coordinate) time
For each anchor, reduce every direction vector by its greatest common divisor and normalize its sign. Equal normalized directions identify points on the same line through that anchor.
Your call · What should guide every step of this algorithm?