ProjectEulerPython/Problems/Problem37.py

#ProjectEuler/ProjectEulerPython/Problems/Problem37.py
#Matthew Ellison
# Created: 07-01-21
#Modified: 07-01-21
#Find the sum of the only eleven primes that are both truncatable from left to right and right to left (2, 3, 5, and 7 are not counted).
#Unless otherwise listed, all of my non-standard imports can be gotten from my pyClasses repository at https://bitbucket.org/Mattrixwv/pyClasses
"""
	Copyright (C) 2021  Matthew Ellison

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU Lesser General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU Lesser General Public License for more details.

	You should have received a copy of the GNU Lesser General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
"""


from Problems.Problem import Problem
import NumberAlgorithms


class Problem37(Problem):
	#Variables
	__last_prime_before_check = 7	#The last prime before 11 since single digit primes aren't checked

	#Functions
	#Constructor
	def __init__(self) -> None:
		super().__init__("Find the sum of the only eleven primes that are both truncatable from left to right and right to left (2, 3, 5, and 7 are not counted).")
		self.truncPrimes = []	#All numbers that are truncatable primes
		self.sumOfTruncPrimes = 0	#The sum of all elements in truncPrimes

	#Operational functions
	#Solve the problem
	def solve(self) -> None:
		#If the problem has already been solved do nothing and end the function
		if(self.solved):
			return

		#Start the timer
		self.timer.start()


		#Create the sieve and get the first prime number
		sieve = NumberAlgorithms.primeGenerator()
		currentPrime = next(sieve)
		#Loop through the sieve until you get to __last_prime_before_check
		while(currentPrime < self.__last_prime_before_check):
			currentPrime = next(sieve)
		#Loop until truncPrimes contains 11 elements
		while(len(self.truncPrimes) < 11):
			isTruncPrime = True
			#Get the next prime
			currentPrime = next(sieve)
			#Convert the prime to a string
			primeString = str(currentPrime)
			#If the string contains an even digit move to the next prime
			for strLoc in range(0, len(primeString)):
				#Allow 2 to be the first digit
				if((strLoc == 0) and (primeString[strLoc] == '2')):
					continue
				if((primeString[strLoc] == '0') or (primeString[strLoc] == '2') or (primeString[strLoc] == '4') or (primeString[strLoc] == '6') or (primeString[strLoc] == '8')):
					isTruncPrime = False
					break
			#Start removing digits from the left and see if the number stays prime
			if(isTruncPrime):
				for truncLoc in range(1, len(primeString)):
					#Create a substring of the prime, removing the needed digits from the left
					primeSubstring = primeString[truncLoc::]
					#Convert the string to an int and see if the number is still prime
					newPrime = int(primeSubstring)
					if(not NumberAlgorithms.isPrime(newPrime)):
						isTruncPrime = False
						break
			#Start removing digits from the right and see if the number stays prime
			if(isTruncPrime):
				for truncLoc in range(1, len(primeString)):
					#Create a substring of the prime, removing the needed digits from the right
					primeSubstring = primeString[0:len(primeString) - truncLoc]
					#Convert the string to an int and see if the number is still prime
					newPrime = int(primeSubstring)
					if(not NumberAlgorithms.isPrime(newPrime)):
						isTruncPrime = False
						break
			#If the number remained prime through all operations add it to the vector
			if(isTruncPrime):
				self.truncPrimes.append(currentPrime)
			#End the loop if we have collected enough primes
			if(len(self.truncPrimes) == 11):
				break
		#Get the sum of all elements in the truncPrimes vector
		self.sumOfTruncPrimes = sum(self.truncPrimes)


		#Stop the timer
		self.timer.stop()

		#Throw a flag to show the problem is solved
		self.solved = True

	#Reset the problem so it can be run again
	def reset(self) -> None:
		super().reset()
		self.truncPrimes = []
		self.sumOfTruncPrimes = 0

	#Gets
	#Returns a string with the solution to the problem
	def getResult(self) -> str:
		self.solvedCheck("result")
		return f"The sum of all left and right truncatable primes is {self.sumOfTruncPrimes}"
	#Returns the list of primes that can be truncated
	def getTruncatablePrimes(self) -> list:
		self.solvedCheck("list of truncatable primes")
		return self.truncPrimes
	#Returns the sum of all elements in truncPrimes
	def getSumOfPrimes(self) -> int:
		self.solvedCheck("sum of truncatable primes")
		return self.sumOfTruncPrimes


""" Results:
The sum of all left and right truncatable primes is 748317
It took an average of 224.657 milliseconds to run this problem through 100 iterations
"""