Challenge: Number Spiral Diagnols

Posted on: June 14, 2017 12:17:51 AM
Another project euler challenge that states:

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

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

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?

I found this challenge to be very straight forward in how I would solve it. I know that there is an algebraic way to do it, but I didn't want to find/figure that equation out. I found that the top right corner is going to be the square of the size of the square, so 10012. From there, I can use simple subtraction to find the other corners. Then to get the next number to square will be the floor value of the root value of the bottom left corner. From there, it's a simple loop to go through all values.
Program.cs
using System;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_28
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            const int squareSize = 1001;

            Stopwatch sw = Stopwatch.StartNew();

            int half = (int)Math.Ceiling(squareSize / 2D) - 1;
            int[] topRight = new int[half];
            int[] topLeft = new int[half];
            int[] bottomLeft = new int[half];
            int[] bottomRight = new int[half];

            int idx = 0;
            for (int i = squareSize; i > 1;)
            {
                topRight[idx] = i * i;
                topLeft[idx] = topRight[idx] - i + 1;
                bottomLeft[idx] = topLeft[idx] - i + 1;
                bottomRight[idx] = bottomLeft[idx] - i + 1;

                i = (int)Math.Floor(Math.Sqrt(bottomRight[idx]));

                idx++;
            }

            sw.Stop();

            Console.WriteLine($"Sum of diagonols: {topRight.Sum() + topLeft.Sum() + bottomLeft.Sum() + bottomRight.Sum() + 1} in {sw.ElapsedTicks} ticks");
        }
    }
}

Comments


No comments yet, be the first to leave one.

Leave a Comment