# Euler problem c++ / std::library usage

Euler problems (projecteuler.net) often invites to quick and dirty solutions.

While hurrying through Problem 32 I found myself in want of the std:: toolkit. Not sure what it is though.

The problem description is included in the first comment.

I would really appreciate any suggestions as for the usage of the tools provided by standard c++ (11 if need be, lambdas might make it more succinct/elegant).

/*
* File:   main.cpp
* Author: cpt_giraffe
*
*

* 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.

* 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.

* Created on November 27, 2013, 9:41 PM
*/

#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <numeric>
#include <sstream>

using namespace std;

// store the products, a set is ideal because of the HINT:
set<unsigned> products;

/**
* Insert to products if string arguments is a proper product
*/
void insert_if_product(string factor1, string factor2, string product) {
stringstream values(factor1 + " " + factor2 + " " + product);

// is this a valid product.  (Most cases says no)
unsigned f1, f2, p;
values >> f1 >> f2 >> p;
if (f1 * f2 == p) {
products.insert(p);
}

}

/**
* magnitudes needs to add up: I'm checking
* 9 digits total
* m1 * m3 = m5
* m1 * m4 = m4
* m2 * m3 = m4
* Is this all?
*
* @param check this permutation
*/
void check_products(string perm) {
// all permutations are coming from perm, so no need to perm stuff here.
string factor1 = perm.substr(0, 1);
string factor2 = perm.substr(1, 3);
string product = perm.substr(4, 5);

insert_if_product(factor1, factor2, product);

factor1 = perm.substr(0, 1);
factor2 = perm.substr(1, 4);
product = perm.substr(5, 4);

insert_if_product(factor1, factor2, product);

factor1 = perm.substr(0, 2);
factor2 = perm.substr(2, 3);
product = perm.substr(5, 4);

insert_if_product(factor1, factor2, product);

}

int main(int argc, char** argv) {
string s = "123456789";
do {
check_products(s);

} while (next_permutation(s.begin(), s.end()));

// Test case
if (products.find(7254) != products.end()) {
cout << "found 7254" << endl;
} else {
cout << "did not find 7254" << endl;
}
unsigned sum = 0;

sum = accumulate(products.begin(), products.end(), 0);
cout << "Sum:" << sum << endl;
return 0;
}

• I think, you should add a reference to the original task in your comment. I think it's at least as important as the date and stating that you were the author. – Wolf Nov 28 '13 at 12:09

1. Your conversions are... pretty WTF :)

void insert_if_product(string const& factor1, string const& factor2, string const& product) {
auto p = std::stoul(product);
if (std::stoul(factor1, nullptr, 10) * std::stoul(factor2, nullptr, 10) == p) {
products.insert(p);
}
}


I mean why use an intermediate stream? Why, if you're using a stream, build it using string concatenation? Also, why pass in copies of read-only strings?!

2. avoid unnecesary allocations:

string factor1 = perm.substr(0, 1);
string factor2 = perm.substr(1, 3);
string product = perm.substr(4, 5);


is gonna do a lot of allocations. Probably more than you'd think. At least, reuse factor1,factor2 and product capacities? (My sample below makes them static)

### Edit Squeezing a few more drops out:

3. avoiding strings in more places avoids the temps from perm.substr(). Now I just directly assign by indices:

    factor1.assign(perm.begin()+0, perm.begin()+1);
factor2.assign(perm.begin()+1, perm.begin()+4);
product.assign(perm.begin()+4, perm.begin()+9);

4. using unordered_set seems to shave off milliseconds on average :)

Quick performance comparison (g++ -std=c++11 -march=native -O3) shows the time taken goes down from ~1.036s to ~0.116s.

So, roughly 8.9x speed effectively.

Full code:

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <sstream>

// store the products, a set is ideal because of the HINT:
std::unordered_set<unsigned> products;

/**
* Insert to products if string arguments is a proper product
*/
void insert_if_product(std::string const& factor1, std::string const& factor2, std::string const& product) {
auto p = std::stoul(product);
if (std::stoul(factor1, nullptr, 10) * std::stoul(factor2, nullptr, 10) == p) {
products.insert(p);
}
}

/**
* magnitudes needs to add up: I'm checking
* 9 digits total
* m1 * m3 = m5
* m1 * m4 = m4
* m2 * m3 = m4
* Is this all?
*
* @param check this permutation
*/

void check_products(std::string const& perm)
{
static std::string factor1, factor2, product;
// all permutations are coming from perm, so no need to perm stuff here.
factor1.assign(perm.begin()+0, perm.begin()+1);
factor2.assign(perm.begin()+1, perm.begin()+4);
product.assign(perm.begin()+4, perm.begin()+9);

insert_if_product(factor1, factor2, product);

//  factor1.assign(perm.begin()+0, perm.begin()+1);
factor2.assign(perm.begin()+1, perm.begin()+5);
product.assign(perm.begin()+5, perm.begin()+9);

insert_if_product(factor1, factor2, product);

factor1.assign(perm.begin()+0, perm.begin()+2);
factor2.assign(perm.begin()+2, perm.begin()+5);
//  product.assign(perm.begin()+5, perm.begin()+9);

insert_if_product(factor1, factor2, product);
}

int main() {
std::string s = "123456789";

do {
check_products(s);
} while(std::next_permutation(std::begin(s), std::end(s)));

std::cout << "Sum:" << std::accumulate(products.begin(), products.end(), 0u) << "\n";
}

• updated now 8x faster, check_products back as a free function (better IMO). Also, note subtle things like 0u in the accumulate` call! – sehe Nov 28 '13 at 0:46
• And thank you for your time and insights sehe. – Captain Giraffe Nov 28 '13 at 21:48
• Oh hey, shaved off another 15% after actually looking at the indices :). Now ~8.9x faster :) – sehe Nov 30 '13 at 23:22