Project Euler #49 Prime permutations

Question

Today I solved problem #49 from project euler .net which reads :

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

We can easily shorten our range from 999-9999 to 999 - 9999 - 2*3330 because if the first number is bigger than that the third one will no longer be 4-digit number. The code breaks the moment it finds the correct result but still.

The way I solved this problem is by separating my work in 3 steps :

1 . Implementing the Sieve of Eratosthenes :

    private static bool[] SetPrimes(int max)
    {
        bool[] localPrimes = new bool[max + 1];
        for (int i = 2; i <= max; i++)
        {
            localPrimes[i] = true;
        }
        for (int i = 2; i <= Math.Sqrt(max); i++)
        {
            if (localPrimes[i])
            {
                for (int j = i * i; j <= max; j += i)
                {
                    localPrimes[j] = false;
                }
            }
        }
        return localPrimes;
    }

Which was pretty easy it is something I have done before and I have experience with. I picked sieve over a function which checks if a number is prime because the time it takes for the sieve to calculate all the numbers from 1-9999 is lesser than the time the function will take.

2 . Implementing a permutation generator

    private static IEnumerable<int?> GetSubset(int number)
    {
        int?[] localSubset = new int?[GetFactiorial(number.ToString().Length)];
        char[] digits = number.ToString().ToCharArray();
        int startingIndex = 0;
        int[] indexesToSwap = new int[digits.Length - 1];
        for (int index = 0; index < indexesToSwap.Length; index++)
        {
            indexesToSwap[index ] = index + 1;
        }
        for (int i = 0; i < localSubset.Length; i += localSubset.Length/digits.Length)
        {
            char[] tmpSubsetDigits = (char[])digits.Clone();
            tmpSubsetDigits[0] = tmpSubsetDigits[startingIndex];
            tmpSubsetDigits[startingIndex] = digits[0];
            localSubset[i] = int.Parse(tmpSubsetDigits.Aggregate(string.Empty, (current, digit) => current + digit));
            int n = 0;
            while (n < localSubset.Length/digits.Length)
            {
                for (int j = 0; j < indexesToSwap.Length - 1; j++)
                {
                    char tmp = tmpSubsetDigits[indexesToSwap[j]];
                    tmpSubsetDigits[indexesToSwap[j]] = tmpSubsetDigits[indexesToSwap[j + 1]];
                    tmpSubsetDigits[indexesToSwap[j + 1]] = tmp;
                    localSubset[i + n + 1] = int.Parse(tmpSubsetDigits.Aggregate(string.Empty, (current, digit) => current + digit));
                    if (localSubset[localSubset.Length - 1] != null)
                    {
                        return localSubset;
                    }
                    n++;
                }
            }
            startingIndex++;
            digits = number.ToString().ToCharArray();
        }
        return localSubset;
    }

    private static int GetFactiorial(int n)
    {
        int fact = 1;
        for (int i = 1; i <= n; i++)
        {
            fact *= i;
        }
        return fact;
    }

This is my first time implementing my own permutation generator and it works fine, for some reason it wont work for 2 digit numbers.

• We know that the permutations of number are equal to the factorial of the number's length we use this to give our array a specified length. Next, since we are going to work with the digits of the number I decided to go with a char array.

• Next up we have another int array which holds all the indexes of our number except for the first one, since my code swaps all the other numbers aside from the first one which I manually change, so we fill the array with those values and we go into the actual permutation generator.

• We have a for loop which increases by localSubset.Length/digits.Length okay let's say we have 123 the permutations starting with the digit 1, are 2 namely - 123 & 132 so if we divide the the total length of the permutations by the length of the number we get exactly how much permutations there are starting with 1. Continuing down in the for loop we are declaring another char array which we use in our operations, just so we don't touch the digits array we Clone it, after we have done that we are swapping the first index of our number with the startingIndex variable this variable is increased once each time we have found all the permutations starting with the same digit,let's say we have then number 123 on the first iteration it will take 1 and replace it with 1 because startingIndex value is 0, after the we have added 123 and 132 to our array variable will increase by 1 and it will replace 1 with 2 and so on.

