http://projecteuler.net/index.php?section=problems&id=28
螺旋を1歩ずつ辿っていくとこう書ける。ただし、遅い。
n = 1001
next (x, y) | y >= 0 && y >= abs(x) = (x + 1, y)
| x < 0 && -x >= abs(y) = (x, y + 1)
| y < 0 && -y >= abs(x) = (x - 1, y)
| otherwise = (x, y - 1)is_diagonal (x, y) = abs(x) == abs(y)
a = (0, 0):[ next(pt) | pt <- a ]
main = print(sum(map (\(id, _) -> id)
(filter (\(id, pt) -> is_diagonal pt) (zip [1..n^2] a))))
線形時間で計算しようと思うと、対角線だけ順番に辿って、
n = 1001
m = div n 2
make_diagonal num step = [ num + step * k | k <- [1..4 ] ]
++ (make_diagonal (num + step * 4) (step + 2))
main = print(1 + (sum (take (m * 4) (make_diagonal 1 2))))
