3
\$\begingroup\$

I have implemented a solution to Project Euler problem #60. In summary, the problem asks to find the smallest sum of a set of five prime numbers such that the decimal strings of any two numbers in the set concatenated together form the decimal string of a prime.

I'd like some comments on the structure and style of my program and advice on improving its performance. I'm pretty new to OOP style, so advice on how I can use OO patterns to make the code better is desired too.

The basic idea of my solution is that the set of primes with this relation can be represented as an undirected graph. A "prime pair set" is a clique within this graph (A clique is a fully connected subgraph). I determine if a node is part of a clique recursively each time I add one to the graph.

Here is the pseudocode for my algorithm:

for prime p in primes:
  n(p) is a node in graph g
  for node n in graph g:
    if n and p form a pair:
      add an edge to graph g between n and n(p)
  if n(p) is part of a clique of size 5:
    return sum of clique   

function find clique (graph g, target size):
  for node n in g:
    if number of neighbors of n >= target size - 1:
      find clique (neighbors of n, target size - 1)

where neighbors of n itself forms a graph. With each iteration, the graph gets smaller.

Let's start with my Node implementation. I restrict myself to using the stl and not boost for Project Euler because I think I learn more that way. It's probably necessary to include this for you to understand the rest of the program. I would like some advice on how to improve it in case I use it again.

#ifndef _NODE_H
#define _NODE_H

#include <set>

template<typename T>
class Node {
public:
  T data;
  std::set<Node<T>*> edges;

  // constructor
  Node(T);

  // destructor
  ~Node();

  void add_edge(Node<T>*);
  void remove_edge(Node<T>*);
};

template<typename T>
Node<T>::Node(T t) {
  data = t;
}

template<typename T>
Node<T>::~Node() {
  // erase all references to Node
  for (auto edge : edges) {
    edge->edges.erase(edge->edges.find(this));
  }
}

template<typename T>
void Node<T>::add_edge(Node<T>* edge) {
  edges.insert(edge);
  edge->edges.insert(this);
}

template<typename T>
void Node<T>::remove_edge(Node<T>* edge)  {
  edges.erase(edges.find(edge));
  edge->edges.erase(edge->edges.find(this));
}

#endif /*_NODE_H*/

Does it make sense to use std::set here instead of std::vector?

The next part is the functions that I use to generate primes (trial division), and check if two primes form a pair. I test primality of concatenated strings with a Miller-Rabin test that I won't show.

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

#include "miller_rabin.h"
#include "node.h"

const int SET_SIZE = 5; // size of the prime pair set to return

std::vector<int> primes({2, 3});

int next_prime() {
  for (int n = primes.back() + 2; ; n += 2) {
    for (auto p : primes) {
      if (n % p == 0) break;
      if (p*p > n) {
        primes.push_back(n);
        return n;
      }
    }
  }
}

bool are_pair(int a, int b) {
  std::string as = std::to_string(a);
  std::string bs = std::to_string(b);
  return miller_rabin(stoi(as + bs)) && miller_rabin(stoi(bs + as));
}

The next bit is the most important, with my find_clique function and main.

int graph_sum(std::set<Node<int>*> &graph) {
  int sum = 0;
  for (auto node : graph) {
    sum += node->data;
  }
  return sum;
}

// find a clique in a graph recursively
std::set<Node<int>*> find_clique(std::set<Node<int>*> &graph,
                                 size_t size) {
  if (graph.size() < size) { // failed to find clique
    return std::set<Node<int>*>();
  } 
  if (graph.size() == 1) {   // graph is a clique
    return graph;
  }

  for (auto node = graph.begin(); node != std::prev(graph.end(), size); 
       ++node) {
    std::set<Node<int>*> mutual;
    std::set_intersection(
        (*node)->edges.begin(), (*node)->edges.end(),
        graph.begin(), graph.end(),
        std::inserter(mutual, mutual.begin()));
    if (mutual.size() < size - 1) continue;
    std::set<Node<int>*> clique = find_clique(mutual, size - 1);
    if (clique.size() > 0) {  // a clique has been found
      clique.insert(*node);
      return clique;
    }
  }

  return std::set<Node<int>*>();
}

