nekedome / project-euler

solutions/problem37.py

"""
Project Euler Problem 37: Truncatable Primes
============================================

.. module:: solutions.problem37
   :synopsis: My solution to problem #37.

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

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

The number :math:`3797` has an interesting property. Being prime itself, it is possible to continuously remove digits

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

from left to right, and remain prime at each stage: :math:`3797, 797, 97`, and :math:`7`. Similarly we can work from

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

right to left: :math:`3797, 379, 37`, and :math:`3`.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

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

.. note:: :math:`2, 3, 5`, and :math:`7` are not considered to be truncatable primes.

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

Enumerate the prime numbers in ascending order, testing each in term for the truncatable property. For each truncatable

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

prime, accumulate their sum until eleven have been accounted for.

.. note:: due to the implementation of :func:`lib.sequence.Primes`, an upper-bound must be provided. This meant trial

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

          and error was required to identify an appropriate bound before the code below was correct.

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

.. literalinclude:: ../../solutions/problem37.py
   :language: python
   :lines: 39-
"""

from typing import Set

from lib.digital import num_digits
from lib.sequence import Primes


def is_truncatable_prime(value: int, primes: Set[int]) -> bool:
    """ Test whether `value` is both left to right and right to left truncatable or not

    :param value: the integer to test
    :param primes: a set of primes containing at least those in the range :math:`[2, value]`
    :return: whether `value` is truncatable or not
    """

    # Check for right to left truncatable
    temp = value
    while temp >= 10:
        temp //= 10
        if temp not in primes:
            return False

    # Check for left to right truncatable
    while num_digits(value) > 1:
        value %= 10 ** (num_digits(value) - 1)
        if value not in primes:
            return False

    return True


def solve():
    """ Compute the answer to Project Euler's problem #37 """
    upper_bound = 740000  # found by trial and error
    primes = set(Primes(upper_bound=upper_bound))
    multidigit_primes = filter(lambda p: p >= 10, primes)
    truncatable_primes = filter(lambda p: is_truncatable_prime(p, primes), multidigit_primes)
    answer = sum(truncatable_primes)
    return answer


expected_answer = 748317

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