Problem 184

http://projecteuler.net/index.php?section=problems&id=184

三角形を頂点ではなく、頂点と原点を結ぶ直線で考えた。

import Data.Function (on)
import Data.Map (fromListWith,toList)
choose :: [a] -> Int -> [[a]]
choose _  = [[]]
choose [] _ = []
choose (x:xs) (n+1) = [x:ys|ys<-choose xs n]++choose xs (n+1)
gridLines :: Integral a => a -> [(a,a)]
gridLines r = ((r-1,2):).((d,2):).toList.fromListWith (+) $
[(count x y,4)| x <- [1..r-1], y <- [x+1..sqrt'$ r^2-x^2-1], gcd x y == 1]
where sqrt' = floor.sqrt.fromIntegral
count x y = floor.sqrt.on (/) fromIntegral (r^2-1) $ x^2+y^2
d = floor $ fromIntegral r / sqrt 2
triangles :: Integral a => a -> a
triangles r = sum.map count.concatMap (choose.gridLines $ r) $ [1,2,3]
where count [(g,n)] = (g^3*n*(n-1)*(n-2)) `div` 3
count [(g1,n1),(g2,n2)] = g1*n1*g2*n2*(g1*(n1-1)+g2*(n2-1))
count gns = (2*).product.map (uncurry (*)) $ gns
main = print.triangles $ 105
More Reading
Older// Problem 181