Issues (956)

solutions/problem28.py (2 issues)

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):
0 ignored issues
show
The variable i seems to be unused.
Loading history...
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):
0 ignored issues
show
The variable i seems to be unused.
Loading history...
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