Saturday, June 8, 2013

Project Euler Problem 32

After quite a long while I did another Project Euler Problem: 32 - Pandigital products.
Quoting projecteuler:


We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, 39  186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

The problem is quite straight forward: For all permutations of 123456789 check if you can form a pandigital product. If so, add the product to a unique set. The first five digits of each permutation are reserved to form the two factors, the last four for the resulting product.
The STL offers all the neccessary tools: std::next_permutation and std::set. Obviously, the implementation did not aim for good design.


bool check_product(int x1, int x2, int res) {
  return (x1*x2) == res;
}

template <typename t>
int get_int_from_array(T* begin, T* end) {
  --end;
  --begin;
  int res = 0;
  for (int n = 1; end != begin; --end, n *= 10) {
    res += n*(*end);
  }
  return res;
}


void get_set_of_pandigital_products(int* begin, int* end, std::set<int>& prods) {
  int n_digits = end-begin;
  int n_max = 5;
  int x1, x2, res;
  do {
    for (int i = 0; i < n_max-1; ++ i) {
      x1 = get_int_from_array(begin, begin+i);
      x2 = get_int_from_array(begin+i, begin+n_max);
      res = get_int_from_array(begin+n_max, begin+n_digits);
      if (check_product(x1, x2, res)) {
        prods.insert(res);
      }
    }
  } while (std::next_permutation(begin, end));
}

As usual, the code can be found on github.

No comments:

Post a Comment