function [] = Problem37()
%ProjectEuler/ProjectEulerOctave/Problem37.m
%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).
%{
	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/>.
%}

%Setup the variables
truncPrimes = [];	%All numbers that are truncatable primes
sumOfTrunc = 0;		%The sum of all elements in truncPrimes

%Start the timer
startTime = clock();

%Get all the primes up to a max number
primeList = primes(750000);
%primeList = primes(30);
for loc = 5 : size(primeList)(2)
	currentPrime = primeList(loc);
	isTruncPrime = true;
	%Convert the prime to a string
	primeString = num2str(currentPrime);
	%If the string contains an even digit move to the next prime
	strLoc = 1;
	while((strLoc <= size(primeString)(2)) && (isTruncPrime))
		ch = primeString(strLoc);
		%Allow 2 to be the first digit
		if((strLoc == 1) && (ch == '2'))
			strLoc = strLoc;
		else
			if((ch == '0') || (ch == '2') || (ch == '4') || (ch == '6') || (ch == '8'))
				isTruncPrime = false;
			end
		end
		++strLoc;
	end
	%Start removing digits from the left and see if the number stays prime
	if(isTruncPrime)
		for truncLoc = 2 : size(primeString)(2)
			%Create a substring of the prime, removing the needed digits frome the left
			primeSubstring = substr(primeString, truncLoc);
			%Convert the string to an int and see if the number is still prime
			newPrime = str2num(primeSubstring);
			if(~isprime(newPrime))
				isTruncPrime = false;
				break;
			end
		end
	end
	%Start removing digits from the right and see if the number stays prime
	if(isTruncPrime)
		for truncLoc = 1 : size(primeString)(2) - 1
			%Create a substring of the prime, removing the needed digits from the right
			primeSubstring = substr(primeString, 1, size(primeString)(2) - truncLoc);
			%Convert the string to an int and see if the number is still a prime
			newPrime = str2num(primeSubstring);
			if(~isprime(newPrime))
				isTruncPrime = false;
				break;
			end
		end
	end
	%If the number remained prime through all operations add it to the table
	if(isTruncPrime)
		truncPrimes(end + 1) = currentPrime;
	end
	%End the loop if we have collected enough primes
	if(size(truncPrimes)(2) == 11)
		break;
	end
end
%Get the sum of all elements in the truncPrimes vector
sumOfTrunc = sum(truncPrimes);

%Stop the timer
endTime = clock();

%print the results
printf("The sum of all left and right truncatable primes is %d\n", sumOfTrunc);
printf("It took %f seconds to run this algorithm\n", etime(endTime, startTime))

end

%{
The sum of all left and right truncatable primes is 748317
It took 38.635521 seconds to run this algorithm
%}