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:

$\begin{split}&\color{red}{21}, 2&2, 2&3, 2&4, &\color{red}{25} \\ &20, &\color{red}{7}, &8, &\color{red}{9}, &10 \\ &19, &6, &\color{red}{1}, &2, &11 \\ &18, &\color{red}{5}, &4, &\color{red}{3}, &12 \\ &\color{red}{17}, 1&6, 1&5, 1&4, &\color{red}{13}\end{split}$

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.

1. Mark the centre with $$1$$
2. Set a counter to $$1$$ and distance to $$1$$
3. Repeat the following $$^n / _2$$ times:
1. Mark the cells using the counter, moving right distance cells
2. Mark the cells using the counter, moving down distance cells
3. Increment distance
4. Mark the cells using the counter, moving left distance cells
5. Mark the cells using the counter, moving up distance cells
6. Increment distance
4. 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 co-ordinate
:param y: the staring :math:y co-ordinate
: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) co-ordinates 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 odd-valued 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
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 double-counted the centre cell which has a value of 1, remove one copy


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
Parameters: matrix (List[List[Optional[int]]]) – the grid to be populated with counter in a spiral pattern x (int) – the starting $$x$$ co-ordinate y (int) – the staring $$y$$ co-ordinate 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 Tuple[int, int, int] the new $$(x,y)$$ position and the final value of counter
solutions.problem28.solve()