Problem 163

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

三角形の数を数える簡単なお仕事。

そんなに簡単ではないが。

m = 36
layer n = tail.concat $ [map (<+>(6*n-k,k)) grid| k<-[,6..6*n]]++[[(6*(n+1),)]]
where grid = [(4,-2),(,3),(,6),(2,2),(3,),(3,3)]
onLine x y = any (prallel (x <-> y)).map head.line $ x <%> 6
where prallel (a,b) (c,d) = a*d==b*c
gridOnLine x = filter (not.null).map (lg x).line $ x <%> 6
where lg x = tail.takeWhile inner.scanl (<+>) x.cycle
inner (x,y) = y>= && x+y<=6*m
triangle a = [(b,c)| [l,k]<- comb 2 $ gridOnLine a,b<-l, c<-k,onLine b c]
main = print.sum.map (length.triangle).((,):).concatMap layer $ [..m-1]
comb  _ = [[]]
comb _ [] = []
comb (n+1) (x:xs) = map (x:) (comb n xs) ++ comb (n+1) xs
(<+>) (a,b) (c,d) = (a+c,b+d)
(<->) (a,b) (c,d) = (a-c,b-d)
(<%>) (a,b) c = (mod a c,mod b c)
line (,) = [[(,3)],
[(2,2),(1,1),(1,1),(2,2)],
[(3,)],
[(4,-2),(2,-1),(2,-1),(4,-2)],
[(3,-3)],
[(2,-4),(1,-2),(1,-2),(2,-4)]]
line (,3) = [[(,3)],
[(2,-1),(4,-2),(4,-2),(2,-1)]]
line (2,2) = [[(1,1),(1,1),(2,2),(2,2)],
[(4,-2),(4,-2),(2,-1),(2,-1)],
[(1,-2),(1,-2),(2,-4),(2,-4)]]
line (3,) = [[(3,)],
[(1,-2),(2,-4),(2,-4),(1,-2)]]
line (4,4) = [[(2,2),(2,2),(1,1),(1,1)],
[(2,-1),(2,-1),(4,-2),(4,-2)],
[(2,-4),(2,-4),(1,-2),(1,-2)]]
line (3,3) = [[(1,1),(2,2),(2,2),(1,1)],
[(3,-3)]]

座標変換(正三角形を直角二等辺三角形に)して格子点の座標が整数になるようにした。

格子点の種類が割り算のあまりでわかる。

まあ、全探索ですが、計算量が良く分からないなぁ。

問題の状況では格子点は約4000個(プログラムによると)

三角形かどうかチェックした格子点の組の数は約10^7個(プログラムによると)

だから、格子点の数に関して2乗ぐらい?(根拠がないなー)

More Reading
Older// Problem 164