# The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits
# from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right
# to left: 3797, 379, 37, and 3.
#
# Find the sum of the only eleven primes that are both truncatable from left to right and right to left.
#
# NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

from Problem import Problem
from sortedcontainers import SortedList
from Utilities import Primes

primes = SortedList(Primes.primes_up_to_n(2000000))  # 2 million primes should be a good start


class TruncatablePrimes(Problem):
    def __init__(self):
        self.answer = 748317

    def do(self):
        trunc = []

        for prime in primes:
            if self.truncatable(prime):
                trunc.append(prime)
        return sum(trunc)

    def truncatable(self, x):
        if len(str(x)) < 2:
            return False

        for i in range(len(str(x))):
            if i+1 > 0:
                if not primes.__contains__(int(str(x)[:i+1])):
                    return False
            if i < len(str(x)) - 1:
                if not primes.__contains__(int(str(x)[i+1:])):
                    return False
        return True

print(TruncatablePrimes().do())
