Project Euler Problem 28: Number Spiral Diagonals¶
The source code for this problem can be found here.
Problem Statement¶
Starting with the number \(1\) and moving to the right in a clockwise direction a \(5\) by \(5\) spiral is formed as follows:
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?
Solution Discussion¶
The example \(5 \times 5\) matrix reveals a general algorithm to complete an \(n \times n\) square matrix with the clockwise spiral pattern where \(n\) is an odd integer.
This solution creates the matrix by storing the value of an incrementing counter in the clockwise spiral pattern. The two diagonals are then summed to produce the final answer.
 Mark the centre with \(1\)
 Set a counter to \(1\) and distance to \(1\)
 Repeat the following \(^n / _2\) times:
 Mark the cells using the counter, moving right distance cells
 Mark the cells using the counter, moving down distance cells
 Increment distance
 Mark the cells using the counter, moving left distance cells
 Mark the cells using the counter, moving up distance cells
 Increment distance
 Mark the cells using the counter, moving right distance cells
Solution Implementation¶
from typing import List, Optional, Tuple
from lib.numbertheory import is_odd
def complete_line_segment(matrix: List[List[Optional[int]]], x: int, y: int, counter: int, direction: str,
distance: int) > Tuple[int, int, int]:
""" Fill in adjacent cells in `matrix`, starting at position :math:`(x,y)`, moving in the specified `direction` for
the specified `distance`
.. note:: the initial value of `counter` is used to start, it is incremented at each step.
:param matrix: the grid to be populated with `counter` in a spiral pattern
:param x: the starting :math:`x` coordinate
:param y: the staring :math:`y` coordinate
:param counter: the current value of the counter to use when setting cell values
:param direction: the direction to move in (``"R"``, ``"D"``, ``"L"`` or ``"U"``)
:param distance: the distance to move in the given direction
:return: the new :math:`(x,y)` position and the final value of `counter`
"""
step_coords = {"R": lambda _x, _y: (_x + 1, _y), "D": lambda _x, _y: (_x, _y + 1),
"L": lambda _x, _y: (_x  1, _y), "U": lambda _x, _y: (_x, _y  1)}
for i in range(distance):
matrix[y][x] = counter # mark the (x,y) cell in matrix with counter
x, y = step_coords[direction](x, y) # advance (x,y) coordinates in the specified direction
counter += 1 # get next counter value
return x, y, counter
def solve():
""" Compute the answer to Project Euler's problem #28 """
dimension = 1001
assert is_odd(dimension), "this algorithm is only correct for an oddvalued dimension"
# Initialise the matrix with None values everywhere, start a position (x,y) at the centre
matrix = [[None for _ in range(dimension)] for _ in range(dimension)]
x, y = dimension // 2, dimension // 2
# Iteratively fill in matrix values in a clockwise direction
counter = 1
distance = 1
for i in range(dimension // 2):
x, y, counter = complete_line_segment(matrix, x, y, counter, "R", distance)
x, y, counter = complete_line_segment(matrix, x, y, counter, "D", distance)
distance += 1
x, y, counter = complete_line_segment(matrix, x, y, counter, "L", distance)
x, y, counter = complete_line_segment(matrix, x, y, counter, "U", distance)
distance += 1
# Complete the top row of the matrix
complete_line_segment(matrix, x, y, counter, "R", distance)
# Sum the values along both diagonals
answer = 0
for z in range(dimension):
answer += matrix[z][z] # top left to bottom right
answer += matrix[dimension  1  z][z] # bottom left to top right
answer = 1 # we doublecounted the centre cell which has a value of 1, remove one copy
return answer
expected_answer = 669171001

solutions.problem28.
complete_line_segment
(matrix, x, y, counter, direction, distance)¶ Fill in adjacent cells in matrix, starting at position \((x,y)\), moving in the specified direction for the specified distance
Note
the initial value of counter is used to start, it is incremented at each step.
Parameters:  matrix (
List
[List
[Optional
[int
]]]) – the grid to be populated with counter in a spiral pattern  x (
int
) – the starting \(x\) coordinate  y (
int
) – the staring \(y\) coordinate  counter (
int
) – the current value of the counter to use when setting cell values  direction (
str
) – the direction to move in ("R"
,"D"
,"L"
or"U"
)  distance (
int
) – the distance to move in the given direction
Return type: Tuple
[int
,int
,int
]Returns: the new \((x,y)\) position and the final value of counter
 matrix (

solutions.problem28.
solve
()¶ Compute the answer to Project Euler’s problem #28