Monday, July 27, 2009

Grind Report 28

Problem 28

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 both diagonals is 101.

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


*WARNING: This contains the solution!*

This is by far my most compact solution so far and like any compact algorithm, there was a decent amount of thought that went into it. So here is my attempt to explain everything...

One of the first things I did was write out the corners by themselves as well as expand the grid to be 9x9 so I could get a better view of what exactly was going on. After drawing them out and staring at them I saw that the way to get the corners is to just add multiples of two to the previous number...


3 5 7 9 13 17 21 25... //corner value
2 2 2 2 4 4 4 4 6 6 6 6 8 8 8 8 //amount to add to the previous corner

That's not exactly a beautiful example but I think it will suffice. With just this it would be very easy to write a program to do this; however, I took it a step further. Instead of considering each corner, I figured why not just consider the average of the corners and multiply that by 4. It makes sense if you think about it, but it actually turns out that the average of the corners is all of the numbers directly to the left of 1 (and including 1). In the example you can see 3 averages: 1, 6, 19. As I just said, to get the answer we just need to sum of the averages and multiply by 4.

One way to get to each average is to follow the bottom left diagonal and move n numbers up, where n is the number of spirals moved over from the center. And now the question shifts to how to find the corners in the bottom left diagonal. Using the previously gathered information I derived that at any given spiral n the value of the bottom left corner is

n
* 4 + ((8 * (n - 1) * n) / 2) + 1

n * 2 * 2 //is that for the given spiral we need to find the 2nd corner
((8 * (n - 1) * n) / 2) //this sums up all of the previous corners
1 //because we start with the center 1

This is a little complex and I could go into it more but I doubt it is of that much interest. Here is my code solution.

#include <iostream>

using std::cout;

const int SPIRALSIZE = 1001;

int main()
{
long long average = 1;
for (int i = 1; i * 2 + 1 >= 1001; ++i)
average += (i * 4 + ((8 * (i - 1) * i) / 2) + i + 1);
cout << average * 4;
}

*saved game*

No comments:

Post a Comment