# euler 28 spiral diagonals

Feb 17, 2015

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)

``````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.