I'm having trouble optimizing the Project Euler problem #43 :
The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.
Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:
d2d3d4=406 is divisible by 2
d3d4d5=063 is divisible by 3
d4d5d6=635 is divisible by 5
d5d6d7=357 is divisible by 7
d6d7d8=572 is divisible by 11
d7d8d9=728 is divisible by 13
d8d9d10=289 is divisible by 17
Find the sum of all 0 to 9 pandigital numbers with this property.
Here's a link for the challenge since the d's don't look well here : https://projecteuler.net/problem=43
Now what we need to do here is first get all the pandigital numbers from 1234567890 up to 9876543210. After thinking for a while I realised I don't need a loop that will iterate through them all but instead they just simple permutations of the numbers from 0 to 9.. so I made the following set of method's for calculating all possible permutations :
private static void Swap(ref char a, ref char b)
{
if (a == b) return;
a ^= b;
b ^= a;
a ^= b;
}
public static void GetPer(char[] list)
{
int x = list.Length - 1;
GetPer(list, 0, x);
}
private static void GetPer(char[] list, int k, int m)
{
if (k == m)
{
permutations.Add((char[])(list.Clone()));
}
else
for (int i = k; i <= m; i++)
{
Swap(ref list[k], ref list[i]);
GetPer(list, k + 1, m);
Swap(ref list[k], ref list[i]);
}
}
and we add them to the list of permutations which is declared like this :
private static readonly List<char[]> permutations = new List<char[]>();
We store them all there now that we have this the interesting property they are speaking of in the challenge is that all the concatenated substringed values are divisible by the primes from 2 to 17. So here we have a few options.. since they will always be only 2-17 we can just add them into a int array and use them from there however I wanted to be able to use the false/true property in my checks/if statements I went for a simple sieve of Eratosthenes, it doesn't take that much time anyway.
private static readonly bool[] Primes = SetPrimes(17);
private static bool[] SetPrimes(long max)
{
bool[] localPrimes = new bool[max + 1];
for (long i = 2; i <= max; i++)
{
localPrimes[i] = true;
}
for (long i = 2; i <= Math.Sqrt(max); i++)
{
if (localPrimes[i])
{
for (long j = i * i; j <= max; j += i)
{
localPrimes[j] = false;
}
}
}
return localPrimes;
}
Once we have this we need a method that will check if this property is fulfilled by the current pandigital number so I implemented the following method :
private static bool IsDivisibleByPrimes(long inputPandigital)
{
char[] digits = inputPandigital.ToString().ToCharArray();
int start = 1;
int end = 3;
string temp = string.Empty;
int lastPrime = 2;
while (end < 10)
{
for (int i = start; i <= end; i++)
{
temp += char.GetNumericValue(digits[i]);
}
for (int i = lastPrime; i < Primes.Length; i++)
{
lastPrime++;
if (Primes[i])
{
if (int.Parse(temp)%i != 0)
{
return false;
}
break;
}
}
start++;
end++;
temp = string.Empty;
}
return true;
}
Which takes the current number as input convert's it to a char array check's if the concatenated substringed values are equal to the primes and return's the respective value.
Now we have all that we need we simply need to iterate through the permutations array and check which value's meet's our condition :
private static void Main()
{
string str = "0123456789";
char[] arr = str.ToCharArray();
Stopwatch sw = Stopwatch.StartNew();
GetPer(arr);
var order = permutations.OrderBy(e => e[0]);
long sum = (from permutation in permutations
select permutation.Aggregate(string.Empty, (current, t) => current + char.GetNumericValue(t))
into number
where number[0] != '0'
where IsDivisibleByPrimes(long.Parse(number))
select long.Parse(number)).Sum();
sw.Stop();
Console.WriteLine(sum);
Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
Console.ReadKey();
}
First we get all the permutations by using the previous method GetPer. Than we have this long LINQ expression which basically iterates through all the permutations, creates an empty string and add's all the values from the permutation char array but it also takes the NumericValue of it so we don't get 49 instead of 1 etc.. than it checks if the first index of that string is zero if so we skip this number it wont fit in our condition anyway, however if it's different we check if IsDivisibleByPrimes and if so we add it to the sum.
It gives the correct result but it takes about ~14500 ms which doesn't satisfy me.
