This problem afforded a chance to be lazy and have fun.

There definitely is a pattern in the diagonals here: for a `3 x 3`

matrix, the elements are 3, 5, 7, 9. For a `5 x 5`

matrix, the additional elements are 13, 17, 21, 25.

You can see these as being (1 + 2), (1 + 4), (1 + 6), (1 + 8), and then (1 + 2 + 2 + 8), (1 + 4 + 4 + 8), (1 + 6 + 6 + 8), (1 + 8 + 8 + 8).

Similarly, for a `7 x 7`

matrix, the numbers are 31, 37, 43, 49, which are (1 + 2 + 2 + 2 + 8 + 8 + 8), (1 + 4 + 4 + 4 + 8 + 8 + 8), (1 + 6 + 6 + 6 + 8 + 8 + 8), (1 + 8 + 8 + 8 + 8 + 8 + 8)

On the other hand, the problem mentions a `1001 x 1001`

matrix, which is *tiny*, so why bother with these patterns? Just create the matrix and sum up the diagonals directly! (It’s *just* a million elements … now if it was a few orders of magnitude higher, it would be a different story)

**Statutory Warning**: Spoilers ahead!

```
import qualified Data.List as L
import qualified Data.Vector as V
import qualified Data.Matrix as M
import qualified Data.HashMap.Strict as H
import Prelude hiding (Left,Right)
-- Euler 28: spiral int matrix
data Direction = Down | Left | Right | Up deriving Show
move :: (Int,Int) -> Direction -> (Int,Int)
move oldPoint@(y,x) dir =
case dir of Down -> (y+1,x)
Left -> (y,x-1)
Right -> (y,x+1)
Up -> (y-1,x)
getSpiralMoves :: Int -> [Direction]
getSpiralMoves n =
if n == 3
then [Down, Right, Up, Up, Left, Left, Down, Down]
else let prevMoves = getSpiralMoves (n-2)
firstMove = [Down]
secondMove = take (n-2) $ repeat Right
thirdMove = take (n-1) $ repeat Up
fourthMove = take (n-1) $ repeat Left
fifthMove = take (n-1) $ repeat Down
in
prevMoves ++ firstMove ++ secondMove ++ thirdMove ++ fourthMove ++ fifthMove
getSpiralCoords :: Int -> [(Int,Int)]
getSpiralCoords n =
let mid = div (n+1) 2
start = (mid,mid)
in
L.scanl move start $ getSpiralMoves n
getCoordHash :: Int -> H.HashMap (Int,Int) Int
getCoordHash n = H.fromList $ zip (getSpiralCoords n) [1..]
genF :: H.HashMap (Int,Int) Int -> (Int, Int) -> Int
genF h (i,j) = h H.! (i,j)
getDiagElems :: M.Matrix Int -> Int -> Int
getDiagElems mat n =
let leftDiag = sum $ [M.getElem i i mat | i <- [1 .. n]]
rightDiag = sum $ [M.getElem i (n + 1 - i) mat | i <- [1 .. n]]
centerElem = let c = div (n+1) 2
in
M.getElem c c mat
in
leftDiag + rightDiag - centerElem
getSpiralMatrix :: Int -> M.Matrix Int
getSpiralMatrix n = M.matrix n n $ genF $ getCoordHash n
diagSum :: Int -> Int
diagSum n = getDiagElems (getSpiralMatrix n) n
```

I added type signatures for every function, so here’s a quick overview (this is terribly over-engineered, and turned out to be more of a way to get to know various Haskell datatypes than to actually solve this problem!):

`getSpiralMoves`

translates the literal pattern of the square spiral into concrete steps and then `getSpiralCoords`

converts these into `(i,j)`

elements within the matrix. Since I use a *generating function* (in `getSpiralMatrix`

) to create the matrix, I use a hash-map to store the value of each co-ordinate … and then `getDiagElems`

iterates over the diagonal elements.

The matrix does turn out as expected:

```
*Main> getSpiralMatrix 7
( 43 42 41 40 39 38 37 )
( 44 21 20 19 18 17 36 )
( 45 22 7 6 5 16 35 )
( 46 23 8 1 4 15 34 )
( 47 24 9 2 3 14 33 )
( 48 25 10 11 12 13 32 )
( 49 26 27 28 29 30 31 )
```

This was a simple problem but I was surprised by how *short* the code was; I didn’t write overly terse code, added lots of whitespace, indentation, extra lines, etc, and the whole piece was *still* just 60 lines!

**Update**: Fine, here’s the simple solution too.

For every `N x N`

matrix (where `N`

is odd), the diagonal elements are all the diagonal elements of the `N-2`

-sized matrix, plus four more. And these four include `N^2`

and three others, each being `(N-1)`

less than the other. The base case is `1 x 1`

, with a value of 1.

```
euler28 :: Int -> Int
euler28 1 = 1
euler28 n = let sideDiff = n - 1
sq = n ^ 2
in
euler28 (n-2) + 4 * sq - (1 + 2 + 3) * sideDiff
```

… and then `euler28 1001`

gives the same answer.