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 |
||
0 ignored issues
–
show
|
|||
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? |
||
0 ignored issues
–
show
|
|||
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 |
||
0 ignored issues
–
show
|
|||
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 |
||
0 ignored issues
–
show
|
|||
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, |
||
0 ignored issues
–
show
The name
x does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
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 |
||
0 ignored issues
–
show
|
|||
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): |
||
0 ignored issues
–
show
|
|||
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 |
||
0 ignored issues
–
show
The name
x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
96 | |||
97 | # Iteratively fill in matrix values in a clockwise direction |
||
98 | counter = 1 |
||
99 | distance = 1 |
||
100 | for i in range(dimension // 2): |
||
0 ignored issues
–
show
|
|||
101 | x, y, counter = complete_line_segment(matrix, x, y, counter, "R", distance) |
||
0 ignored issues
–
show
The name
x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
102 | x, y, counter = complete_line_segment(matrix, x, y, counter, "D", distance) |
||
0 ignored issues
–
show
The name
x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
103 | distance += 1 |
||
104 | x, y, counter = complete_line_segment(matrix, x, y, counter, "L", distance) |
||
0 ignored issues
–
show
The name
x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
105 | x, y, counter = complete_line_segment(matrix, x, y, counter, "U", distance) |
||
0 ignored issues
–
show
The name
x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() The name
y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
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): |
||
0 ignored issues
–
show
The name
z does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
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 |
||
0 ignored issues
–
show
The name
expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$ ).
This check looks for invalid names for a range of different identifiers. You can set regular expressions to which the identifiers must conform if the defaults do not match your requirements. If your project includes a Pylint configuration file, the settings contained in that file take precedence. To find out more about Pylint, please refer to their site. ![]() |
|||
122 |
This check looks for lines that are too long. You can specify the maximum line length.