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?
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
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
t is the
total of the numbers in the previous ring. The numbers on the diagonals can all be
expressed in terms of
t. For example, when
n is 3 and
t is 1, then the
4 diagonals are:
The side length goes up by 2 each time. For the next side length, 5, we get:
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
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
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. newLength newSum loop 1 1 1
diagonals function returns the 4 diagonals for a given side length. The
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.