int main() {

  // initialize prime pair graph
  std::vector<Node<int>*> graph({new Node<int>(primes.back())});

  while (true) {
    Node<int>* node = new Node<int>(next_prime());
    // build set of edges for new node
    for (auto n : graph) {
      if (are_pair(node->data, n->data)) {
        node->add_edge(n);
      }
    }

    // 
    if (node->edges.size() >= SET_SIZE - 1) {
      std::set<Node<int>*> neighborhood;
      std::copy(node->edges.begin(), node->edges.end(),
                std::inserter(neighborhood, neighborhood.begin()));
      neighborhood.insert(node);
      std::set<Node<int>*> clique = find_clique(neighborhood, 
                                                SET_SIZE - 1);
      if (clique.size() >= SET_SIZE) {
        for (auto n : clique) {
          std::cout << n->data << ", ";
        } std::cout << std::endl;
        std::cout << "sum: " << graph_sum(clique) << std::endl;
        break; 
      }
    }
    graph.push_back(node);
  }

  /*for (auto node : graph) {
    delete node;
  }*/

  return 0;
}

If you want to download and compile everything, it's available on my GitHub here.

\$\endgroup\$
  • \$\begingroup\$ I think i would have give it a try the other way, searching for primes ending with 693 and then check if it fits (if it contain another prime). You are basically testing every primes you found, when only a very small set of prime ends with 693 \$\endgroup\$ – Cyrbil Aug 25 '15 at 6:26
  • \$\begingroup\$ @Cyrbil, I'm not sure you understand the problem. What is the significance of 693? The first 5-element prime pair set is {13, 5197, 5701, 6733, 8389}, and none of the primes produced ends in 693. \$\endgroup\$ – castle-bravo Aug 25 '15 at 15:14
  • \$\begingroup\$ Oups, okay i read the problem to fast, though the goal was to find the next prime in the set ... mb :) \$\endgroup\$ – Cyrbil Aug 25 '15 at 15:16
1
\$\begingroup\$

Try implementing it this way:

  1. Define a variable allCliques which will hold all of the cliques found (of any size.) Initialize allCliques to just the empty clique.

  2. Consider the next node - call it n.

  3. Let newCliques be all the new cliques you can form by adding n to an existing clique in allCliques.

  4. Check newCliques for a solution. If no solution is found, add newCliques to allCliques and repeat from step 2.

A clique is just a set of Ints. You could use a linked list, or a bit set, or whatever you want.

Here is part of a Haskell solution which might help you structure the problem in C++:

cliques :: (Int -> [Int]) -> [Int] -> [ Set ]
cliques adj nodes = go nodes [ Set.empty ]
  where
    go [] cs = []
    go (n:ns) cs = new ++ go ns (new ++ cs)
      where new = [ Set.insert n c | c <- cs, contains neighbors c]
            neighbors = Set.fromList (adj n)

Notes:

adj :: Int -> [Int]
   -- the adjacency function; given an Int it returns a list of
      SMALLER Ints which are adjacent (note SMALLER is important here)

nodes :: [Int]
   -- the nodes of the graph (in this case the primes)

Set - a set data structure - use to represent a clique

Set.empty - the empty set - used for the empty clique

++  - list concatenation

Set.insert :: Int -> Set -> Set - add a value to a set

contains :: Set -> Set -> Bool
   -- test if the second set is contained in the first set

When called with an adjacency function and list of nodes will return a stream of the cliques found.

To solve the problem:

solution = take 1 $ filter (\s -> Set.size s >= 5)
                  $ cliques adjacent primes

where primes is the (infinite) list of primes and adjacent p returns all of primes less than p which can be combined with p.

\$\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.