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.