Project Euler: Problem 28 – Number spiral diagonals

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 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?

Idea:

Given the performance limits (or in this case, lack thereof) of modern computers, I figured it would be trivial for a modern computer to make a two-dimensional array of 1001×1001. I decided it would be easiest to just recreate the spiral and add the diagonals.

long answer = -1;

int[][] spiral = new int[1001][1001];
int number = spiral.length*spiral.length;

for(int level = 0; level < = spiral.length/2; level++) {
    //top row : reverse
    for(int i = spiral.length-level-1; i >= level; i--) {
        spiral[level][i] = number;
        number--;
    }
    //left column: down
    for(int i = level+1; i < spiral.length-level; i++) {
        spiral[i][level] = number;
        number--;
    }
    //bottom row: forward
    for(int i = level+1; i < spiral.length-level; i++) {
        spiral[spiral.length-1-level][i] = number;
        number--;
    }
    //right column: up
    for(int i = spiral.length-1-level-1; i > level; i--) {
        spiral[i][spiral.length-1-level] = number;
        number--;
    }
}
//sum the diagonals (leave answer starting at -1, adding 1 twice)
for(int i = 0; i < spiral.length; i++) {
    answer += spiral[i][i];
    answer += spiral[spiral.length-1-i][i];
}

System.out.println("Answer: "+answer);
Bookmark the permalink.

One Comment

  1. Pingback: Project Euler: Problem 58 – Spiral primes | Pursuit of Intellectual Curiosity

Leave a Reply

Your email address will not be published. Required fields are marked *