Necklace counting problem-with consecutive prime constraint

Question

This is codeEval challenge to count the number of chains possible to make with beads holding numbers. Constraint is sum of the consecutive beads of chain should be a prime number.

The standard algorithm std::next_permutation is very resource oriented in this case, so dropped the idea to use that one.

I created a simple algorithm. If the input number is 4, we have to consider numbers 1-4. If we take permutations of 2-4 and append 1 to all resultant permutations we will get all possible necklaces without repetition using numbers 1-4. The above stated is the basic approach.

By considering, beads should be placed in chain to satisfy the prime number constraints at least, they should be in even number after odd number order or vice versa. Since I am always starting with 1, I have chosen the odd number before even number order.

My solution is not yet accepted because of performance constraints in that it should output answers for 5 input even numbers within 10 seconds. On my Intel dual core system by using O3 compiler optimization, it is taking 35 seconds and without optimization in range of 180-200 seconds for the number 18. For all other numbers up to 16 it will execute before 10 seconds.

I created an array of possible eligible digits to get position in the chain.

int prime_vec[10][8]={ {},
                           { 2, 4, 6, 10, 12, 16, 18, 0 },     //1//
                           { 2, 4, 8, 10, 14, 16, 0, 0  },        //3//
                           { 2, 6, 8, 12, 14, 18, 0, 0  },       //5//
                           { 4, 6, 10, 12, 16, 0, 0, 0  },         //7
                           { 2, 4, 8, 10,  14, 0, 0, 0  },          //9
                           { 2, 6, 8, 12,  18, 0, 0, 0 },          //11
                           { 4, 6, 10, 16, 18, 0, 0, 0 },         //13
                           { 2, 4, 8, 14,  16, 0, 0, 0 },          //15
                           { 2, 6, 12, 14,  0, 0, 0, 0 } };          //17

If the last digit in so far calculated permutation set is 1 , the first index of of the prime_vec for further iteration is 1.

int candidate = prime_vec[ index ][ i++ ];

index will get value 1 and iterate over that specific dimension to consider all eligible values to accommodate the next probable position in permutation.

This is the Pseudo code for this solution:

1. Read the even number N from input file
2. if it is less than 2 or greater than 18, return 0
3. Create a std::vector> Vec to keep all possible permutations satisfying condition sum of consecutive elements should be prime.
4. create a std::vector temp and insert 1
5. In step 4 since we inserted with 1, an odd number, consider all even numbers <= N and append with temp. 2,4,6,10,12,16,18 are all candidates. So if N==18, we will get {1,2}, {1,4}, {1,6}, {1,10}, {1,12}, {1,16},{1,18}. {1,8} is not a valid pair since sum of digits is 9 and not a prime. On top of that we have to make sure the new digit that we are going to add in vector should not be present in that vector before we are adding. So keep all eligible pair of digits as vectors inside vec
6. Iterate over each vector from vec. And consider the digit from 2nd position of vector. For example consider {1,2}. So 2 is the 2nd position digit, so eligible digits to place in 3rd position are {3,5,9,11,15,17}. So we will get{1,2,3}, {1,2,5}, {1,2,9}, {1,2,11}, {1,2,15} and {1,2,17}. Digits 7 and 13 are not eligible , since addition with 2 for them will not generate prime numbers. On top of that we have to make sure the new digit that we are going to add in vector should not be present in that vector before we are adding.
7. Repeat the steps 5 and 6 in order for all vectors from vector vec until we place the digits in all N positions.
8. Take the size of vector vec

Is there any way to improve its performance? Please let me know if I need to clarify any details more.

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<chrono>


//if Yes return true;
//if No return false;
inline bool const find_in_vec( std::vector<int> vec, const int x )
{
    std::sort( vec.begin(), vec.end() );
    return std::binary_search( vec.begin(), vec.end(), x );
}

std::vector<std::vector<int>> insertOddNumber( std::vector<std::vector<int>> &vec,
                     const int num, const int pos )
{
    int prime_vec[ 10 ][ 8 ] ={ {},
                           { 3, 5, 9, 11, 15, 17, 0, 0 },        //2//
                           { 3, 7, 9, 13, 15, 0, 0, 0  },          //4//
                           { 5, 7, 11,13, 17, 0, 0, 0  },        //6//
                           { 3, 5, 9, 11, 15, 0, 0, 0  },         //8
                           { 3, 7, 9, 13, 0, 0, 0,  0  },            //10
                           { 5, 7, 11,17, 0, 0, 0,  0  },               //12
                           { 3, 5, 9, 15, 17, 0, 0, 0  },         //14
                           { 3, 7, 13,15, 0, 0, 0, 0  },          //16
                           { 5, 11,13, 0, 0, 0, 0, 0 } };            //18

    std::vector<std::vector<int>> eVecTemp;
    for(auto &x: vec)
    {
        int index = x.at( pos-1 ) * 0.5;
        int i = 0;
        while( index )
        {
            int candidate = prime_vec[ index ][ i++ ];

            if( ( candidate == 0 ) || ( candidate   > num ))
            {
                break;
            }

            if( !find_in_vec( x, candidate ) )
            {
                 eVecTemp.emplace_back( x );
                 eVecTemp.back().push_back( candidate );
            }
        }

    }
    return eVecTemp;
}

int updateLastdigit( std::vector<std::vector<int>>& vec, const int num )
{
    int prime[11]  = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
    for( auto &x: vec )
    {
        int sum= x.at( num-1 ) +1;

        if( !std::binary_search( prime, prime+11, sum ) )
        {
            x.clear();
        }

    }
    return std::count_if( vec.begin(), vec.end(), [](std::vector<int> & x){ return !( x.empty() );} );
}

