Project-Euler/Problem28.py at master · russellsmith/Project-Euler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
"""
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?
"""

def generate_spiral(dimension):
    spiral = []
    offset = 1
    count = 1
    total = dimension * dimension
    half = dimension/2
    x,y = half, half

    for i in xrange(dimension):
        spiral.append([0]*dimension)


    while True:
        while x < half + offset:
            # Move right up to offset
            spiral[y][x] = count
            x += 1
            count += 1

        if count >= total:
            break

        while y < half + offset:
            # Move down up to offset
            spiral[y][x] = count
            y += 1
            count += 1

        while x > half - offset:
            # Move left up to offset
            spiral[y][x] = count
            x -= 1
            count += 1

        while y > half - offset:
            spiral[y][x] = count
            y -= 1
            count += 1

        offset += 1

    return spiral

def sum_diagonals(matrix):
    dimension = len(matrix)
    sum = 0

    for i in xrange(dimension):
        # find indexes of both elements to pull from the row
        a, b = i , dimension - (i + 1)

        if a != b:
            sum += matrix[i][a] + matrix[i][b]
        else:
            sum += matrix[i][a]

    return sum


if __name__ == "__main__":
    dimension = 1001
    spiral = generate_spiral(dimension)

    sum = sum_diagonals(spiral)

    print('The sum of diagonals of dimension %d is %d'%(dimension, sum))