Skip to content

Instantly share code, notes, and snippets.

@crclark96
Last active April 27, 2020 12:22
Show Gist options
  • Save crclark96/216135e41ed656451771e1be1931ba70 to your computer and use it in GitHub Desktop.
Save crclark96/216135e41ed656451771e1be1931ba70 to your computer and use it in GitHub Desktop.
*Main> maxPointsOnLine [(1,1), (3,2), (5,3), (4,1), (2,3), (1,4)]
4
import Data.List
import Data.Ord
type Point = (Float, Float)
data Line = Line { yInt :: Float, slope :: Float } deriving (Eq, Show, Ord)
lineFromPoints :: Point -> Point -> Line
lineFromPoints p1 p2 = Line { slope = s, yInt = snd p1 - s * fst p1 }
where x = fst p2 - fst p1
y = snd p2 - snd p1
s = y / x
maxPointsOnLine :: [Point] -> Int
maxPointsOnLine ps = 1 + n
where n = maximum . concat $ -- find max freq
[map length . group . sort $ -- get freq of lines
[lineFromPoints x y | y <- ys ] -- find lines b/w
| (x:ys) <- tails ps] -- all unique pairs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment