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
    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 double-counted 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\) 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
Return type:

Tuple[int, int, int]
Returns:

the new \((x,y)\) position and the final value of counter
solutions.problem28.solve()

Compute the answer to Project Euler’s problem #28