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?
let rec sumDiagonals n m total max = match n with | 1 -> sumDiagonals (n+1) m 1 1 | _ when n > m -> total | _ when n % 2 = 0 -> sumDiagonals (n+1) m total max | _ -> let newValues = [1..4] |> List.map (fun x -> max + x * (n-1)) let newMax = newValues |> List.max let newTotal = total + (newValues |> List.sum) sumDiagonals (n+1) m newTotal newMax let answer = sumDiagonals 1 1001 0 0
As you’ve probably noticed already, there’s a pattern in the sequence 1, 3, 5, 7, 9, 13, 17, 21, 25, … generated by the spiral in the problem brief. As the dimension goes up by 2 at a time, all odd numbers, 4 new numbers are added to the sequence:
|Dimension (d)||Numbers on the edge of the square||Max number from last dimension|
|3||3, 5, 7, 9||1|
|5||13, 17, 21, 25||9|
Looking at the above table, it quickly becomes clear that the new numbers that are added to the diagonals when you expand the dimension by 2 can be calculated as:
max number from last dimension + (d-1) * i (where i is a number from 1 to 4)
My solution simply wraps this logic in a recursive function whilst keeping a running total of all the numbers that have been generated.
I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.
Here is a complete list of all my posts on serverless and AWS Lambda. In the meantime, here are a few of my most popular blog posts.
- Lambda optimization tip – enable HTTP keep-alive
- You are thinking about serverless costs all wrong
- Many faced threats to Serverless security
- We can do better than percentile latencies
- I’m afraid you’re thinking about AWS Lambda cold starts all wrong
- Yubl’s road to Serverless
- AWS Lambda – should you have few monolithic functions or many single-purposed functions?
- AWS Lambda – compare coldstart time with different languages, memory and code sizes
- Guys, we’re doing pagination wrong