1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

I've got the following approach:

  1. Store in an array all primes we will use:

    int[] primes = { 2, 3, 5, 7, 11, 13, 17 };
    
  2. Create the GetDivisibles method to generate a sequence of 3-digit numbers (possible with leading zero(s)), which are divisible by a given prime number:

    private static IEnumerable<int> GetDivisibles(int divider)
    {
        for (int i = divider; i <= 999; i += divider)
            yield return i;
    }
    
  3. Create a method to join two sequences of divisibles: n-digit (a) and 3-digit (b) to a new sequence of n+1-digit numbers where the last 2 digits of each number from the first sequence (a) equal to the first 2 digits of a number from b.

    private static IEnumerable<int> JoinDivisibles(IEnumerable<int> a, IEnumerable<int> b)
    {
        var bArray = b.ToArray();
        return from aItem in a
               let aTail = aItem % 100
               from bItem in bArray
               where bItem / 10 == aTail
               select aItem * 10 + (bItem % 10);
    }
    
  4. Now we need a method to test a number if it is pandigital (based on the Eric Lippert's comment):

    private static bool IsPandigital(long number)
    {
        const int TotalDigits = 10;
        const int AllBits = (1 << TotalDigits) - 1;
    
        int digitBits = 0;
        while (number != 0)
        {
            int digit = (int)(number % 10);
            int mask = 1 << digit;
            if ((digitBits & mask) != 0)
                return false;
            digitBits |= mask;
            number /= 10;
        }
        return digitBits == AllBits;
    }
    
  5. Run it, iterating through all divisibles found and all first digits of 10-digit number:

    int[] primes = { 2, 3, 5, 7, 11, 13, 17 };
    
    var divisibles = GetDivisibles(2);
    for (int i = 1; i < primes.Length; i++)
    {
        divisibles = JoinDivisibles(divisibles, GetDivisibles(primes[i]));
    }
    
    long sum = 0;
    foreach (int divisible in divisibles)
    {
        for (long i = 1; i <= 9; i++)
        {
            long number = i * 1000000000 + divisible;
            if (IsPandigital(number))
                sum += number;
        }
    }
    Console.WriteLine(sum);
    
\$\endgroup\$
  • \$\begingroup\$ Great answer 96 ms ! One improvement would be enumerating to array from bItem in b the b here is being enumerated multiple times doing this var enumerable = b as int[] ?? b.ToArray(); will prevent it, anyway thank you for the good suggestions on a lot of my questions ! \$\endgroup\$ – Denis Apr 14 '16 at 11:27
  • \$\begingroup\$ @denis Thank you for pointing me to the multiple times enumeration issue. I've updated the answer. \$\endgroup\$ – Dmitry Apr 14 '16 at 11:35
2
\$\begingroup\$

The right way to find out where you're spending time is to use a profiler; I encourage you to do so.

That said, I can glance at your program and see numerous places where more work is being done than necessary.

Let's start with your generation of all the permutations. You generate all the permutations eagerly; you allocate arrays for all 360000+ permutations and stick them in a list. That's a huge amount of memory for something that you only need to access one at at time because you're using LINQ.

Rather than producing all permutations at once, you can produce them one at a time, as needed. I give several algorithms to do so here:

https://ericlippert.com/2013/04/15/producing-permutations-part-one/

You have a call to OrderBy, the result of which is ignored. I don't know why you have this in here. It's not expensive, but it's also unnecessary.

This

select permutation.Aggregate(string.Empty, (current, t) => current + char.GetNumericValue(t))
        into number

is an incredibly expensive way to say let number = new string(permutation). It allocates some ten times more memory than is needed.

where number[0] != '0'

The where clause can be moved up to be

where permutation[0] != '0'

and now you are not even constructing the string if you don't need to.

You call long.Parse twice every time through. The result didn't change, but you compute it all over again.

Look at the interaction between the query and the filter. You make a char array into a string, then make that into a number, then pass it to the filter method, what is the first thing it does?

private static bool IsDivisibleByPrimes(long inputPandigital)
{
    char[] digits = inputPandigital.ToString().ToCharArray();

Let's sum up. You have an array of chars, so you turn it into a string, then turn it into a long, then turn it back into a string, then decompose it into a char array THIS IS INSANITY.

Get this whole query re-organized:

from permutation in permutations
where permutation[0] != '0' 
where IsDivisibleByPrimes(permutation)
select long.Parse(new string(permutation))

Make IsDivisibleByPrimes take a char array if that's what it needs.

Wow, is that ever easier to read, and probably a lot faster.

You make that mistake again here:

if (int.Parse(temp)%i != 0)

You're calling int.Parse every time through the loop, despite the fact that temp hasn't changed.

But why call it at all? You have the chars, just add them up:

int number = 0;
...
  for (int i = end; i >= start; i--)
    number = 10 * number + digits[i] - '0';

If the digits are 1 2 3 then we start with 0, multiply it by 10, get 0, add 1. Then multiply that by 10, add 2, we've got 12. Multiply by 10, add 3, we've got 123, done.

Summing up: think hard about the flow of data through your program. Where do things need to be arrays? Where do they need to be strings? Where do they need to be numbers? Don't just convert one to the other willy-nilly. These conversions are not cheap, so get the data flow right so that conversions are done as little as possible. Also think hard about how many times you recompute something, and whether you are computing something eagerly that could be computed lazily.

\$\endgroup\$
  • \$\begingroup\$ Oh and one more thing the loop for (int i = end; i >= start; i--) will obviously not work like this .. \$\endgroup\$ – Denis Apr 13 '16 at 20:48
  • \$\begingroup\$ @denis: Why will it not work? \$\endgroup\$ – Eric Lippert Apr 13 '16 at 21:02
  • \$\begingroup\$ With the current set up using this for wont generate correct digits to compare..resulting in wrong answer maybe some edits will fix it but right now its not working properly \$\endgroup\$ – Denis Apr 14 '16 at 10:45
2
\$\begingroup\$

Alternative Solution

This will be a bit confusing, so my apologies in advance.

Bottom-Up Search

When I did this problem, rather than brute force looping over all the possible permutations, I constructed my pandigital numbers from the bottom up. We can do this because each 3-digit sub group is highly constrained. For example, the last 3 digits have to be a multiple of 17 and be less than 987. There are only 58 different multiples, and any with duplicate digits, like 119, are ineligible. Let's say that about 40 are valid. that means the next 3 digits (d6d7d8) must contain the first 2 digits of one of those 40 AND also not contain any duplicate digits.

The constraints mean that trying to construct the number from the bottom up is a very, very small search space, and thus very quick to search.

Possible Implementation/Algorithm

Here is a high level breakdown of my implementation:

  • For each prime, I generated all the multiples from Prime p to 999 (so 2: 2,4,6,8,..,998, 17: 17,34,51,..,986). I'll refer to each of these multiples as a "sub".
  • Each list subs was then filtered such that I only kept the values with unique digits (so 2: ...,240,242,244,246,248,... became 2: 240,246,248,...)
  • For each sub [d1d2d3] I break it into [d1d2], the head, and [d2d3], the tail.
  • Using a tree structure, I match the tails in the tree to my new sub heads
  • After looping through all the subs, any branch that is 6 long (one for each prime) is a solution.

I know this is a bit confusing, and I can edit this answer with additional comments or code as requested. When I implemented this in in ruby, this bottom-up approach ran in 6ms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.