Problem #49

Yeah, it has been a while since I've updated this blog, I havent been to Project Euler in a while, I've been busy with lots of other stuff, but, to all of my loyal readers (haha!), here's the solution to #49.

This code uses the Sieve of Erathosthenes to generate an array of primes to easy access. It then finds all of the permutations of a found prime number. It generates an adjacency matrix of distances from each prime to another prime, and uses a recursive function to parse through all of the possible paths, finding any path that has the same distances.

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <set>

using namespace std;

bool isPrime (int);
void generatePrimes (bool*, int);

const int SIZE = 10000;
bool primes[SIZE];

struct pos
{
    int x;
    int y;
};
vector<pos> coords;

// ----------------------------------------------------------------------------
// Convert an integer to a vector. 12 becomes 0012
// ----------------------------------------------------------------------------
void numToVector (int num, vector<int> &v)
{
  v.clear ();

  stringstream ss;
  string tmp;

  ss << num;
  tmp = ss.str ();

  for (int i = tmp.size () - 1; i >= 0; i--)
    v.push_back (tmp[i] - '0');

  while (v.size () < 4)
    v.push_back (0);

  reverse (v.begin (), v.end ());

}

// ----------------------------------------------------------------------------
// Convert a vector to an integer.
// ----------------------------------------------------------------------------
int vectorToNum (vector<int> &v)
{
  int num = 0;

  for (int i = v.size () - 1; i >= 0; i--)
    num += v[i] * pow (10.0, (v.size () - 1) - i);

  return num;
}

// ----------------------------------------------------------------------------
// Generate all of the permutations of a prime number, that are also prime, and
// store them in a sorted manner.
// ----------------------------------------------------------------------------
void generatePermutationPrimes (int num, vector<int> &v)
{
  vector<int> tmp;
  numToVector (num, tmp);

  sort (tmp.begin (), tmp.end ());

  do {
    if (isPrime (vectorToNum (tmp)))
      v.push_back (vectorToNum (tmp));
  } while (next_permutation (tmp.begin (), tmp.end ()));

  sort (v.begin (), v.end ());
}

// ----------------------------------------------------------------------------
// This is a recursive function, it tests to see if a specific number (num) is
// in the adjacency matrix (matrix), with a connection to (pos). If it is, it
// increments the counter, and calls it's self to parse that new line with the
// same distance value.
// ----------------------------------------------------------------------------
void findNum (int num, int pos, vector< vector<int> > &matrix, int &counter)
{
  ::pos tmpPos;
  tmpPos.x = pos;
  counter++;
  for (int i = 0; i < matrix[pos].size (); i++)
  {
    if (matrix[pos][i] == num)
    {
      tmpPos.y = i;
      coords.push_back (tmpPos);
      findNum (matrix[pos][i], i, matrix, counter);
    }
  }
}

// ----------------------------------------------------------------------------
// This is the starting point for the recursive function. It does the initial
// loop through all of the rows in the matrix, passing each one to the findNum
// function. It then returns a string with the three numbers in it, or
// a string with "NaN" if no string was found.
// ----------------------------------------------------------------------------
string hasSequence (vector< vector<int> > &matrix, vector<int> &v)
{
  int counter = 0;
  stringstream output ("NaN");

  for (int i = 0; i < matrix.size (); i++)
  {
    for (int j = 0; j < matrix.size (); j++)
    {
      if (matrix[i][j] != 0)
      {
        coords.clear ();
        pos tmpPos;
        tmpPos.x = i;
        tmpPos.y = j;
        coords.push_back (tmpPos);
        counter = 0;
        findNum (matrix[i][j], j, matrix, counter);
        if (counter >= 2)
        {
          if ((v[coords[0].x] > 1000) &&
              (v[coords[0].y] > 1000) &&
              (v[coords[1].y] > 1000))
            output << v[coords[0].x] << " " << v[coords[0].y] << " " << v[coords[1].y];
        }
      }
    }
  }
  return output.str ();
}

// ----------------------------------------------------------------------------
// This creates an adjacency matrix for the number sequence stored in v. It
// then calls hasSequence, and returns the string that hasSequence returns.
// ----------------------------------------------------------------------------
string findSequence (vector<int> &v)
{
  vector< vector<int> > adjMatrix;

  adjMatrix.resize (v.size ());
  for (int i = 0; i < v.size (); i++)
    adjMatrix[i].resize (v.size ());

  for (int i = 0; i < adjMatrix.size (); i++)
    for (int j = 0; j < adjMatrix[i].size (); j++)
      adjMatrix[i][j] = 0;

  for (int i = 0; i < v.size () - 1; i++)
    for (int j = i + 1; j < v.size (); j++)
      adjMatrix[i][j] = abs (v[i] - v[j]);

  string seq = hasSequence (adjMatrix, v);
  return seq;
}

int main ()
{
  generatePrimes (primes, SIZE);

  set<string> results;
  for (int i = 1; i < 10000; i++)
  {
    if (isPrime (i))
    {
      vector<int> v;
      generatePermutationPrimes (i, v);

      if (v.size () >= 3)
      {
        string incSeq = findSequence (v);
        if (incSeq != "NaN")
            results.insert (incSeq);
      }
    }
  }

  cout << "Matches: " << endl;
  for (set<string>::iterator it = results.begin (); it != results.end (); it++)
    cout << (*it) << endl;

  return 0;
}

// ----------------------------------------------------------------------------
// Check to see if a number is a prime number
// ----------------------------------------------------------------------------
bool isPrime (int num)
{
  assert (num >= 0);

  if (num >= SIZE)
  {
    if (num == 2)
      return true;
    if (num <= 2 || num % 2 == 0)
      return false;
    for (int i = 3; i < num / 2; i += 2)
      if (num % i == 0)
        return false;
    return true;
  }

  return primes[num];
}

// ----------------------------------------------------------------------------
// Generate a list of all of the primes numbers up to a specific limit.
// ----------------------------------------------------------------------------
void generatePrimes (bool *primes, int size)
{
  int pos = 2;

  primes[0] = false;
  primes[1] = false;

  for (int i = 2; i < size; i++)
    primes[i] = true;

  while (pos < size)
  {
    for (int i = 2; i * pos < size; i++)
      primes[i * pos] = false;
    pos++;
    while (primes[pos] == false && pos < size)
      pos++;
  }
}