|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 28: Number Spiral Diagonals |
|
3
|
|
|
================================================= |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem28 |
|
6
|
|
|
:synopsis: My solution to problem #28. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem28.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
Starting with the number :math:`1` and moving to the right in a clockwise direction a :math:`5` by :math:`5` spiral is |
|
|
|
|
|
|
15
|
|
|
formed as follows: |
|
16
|
|
|
|
|
17
|
|
|
.. math:: |
|
18
|
|
|
|
|
19
|
|
|
&\\color{red}{21}, 2&2, 2&3, 2&4, &\\color{red}{25} \\\\ |
|
20
|
|
|
&20, &\\color{red}{7}, &8, &\\color{red}{9}, &10 \\\\ |
|
21
|
|
|
&19, &6, &\\color{red}{1}, &2, &11 \\\\ |
|
22
|
|
|
&18, &\\color{red}{5}, &4, &\\color{red}{3}, &12 \\\\ |
|
23
|
|
|
&\\color{red}{17}, 1&6, 1&5, 1&4, &\\color{red}{13} |
|
24
|
|
|
|
|
25
|
|
|
It can be verified that the sum of the numbers on the diagonals is :math:`101`. |
|
26
|
|
|
|
|
27
|
|
|
What is the sum of the numbers on the diagonals in a :math:`1001` by :math:`1001` spiral formed in the same way? |
|
|
|
|
|
|
28
|
|
|
|
|
29
|
|
|
Solution Discussion |
|
30
|
|
|
################### |
|
31
|
|
|
|
|
32
|
|
|
The example :math:`5 \\times 5` matrix reveals a general algorithm to complete an :math:`n \\times n` square matrix with |
|
|
|
|
|
|
33
|
|
|
the clockwise spiral pattern where :math:`n` is an odd integer. |
|
34
|
|
|
|
|
35
|
|
|
This solution creates the matrix by storing the value of an incrementing counter in the clockwise spiral pattern. The |
|
|
|
|
|
|
36
|
|
|
two diagonals are then summed to produce the final answer. |
|
37
|
|
|
|
|
38
|
|
|
1. Mark the centre with :math:`1` |
|
39
|
|
|
2. Set a `counter` to :math:`1` and `distance` to :math:`1` |
|
40
|
|
|
3. Repeat the following :math:`^n / _2` times: |
|
41
|
|
|
a. Mark the cells using the `counter`, moving right `distance` cells |
|
42
|
|
|
b. Mark the cells using the `counter`, moving down `distance` cells |
|
43
|
|
|
c. Increment `distance` |
|
44
|
|
|
d. Mark the cells using the `counter`, moving left `distance` cells |
|
45
|
|
|
e. Mark the cells using the `counter`, moving up `distance` cells |
|
46
|
|
|
f. Increment `distance` |
|
47
|
|
|
4. Mark the cells using the `counter`, moving right `distance` cells |
|
48
|
|
|
|
|
49
|
|
|
Solution Implementation |
|
50
|
|
|
####################### |
|
51
|
|
|
|
|
52
|
|
|
.. literalinclude:: ../../solutions/problem28.py |
|
53
|
|
|
:language: python |
|
54
|
|
|
:lines: 57- |
|
55
|
|
|
""" |
|
56
|
|
|
|
|
57
|
|
|
from typing import List, Optional, Tuple |
|
58
|
|
|
|
|
59
|
|
|
from lib.numbertheory import is_odd |
|
60
|
|
|
|
|
61
|
|
|
|
|
62
|
|
|
def complete_line_segment(matrix: List[List[Optional[int]]], x: int, y: int, counter: int, direction: str, |
|
|
|
|
|
|
63
|
|
|
distance: int) -> Tuple[int, int, int]: |
|
64
|
|
|
""" Fill in adjacent cells in `matrix`, starting at position :math:`(x,y)`, moving in the specified `direction` for |
|
|
|
|
|
|
65
|
|
|
the specified `distance` |
|
66
|
|
|
|
|
67
|
|
|
.. note:: the initial value of `counter` is used to start, it is incremented at each step. |
|
68
|
|
|
|
|
69
|
|
|
:param matrix: the grid to be populated with `counter` in a spiral pattern |
|
70
|
|
|
:param x: the starting :math:`x` co-ordinate |
|
71
|
|
|
:param y: the staring :math:`y` co-ordinate |
|
72
|
|
|
:param counter: the current value of the counter to use when setting cell values |
|
73
|
|
|
:param direction: the direction to move in (``"R"``, ``"D"``, ``"L"`` or ``"U"``) |
|
74
|
|
|
:param distance: the distance to move in the given direction |
|
75
|
|
|
:return: the new :math:`(x,y)` position and the final value of `counter` |
|
76
|
|
|
""" |
|
77
|
|
|
|
|
78
|
|
|
step_coords = {"R": lambda _x, _y: (_x + 1, _y), "D": lambda _x, _y: (_x, _y + 1), |
|
79
|
|
|
"L": lambda _x, _y: (_x - 1, _y), "U": lambda _x, _y: (_x, _y - 1)} |
|
80
|
|
|
for i in range(distance): |
|
|
|
|
|
|
81
|
|
|
matrix[y][x] = counter # mark the (x,y) cell in matrix with counter |
|
82
|
|
|
x, y = step_coords[direction](x, y) # advance (x,y) co-ordinates in the specified direction |
|
83
|
|
|
counter += 1 # get next counter value |
|
84
|
|
|
return x, y, counter |
|
85
|
|
|
|
|
86
|
|
|
|
|
87
|
|
|
def solve(): |
|
88
|
|
|
""" Compute the answer to Project Euler's problem #28 """ |
|
89
|
|
|
|
|
90
|
|
|
dimension = 1001 |
|
91
|
|
|
assert is_odd(dimension), "this algorithm is only correct for an odd-valued dimension" |
|
92
|
|
|
|
|
93
|
|
|
# Initialise the matrix with None values everywhere, start a position (x,y) at the centre |
|
94
|
|
|
matrix = [[None for _ in range(dimension)] for _ in range(dimension)] |
|
95
|
|
|
x, y = dimension // 2, dimension // 2 |
|
|
|
|
|
|
96
|
|
|
|
|
97
|
|
|
# Iteratively fill in matrix values in a clockwise direction |
|
98
|
|
|
counter = 1 |
|
99
|
|
|
distance = 1 |
|
100
|
|
|
for i in range(dimension // 2): |
|
|
|
|
|
|
101
|
|
|
x, y, counter = complete_line_segment(matrix, x, y, counter, "R", distance) |
|
|
|
|
|
|
102
|
|
|
x, y, counter = complete_line_segment(matrix, x, y, counter, "D", distance) |
|
|
|
|
|
|
103
|
|
|
distance += 1 |
|
104
|
|
|
x, y, counter = complete_line_segment(matrix, x, y, counter, "L", distance) |
|
|
|
|
|
|
105
|
|
|
x, y, counter = complete_line_segment(matrix, x, y, counter, "U", distance) |
|
|
|
|
|
|
106
|
|
|
distance += 1 |
|
107
|
|
|
|
|
108
|
|
|
# Complete the top row of the matrix |
|
109
|
|
|
complete_line_segment(matrix, x, y, counter, "R", distance) |
|
110
|
|
|
|
|
111
|
|
|
# Sum the values along both diagonals |
|
112
|
|
|
answer = 0 |
|
113
|
|
|
for z in range(dimension): |
|
|
|
|
|
|
114
|
|
|
answer += matrix[z][z] # top left to bottom right |
|
115
|
|
|
answer += matrix[dimension - 1 - z][z] # bottom left to top right |
|
116
|
|
|
answer -= 1 # we double-counted the centre cell which has a value of 1, remove one copy |
|
117
|
|
|
|
|
118
|
|
|
return answer |
|
119
|
|
|
|
|
120
|
|
|
|
|
121
|
|
|
expected_answer = 669171001 |
|
|
|
|
|
|
122
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.