# euler 32 sum of pan digital products

Mar 4, 2015

Pretty dumb naive solution.

Statutory Warning: Spoilers ahead

``````using std::vector;
static const int kNumDigits = 9;

int getNumber(const vector<int>& vNum) {
int result = 0;
for (int i = 0; i < vNum.size(); ++i) {
result = result * 10 + vNum[i];
}
return result;
}

bool isProduct(const vector<int>& vMultA,
const vector<int>& vMultB,
const vector<int>& vProduct) {
int multa = getNumber(vMultA);
int multb = getNumber(vMultB);
int product = getNumber(vProduct);
bool result = (multa * multb == product);
if (result) {
std::cout << "Debug: Testing " << multa << " * " << multb << " = " << product
<< "  --- MATCH!\n";
}
return result;
}

// Try all possible splits from this combination
void tryPermutation(const vector<int>& p,
int* total_matches,
std::unordered_set<int>* products) {
assert(p.size() == kNumDigits);
// There are nine digits, indexed from 0 to 8
// First number spans 0 to i, the second i + 1 to j, third is from j + 1 to 8
for (int i = 0; i <= kNumDigits - 3; ++i) {
for (int j = i+1; j <= kNumDigits - 2; ++j) {
vector<int> n1, n2, n3;
for (int k = 0; k <= i; ++k) {
n1.push_back(p[k]);
}
for (int k = i+1; k <= j; ++k) {
n2.push_back(p[k]);
}
for (int k = j+1; k <= kNumDigits-1; ++k) {
n3.push_back(p[k]);
}
if (isProduct(n1,n2,n3)) {
++(*total_matches);
products->insert(getNumber(n3));
}
}
}
}

int main() {
vector<int> digits;
for (int i = 1; i <= kNumDigits; ++i) {
digits.push_back(i);
}
int total_matches = 0;
std::unordered_set<int> products;
do {
tryPermutation(digits, &total_matches, &products);
} while (std::next_permutation(digits.begin(), digits.end()));
int products_sum = 0;
for (const auto& p : products) {
products_sum += p;
}
std::cout << "Number of matches = " << total_matches << ", "
<< "Sum of products = " << products_sum << std::endl;
}

``````

Runs as follows:

``````~/cpp \$ time ./Test
Debug: Testing 12 * 483 = 5796  --- MATCH!
Debug: Testing 138 * 42 = 5796  --- MATCH!
Debug: Testing 157 * 28 = 4396  --- MATCH!
Debug: Testing 159 * 48 = 7632  --- MATCH!
Debug: Testing 1738 * 4 = 6952  --- MATCH!
Debug: Testing 18 * 297 = 5346  --- MATCH!
Debug: Testing 186 * 39 = 7254  --- MATCH!
Debug: Testing 1963 * 4 = 7852  --- MATCH!
Debug: Testing 198 * 27 = 5346  --- MATCH!
Debug: Testing 27 * 198 = 5346  --- MATCH!
Debug: Testing 28 * 157 = 4396  --- MATCH!
Debug: Testing 297 * 18 = 5346  --- MATCH!
Debug: Testing 39 * 186 = 7254  --- MATCH!
Debug: Testing 4 * 1738 = 6952  --- MATCH!
Debug: Testing 4 * 1963 = 7852  --- MATCH!
Debug: Testing 42 * 138 = 5796  --- MATCH!
Debug: Testing 48 * 159 = 7632  --- MATCH!
Debug: Testing 483 * 12 = 5796  --- MATCH!
Number of matches = 18, Sum of products = 45228
15.517 secs
``````

(Wait, why C++ instead of … other recent languages? Couple of reasons: (1) I thought I’d need to brute force this (though it eventually turned out to take much less time than I anticipated), and (2) I’m sort of over the over-experimentation with languages that I’m not really going to use, and I’m not going to get much out of anyway. Yes, tough. Deal with it)