3
\$\begingroup\$

Here's my C++ solution for PE 43:

#include <algorithm> #include <iostream> #include <string> int main() { const int PRIMES[] {2, 3, 5, 7, 11, 13, 17}; std::string digits = "0123456789"; unsigned long long sum = 0; do { bool has_property = true; for (int i = 1; i <= 7; i++) { long substring_num = std::stol(digits.substr(i, 3)); if (substring_num % PRIMES[i - 1] != 0) { has_property = false; break; } } if (has_property) { sum += std::stol(digits); } } while ( std::next_permutation(digits.begin(), digits.end()) ); std::cout << sum << "\n"; }

Prompt: 1

AFAIK, my use of STL containers and algorithms is appropriate, but I'd like feedback from someone experienced. There are more optimizations I could do, such as skipping all permutations that have an odd digit in their 3rd (zero-indexed) position, but this already runs in under one second on my beat-up Mac and is therefore "good enough."

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Code looks good. I will suggest minor two changes First, Avoiding use of stol by using number array rather than string type for digits, second use of divisibility rules rather than actual division \$\endgroup\$ Commented Aug 22, 2021 at 7:30
  • 2
    \$\begingroup\$ Move backward: first, check 000, 017, 034, 051 etc - divisible by 17. If they have no duplicates, add one of the possible digits at the beginning and check for divisibility by 13, and so on. This will be much faster. \$\endgroup\$ Commented Aug 22, 2021 at 8:11
  • \$\begingroup\$ @nkvns I chose a string type because of substr, and I was willing to sacrifice a bit of performance for brevity. \$\endgroup\$ Commented Aug 23, 2021 at 0:07
  • \$\begingroup\$ The code doesn't really have significant quality issues, so any potential improvements may have to focus on performance anyway. Maybe you can clarify what you want to get out of a code review? \$\endgroup\$ Commented Aug 23, 2021 at 7:26
  • \$\begingroup\$ Skipping is easy: codeproject.com/Articles/1244739/… \$\endgroup\$ Commented Aug 23, 2021 at 14:23

1 Answer 1

Reset to default
4
\$\begingroup\$

The choice of algorithm seems good, and std::next_permutation() was exactly how I would implement the search.

Style review

We could separate the loop from the test for the divisibility property:

static bool has_euler43_property(const std::string& digits) { static constexpr unsigned int primes[] {2, 3, 5, 7, 11, 13, 17}; for (int i = 0; i < 7; ++i) { long substring_num = std::stol(digits.substr(i+1, 3)); if (substring_num % primes[i] != 0) { // failed a test return false; } } // all tests passed return true; } int main() { std::string digits = "0123456789"; unsigned long long sum = 0; do { if (has_euler43_property(digits)) { sum += std::stoul(digits); } } while ( std::next_permutation(digits.begin(), digits.end()) ); std::cout << sum << "\n"; }

That's a little easier to follow than using a has_property variable.

Note that I changed PRIMES to primes - we normally use upper-case only for preprocessor macros, which need particular care. I also changed the second std::stol to std::stoul, since we are accumulating unsigned values.

Performance review

I got a substantial speed-up by avoiding the substring creation and the call of std::stoul inside the loop:

 long substring_num = (digits[i+1] - '0') * 100 + (digits[i+2] - '0') * 10 + digits[i+3] - '0';

And a little more by changing the type and consolidating the subtraction:

 unsigned int substring_num = digits[i+1] * 100 + digits[i+2] * 10 + digits[i+3] - '0' * 111;

I shaved another 10% by prepending quick tests for divisibility by 2 and by 5:

// quick tests if (digits[3] % 2 != '0' % 2) { return 0; } if (digits[5] != '0' && digits[5] != '5') { return 0; }

Adding a quick test for multiples of 3 produced only a very small improvement, but allows us to skip the slow path for primes less than 7.

Reversing the order of testing (as there are fewer multiples of 17 than of 7) produced a tiny improvement too.

Improved code

On my system, this takes around 0.01 seconds, compared to 0.21 seconds for the original code:

#include <algorithm> #include <array> #include <iostream> #include <string> // returns the number itself for digit strings that satisfy the type // or zero for digit strings that don't // * digits must be a ten-digit string (no bounds checking here) static unsigned long long euler43_property(const std::string& digits) { static constexpr std::array primes = {2, 3, 5, 7, 11, 13, 17}; // quick tests if (digits[3] % 2 != '0' % 2) { return 0; } if ((digits[2] + digits[3] + digits[4]) % 3 != ('0' + '0' + '0') % 3) { return 0; } if (digits[5] != '0' && digits[5] != '5') { return 0; } // we skip the cases is covered above (i < 3) for (auto i = primes.size() - 1; primes[i] > 5; --i) { auto substring_num = digits[i+1] * 100 + digits[i+2] * 10 + digits[i+3] - '0' * 111; if (substring_num % primes[i] != 0) { // failed a test return 0; } } // all tests passed return std::stoul(digits); } int main() { std::string digits = "0123456789"; unsigned long long sum = 0; do { sum += euler43_property(digits); } while ( std::next_permutation(digits.begin(), digits.end()) ); std::cout << sum << "\n"; }
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Even more fun with primes! (BTW ('0' + '0' + '0') % 3 must be 0, yet I see why one might code as done here.) \$\endgroup\$ Commented Aug 23, 2021 at 12:47
  • \$\begingroup\$ And there was me, wondering if any coding that actually exists has an odd value for '0' and I never even noticed that! Good catch! \$\endgroup\$ Commented Aug 23, 2021 at 13:17
  • \$\begingroup\$ The test for 11 is that digits[6]+digits[8]-digits[7] is 0 or 11, for what that's worth. \$\endgroup\$ Commented Aug 23, 2021 at 21:42
  • \$\begingroup\$ @Teepeemm, that's true, but we're into the realms of diminishing returns there (and we would have to code the test for multiples of 7, or change the way the loop works), so I didn't implement that. \$\endgroup\$ Commented Aug 24, 2021 at 8:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.