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