Python Implementation of Problem 28

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 28

1 ends at 1^2 2-9 ends at 3^2 10-25 ends at 5^2 26-49 ends at 7^2

perimeter[0] = (1, ) perimeter[i] = ((2 * i - 1)^2, (2 * i + 1)^2]

i = 1
2 3 4 5 6 7 8 9
  ^   ^   ^   ^
2i - 1, 2 * 2i - 1, 3 * 2i - 1, 4 * 2i - 1

i = 2
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
      ^           ^           ^           ^
2i - 1, 2 * 2i - 1, 3 * 2i - 1, 4 * 2i - 1

i = 3
26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
                ^                 ^                 ^                 ^

the corners are: perimeter[i][x * 2i - 1 for x in (1, 2, 3, 4)]

Revision 1:

Extracted the code that finds the corners

Problem:

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?

python.src.p0028.square_corner_sum(i: int) → int

Given the index of some spiral, return the sum of its corners

python.src.p0028.spiral_diagonal_sum(size: int) → int
python.src.p0028.main() → int
 1"""
 2Project Euler Problem 28
 3
 41       ends at 1^2
 52-9     ends at 3^2
 610-25   ends at 5^2
 726-49   ends at 7^2
 8
 9perimeter[0] = (1, )
10perimeter[i] = ((2 * i - 1)^2, (2 * i + 1)^2]
11
12.. code-block::
13
14    i = 1
15    2 3 4 5 6 7 8 9
16      ^   ^   ^   ^
17    2i - 1, 2 * 2i - 1, 3 * 2i - 1, 4 * 2i - 1
18
19    i = 2
20    10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
21          ^           ^           ^           ^
22    2i - 1, 2 * 2i - 1, 3 * 2i - 1, 4 * 2i - 1
23
24    i = 3
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
26                    ^                 ^                 ^                 ^
27
28the corners are:
29perimeter[i][x * 2i - 1 for x in (1, 2, 3, 4)]
30
31Revision 1:
32
33Extracted the code that finds the corners
34
35Problem:
36
37Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
38
3921 22 23 24 25
4020  7  8  9 10
4119  6  1  2 11
4218  5  4  3 12
4317 16 15 14 13
44
45It can be verified that the sum of the numbers on the diagonals is 101.
46
47What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?
48"""
49from .lib.iters import spiral_corners
50
51
52def square_corner_sum(i: int) -> int:
53    """Given the index of some spiral, return the sum of its corners"""
54    if i == 0:
55        return 1
56    return sum(spiral_corners(i))
57
58
59def spiral_diagonal_sum(size: int) -> int:
60    n_size = (size + 1) // 2  # change from square length to number of spirals
61    return sum(square_corner_sum(x) for x in range(n_size))
62
63
64def main() -> int:
65    return spiral_diagonal_sum(1001)

Tags: grid-pattern