The Problem

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

The Solution

Full disclosure: when I originally solved this, I went about it all wrong. I was too focused on getting the answer and not focused enough on analyzing the problem.

My original solution had a complicated function that determined which way to move next based on current direction and position. It was a match statement with 9 different conditions. I was just learning to use F#'s active patterns and every solution looked like it needed active patterns to me. Here's what I came up with:

let size = 1001

type Direction = Up|Down|Left|Right

let getNextDirection (grid : int[,]) x y direction =
    match direction,x,y with
    | Left,x,_ when x = 0 -> Down
    | Left,x,y when grid.[x-1,y] <> 0 -> Down
    | Down,_,y when y = (size - 1) -> Right
    | Down,x,y when grid.[x,y+1] <> 0 -> Right
    | Right,x,_ when x = (size - 1) -> Up
    | Right,x,y when grid.[x+1,y] <> 0 -> Up
    | Up,_,y when y = 0 -> Left
    | Up,x,y when grid.[x,y-1] <> 0 -> Left
    | _ -> direction

I used the function above in a loop to "draw" the spiral and sum elements on the diagonals.

This is exactly the wrong approach. Here's a much better solution.

Each internal "ring" of the spiral forms a square with a side length of n. t is the total of the numbers in the previous ring. The numbers on the diagonals can all be expressed in terms of n and t. For example, when n is 3 and t is 1, then the 4 diagonals are:

• t+(n-1)*1 = 1+(3-1)*1 = 3
• t+(n-1)*2 = 1+(3-1)*2 = 5
• t+(n-1)*3 = 1+(3-1)*3 = 7
• t+(n-1)*4 = 1+(3-1)*4 = 9

The side length goes up by 2 each time. For the next side length, 5, we get:

• t+(n-1)*1 = 9+(5-1)*1 = 13
• t+(n-1)*2 = 9+(5-1)*2 = 17
• t+(n-1)*3 = 9+(5-1)*3 = 21
• t+(n-1)*4 = 9+(5-1)*4 = 25

The diagonals are all we care about, so we can ignore all the other numbers.

Knowing that, we'll first write a function to return the 4 diagonals for a given total and sideLength:

let diagonals total sideLength =
    let inc = sideLength - 1
    let dv n = total + inc * n
    [| 1..4 |] |> Array.map dv

Next, we construct a loop to keep calling diagonals and incrementing the sideLength until we get our answer.

let rec loop total sideLength diagonalSum =
    let newLength = sideLength + 2
    let diags = diagonals total newLength
    let newSum = diagonalSum + Array.sum diags
    if newLength = 1001 then
        newSum
    else
        loop diags.[3] newLength newSum

loop 1 1 1

The diagonals function returns the 4 diagonals for a given side length. The loop function figures out the next side length, gets its diagonals, and adds them to the sum. If we've hit a ring of side length 1001, it returns the total, otherwise it repeats the process.

Other Posts in This Series