Euler problem c++ / std::library usage

Question

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

• Wolf: 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.

Answer 1

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";
}

• sehe: updated now 8x faster, check_products back as a free function (better IMO). Also, note subtle things like 0u in the accumulate call!
• sehe: Oh hey, shaved off another 15% after actually looking at the indices :). Now ~8.9x faster :)