current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite
1

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;
}
share|improve this question
    
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 Answer 1

up vote 7 down vote accepted

  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";
}
share|improve this answer
1  
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
1  
Oh hey, shaved off another 15% after actually looking at the indices :). Now ~8.9x faster :) –  sehe Nov 30 '13 at 23:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.