std::vector<std::vector<int>> insertEvenNumber(std::vector<std::vector<int>>& vec,
                      const int num, const int pos)
{

    int prime_vec[10][8]={ {},
                           { 2, 4, 6, 10, 12, 16, 18, 0 },     //1//
                           { 2, 4, 8, 10, 14, 16, 0, 0  },        //3//
                           { 2, 6, 8, 12, 14, 18, 0, 0  },       //5//
                           { 4, 6, 10, 12, 16, 0, 0, 0  },         //7
                           { 2, 4, 8, 10,  14, 0, 0, 0  },          //9
                           { 2, 6, 8, 12,  18, 0, 0, 0 },          //11
                           { 4, 6, 10, 16, 18, 0, 0, 0 },         //13
                           { 2, 4, 8, 14,  16, 0, 0, 0 },          //15
                           { 2, 6, 12, 14,  0, 0, 0, 0 } };          //17

    std::vector<std::vector<int>> eVecTemp;
    for( auto &x: vec )
    {
        int index = ( x.at( pos-1 ) * 0.5 ) + 1;
        int i = 0;

        while( index )
        {
            int candidate = prime_vec[ index ][ i++ ];

            if( ( candidate == 0 ) || ( candidate  > num ) )
            {
                break;
            }

            if( !find_in_vec( x, candidate ) )
            {
                eVecTemp.emplace_back( x );
                eVecTemp.back().push_back( candidate );
            }
        }

    }
    return eVecTemp;
}

inline void insert_first( std::vector<std::vector<int>>& vec, const int num )
{
    std::vector<int> temp;
    temp.emplace_back( 1 );
    vec.emplace_back( temp );
}

int create_consecutive_primes( const int num )
{
    std::vector< std::vector<int>> vec;
    if( num >= 2 )
    {
        insert_first( vec, num );
        vec = insertEvenNumber( vec, num, 1 );
        if( num == 2 )
        {
              return updateLastdigit( vec, num );
        }
    }
    if( num >= 4 )
    {
         vec = insertOddNumber( vec, num, 2 );
         vec = insertEvenNumber( vec, num, 3 );
         if( num == 4 )
         {
              return updateLastdigit( vec, num );
         }
    }
    if( num >= 6 )
    {
         vec = insertOddNumber( vec, num, 4 );
         vec = insertEvenNumber( vec, num, 5 );
         if( num == 6)
         {
              return updateLastdigit( vec, num );
         }
     }
     if( num >= 8 )
     {
         vec = insertOddNumber( vec, num, 6 );
         vec=insertEvenNumber( vec, num, 7 );
         if( num == 8)
         {
              return updateLastdigit( vec, num );
         }
     }
     if( num >= 10 )
     {
         vec=insertOddNumber( vec, num, 8 );
         vec=insertEvenNumber( vec, num, 9 );
         if( num == 10 )
         {
              return updateLastdigit( vec, num );
         }
     }
     int count = 0;
     for( auto & x: vec)
     {
          std::vector< std::vector<int>> vec1;
          vec1.emplace_back( x );
          for( int i = 10; i < num; ++i )
          {
              vec1=insertOddNumber( vec1, num, i );
              if( !vec1.empty() )
                  vec1 = insertEvenNumber( vec1, num, ++i );
          }

          count += updateLastdigit( vec1, num );
      }
      return count;
}

void readInputFile( std::string filename )
{
    std::ifstream infile( filename );
    std::string record;

    while( std::getline( infile, record ) )
    {

        const int num = atoi( record.c_str() );
        if( num < 2 || num > 18 || (num %2 != 0 ))
        {
            std::cout<< 0 <<"\n";
            continue;
        }
        std::cout << create_consecutive_primes( num ) << "\n";
    }
    infile.close();
}

int main( int argc, char* argv[] )
{
    auto start = std::chrono::steady_clock::now();
    if( argc < 2 )
    {
        std::cout << "usage is filesize filename" << "\n";
        exit( 0 );
    }
    std::ios_base::sync_with_stdio( false );
    readInputFile( argv[ 1 ] );

    auto end = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds> ( end - start );
    std::cout << duration.count() << "\n";    
}

Answer 1

You can improve the performance by using a more efficient algorithm.

Instead of generating all possible combinations, one can count them using dynamic programming.

The state is (mask, last_number), where mask indicates which numbers were already used. A transition is adding a number cur such that it is not in the mask and last_number + cur is a prime. The answer is sum of f(2^n - 1, x) such that x + 1 is prime. Here is a pseudo code of this solution:

def solve(n)
    isPrime = new Array[n + 1, n + 1]
    for i = 1 .. n
        for j = 1 .. n
            isPrime[i][j] = checkIfPrime(i + j) // checks if a number is prime somehow(for instance, by trial division)
    dp = new Array(2^n, n + 1)
    dp(1, 1) = 1 // There is one way to put number one.
    for mask = 0 .. (2^n - 1)
        for last = 1 .. n
            for cur = 1 .. n
                if isPrime[last][cur] && last in mask && not cur in mask
                     dp[mask with cur][cur] += dp[mask][last]
    return sum dp[2^n - 1][x] for all x such that 1 + x is prime

We can check that a number is in a mask using bitwise operations(and we add a new number to a mask in the same way), so the total time complexity is O(2^n * n^2).

It is also possible to improve the constant factor by checking only even cur when last is odd (and vice versa) or by precomputing the list of all cur such that cur + last is a prime before running the dynamic programming.