Project Euler #43 (C++)

Question

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

• nkvns: 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
• Pavlo Slavynskyy: 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.
• William Bradley: @nkvns I chose a string type because of substr, and I was willing to sacrifice a bit of performance for brevity.
• L. F.: 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?
• JDługosz: Skipping is easy: codeproject.com/Articles/1244739/…

Answer 1

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

• chux: Even more fun with primes! (BTW ('0' + '0' + '0') % 3 must be 0, yet I see why one might code as done here.)
• Toby Speight: 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!
• Teepeemm: The test for 11 is that digits[6]+digits[8]-digits[7] is 0 or 11, for what that's worth.
• Toby Speight: @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.