solutions.problem28

Complexity

Total Complexity

12

Size/Duplication

Total Lines	122
Duplicated Lines	0 %

Importance

Changes

0

2 Functions

Rating	Name	Duplication	Size	Complexity
B	complete_line_segment()	0	23	6
B	solve()	0	32	6

"""
Project Euler Problem 28: Number Spiral Diagonals
=================================================

.. module:: solutions.problem28
   :synopsis: My solution to problem #28.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem28.py>`_.

Problem Statement
#################

Starting with the number :math:`1` and moving to the right in a clockwise direction a :math:`5` by :math:`5` spiral is

This line is too long as per the coding-style (118/100).

formed as follows:

.. math::

    &\\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}

It can be verified that the sum of the numbers on the diagonals is :math:`101`.

What is the sum of the numbers on the diagonals in a :math:`1001` by :math:`1001` spiral formed in the same way?

This line is too long as per the coding-style (112/100).

Solution Discussion
###################

The example :math:`5 \\times 5` matrix reveals a general algorithm to complete an :math:`n \\times n` square matrix with

This line is too long as per the coding-style (120/100).

the clockwise spiral pattern where :math:`n` is an odd integer.

This solution creates the matrix by storing the value of an incrementing counter in the clockwise spiral pattern. The

This line is too long as per the coding-style (117/100).

two diagonals are then summed to produce the final answer.

1. Mark the centre with :math:`1`
2. Set a `counter` to :math:`1` and `distance` to :math:`1`
3. Repeat the following :math:`^n / _2` times:
    a. Mark the cells using the `counter`, moving right `distance` cells
    b. Mark the cells using the `counter`, moving down `distance` cells
    c. Increment `distance`
    d. Mark the cells using the `counter`, moving left `distance` cells
    e. Mark the cells using the `counter`, moving up `distance` cells
    f. Increment `distance`
4. Mark the cells using the `counter`, moving right `distance` cells

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem28.py
   :language: python
   :lines: 57-
"""

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,

This line is too long as per the coding-style (106/100).

The name x does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

Too many arguments (6/5)

                          distance: int) -> Tuple[int, int, int]:
    """ Fill in adjacent cells in `matrix`, starting at position :math:`(x,y)`, moving in the specified `direction` for

This line is too long as per the coding-style (119/100).

    the specified `distance`

    .. note:: the initial value of `counter` is used to start, it is incremented at each step.

    :param matrix: the two-dimensional 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):

The variable i seems to be unused.

        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

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    # Iteratively fill in matrix values in a clockwise direction
    counter = 1
    distance = 1
    for i in range(dimension // 2):

The variable i seems to be unused.

        x, y, counter = complete_line_segment(matrix, x, y, counter, "R", distance)

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        x, y, counter = complete_line_segment(matrix, x, y, counter, "D", distance)

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        distance += 1
        x, y, counter = complete_line_segment(matrix, x, y, counter, "L", distance)

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        x, y, counter = complete_line_segment(matrix, x, y, counter, "U", distance)

The name x does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name y does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        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):

The name z does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        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

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).