solutions.problem44

Complexity

Total Complexity

5

Size/Duplication

Total Lines	68
Duplicated Lines	0 %

Importance

Changes

0

1 Function

Rating	Name	Duplication	Size	Complexity
A	solve()	0	11	5

"""
Project Euler Problem 44: Pentagon Numbers
==========================================

.. module:: solutions.problem44
   :synopsis: My solution to problem #44.

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

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

Pentagonal numbers are generated by the formula, :math:`P_n = \\frac{n(3n-1)}{2}`. The first ten pentagonal numbers are:

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

.. math::

    1, 5, 12, 22, 35, 51, 70, 92, 117, 145, \\dots

It can be seen that :math:`P_4 + P_7 = 22 + 70 = 92 = P_8`. However, their difference, :math:`70 - 22 = 48`, is not

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

pentagonal.

Find the pair of pentagonal numbers, :math:`P_j` and :math:`P_k`, for which their sum and difference are pentagonal and

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

:math:`D = |P_k - Pj|` is minimised; what is the value of :math:`D`?

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

This solution is really a brute-force search with some sensible ordering constraints to remove redundant work that would

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

otherwise occur.

Iterate through a two-dimensional collection of pentagonal numbers, :math:`\\lbrace (p_j, p_k) \\rbrace`, and simply

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

test whether both the numbers :math:`p_j + p_k` and :math:`|p_j - p_k|` are pentagonal.

By iterating over :math:`p_k` first, and in ascending order, and then :math:`p_j` second in descending order from

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

:math:`p_{k-1}` to :math:`p_1` we will guarantee that :math:`p_k \\gt p_j`. Therefore, we will only consider positive

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

values for :math:`p_k + p_j` and :math:`p_k - p_j`.

Further, by initialising :math:`p_j` to a value as close to :math:`p_k` as possible and then increasing the distance

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

between :math:`p_j,p_k` at each iteration, the first candidate :math:`(p_j, p_k)` satisfying the search conditions will

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

have minimal distance :math:`|p_j - p_k|` for the current value of :math:`p_k`.

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

.. literalinclude:: ../../solutions/problem44.py
   :language: python
   :lines: 51-
"""

from lib.sequence import Pentagonals


def solve():
    """ Compute the answer to Project Euler's problem #44 """
    pentagonals = Pentagonals()
    visited_pentagonals = []  # will reverse-iterate over this list {p_j}
    pentagonals_set = set()  # for testing whether sums or differences of pentagonal numbers are pentagonal numbers

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

    for p_k in pentagonals:
        for p_j in reversed(visited_pentagonals):
            if (p_k - p_j) in pentagonals_set and (p_k + p_j) in pentagonals:

There is an unnecessary parenthesis after if.

                return p_k - p_j  # p_k > p_j => |p_k - p_j| = p_k = p_j
        visited_pentagonals.append(p_k)
        pentagonals_set.add(p_k)


expected_answer = 5482660

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