• Moving on we have a while loop combined with a for loop, the second one usually iterates n/m times lesser than it should where n is the amount of permutations starting with the same digit and m is the amount of indexes to rotate i.e indexesToSwap, when we have 123 it will iterate 0 times lesser so it's redundant in this case but if we have 1234 it will iterate 1 time less because the indexesToSwap are only going to be 3 while we are looking for 6 permutations in total starting with the same digit. Inside we are simply just swapping the indexes of our current subset and after this we add it to our array of permutations, there is some problem there that I couldn't figure out which was causing the program to crash due to IndexOutOfRange exception, if you run the code using breakpoint there you will see that one of the values is duplicate of the first one and it gets overwritten later on i.e 1 extra value which probably caused the bug.

3 . Combine the pieces and make it work !

    private static void Main()
    {
        const int increament = 3330;
        const int maxFirstNumber = 9999 - increament*2;
        string result = string.Empty;
        Stopwatch sw = Stopwatch.StartNew();
        bool[] primes = SetPrimes(9999);
        for (int i = 999; i <= maxFirstNumber; i++)
        {
            if (i == 1487)
            {
                continue;
            }
            int secondNumber = i + increament;
            int thirdNumber = i + increament*2;
            if (primes[i] && primes[secondNumber] && primes[thirdNumber])
            {
                IEnumerable<int?> permuations = GetSubset(i);
                IEnumerable<int?> values = permuations as int?[] ?? permuations.ToArray();
                if (values.Contains(secondNumber) && values.Contains(thirdNumber))
                {
                    result = i.ToString() + secondNumber + thirdNumber;
                    sw.Stop();
                    break;
                }
            }
        }
        Console.WriteLine(result);
        Console.WriteLine($"Time to calculate in milliseconds : {sw.ElapsedMilliseconds}");
        Console.ReadKey();
    }

Answer 1

The permutation generator has the most room for improvement. It's buggy and takes a screen of text to explain. For programming puzzles, I like to implement the solution myself and then search online to see what other people did. For something like getting permutations, there should be a lot of good examples. Unfortunately, most of the C# examples assume you're working with a set or aren't generic. Looking at the answers here can give you a general idea for a solution at least. I decided to create my own solution. It's a recursive method that, for each item in a collection, gets the permutations of the collection without that item and adds that item to the front of each permutation.

private static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> collection)
{
    var asArray = collection.ToArray();
    if (asArray.Count() <= 1)
    {
        return new[] { asArray };
    }
    var result =
        from index in Enumerable.Range(0, asArray.Count())
        from tail in GetPermutations(asArray.Take(index).Concat(asArray.Skip(index + 1)))
        select (new[] { asArray[index] }).Concat(tail);            
    return result;
}

It can than be called to help get the subsets for your specific problem:

private static IEnumerable<int> GetSubset(int number) =>
    GetPermutations(number.ToString()).Select(xs => int.Parse(new string(xs.ToArray()))).Distinct();

I don't understand your current implementation enough to suggest a lot of improvements. Here are a few things. You shouldn't use nullable integers in this case, especially as return values because none of them will be null. For determining when to exit, instead of checking if the last element is not null you can check if the most recently assigned index is the last index in the array. One of the string constructors takes a char array so instead of calling tmpSubsetDigits.Aggregate(string.Empty, (current, digit) => current + digit), which is longer and creates a bunch of unnecessary strings, you can call new string(tmpSubsetDigits).

Answer 2

General style comments:

• In two places you use "local" as part of a variable name. This is not an informative convention.
• In GetSubset you declare all of your variables at the top, like you would in C. So for instance, startingIndex won't be declared until after the first for loop.
• You use Nullable<int> aka int? in a few places where just an int would suffice. I don't see a single place where it's needed.
• This is very non-idiomatic: IEnumerable<int?> values = permuations as int?[] ?? permuations.ToArray(); Just write int?[] values = permuations.ToArray();, or have GetSubset return an array.

Your approach to the permutations part of the problem seems liked you dove into coding it without thinking it through ahead of time. There are no comments and it's not at all clear what your approach is. You should be able to disprove statements like so if we divide the the total length of the permutations by the length of the number we get exactly how much permutations there are starting with 1 with some math (though it happens to be true for n=3). GetSubset is not a descriptive name for a function.

Finally, generating all permutations of a number is not the most efficient way to approach this. There's a much easier way to tell if two numbers have the same digits.