Advent of Code 2017 Day 3, Part 1

AOC2017Day3Part1.hs

module AOC2017 where

{-
daythree

Observation that cycles are of length 8n
(/ mod four sides of the square) so each
cycle's index starts at (2n-1)^2:

n  cycle/4           length  index
1  1 2                   8      1
2  3 2 3 4              16      9
3  5 4 3 4 5 6          24     25
4  7 6 5 4 5 6 7 8      32     49
a  2a-1..a..2a          8a   (2a-1)^2

Finding which cycle (n) we are in:
 Given index i:N
 Find largest n:N s.t. i >= (2n-1)^2

   i = (2n-1)^2 <=>
   n = (isqrt(i) + 1) idiv 2  * integer square root

Finding steps k:N from center:
 Given cycle n:N, index i:N
 Let d = [ i-(2n-1)^2 ] % 2n
 k = if d < n then 2n-1-d else d+1

-}
daythree i
    | i < 1 = error "no domain"
    | i == 1 = 0
    | otherwise =
        let j = i-1
            n = (isqrt j + 1) `div` 2
            d = (j - (2*n-1)^2) `mod` (2*n)
        in if d < n then 2*n-1-d else d+1

-- Newton's method for isqrt to avoid loss of data to floating point
isqrt n = case n of
    0 -> 0
    1 -> 1
    n -> head $ dropWhile (\x -> x*x > n) $ iterate (\x -> (x + n `div` x) `div` 2) (n `div` 2)