Summing up ints in vectors for education

To get started with C++11/14/17, I decided to write a program that brute forces the problem described in this video (and gives a progress update every few seconds):


Divide the numbers [0, 31] into two sets A and B such that

• \$\sum_A {a} = \sum_B{b}\$

• \$\sum_A {a^2} = \sum_B{b^2}\$

• \$\sum_A {a^3} = \sum_B{b^3}\$

• \$\sum_A {a^4} = \sum_B{b^4}\$

How can I make this code more C++14-ish? My goal is not to make the code more mathematically clever, or necessarily faster. I mainly wanted to use a reasonable to high number of modern C++ standard features to brute-force-solve this problem.

```
#include
#include
#include
#include
#include
#include

int main() {

uint32_t split {0};
uint32_t print_mask { 2048 };
auto lastPrintTime = std::chrono::system_clock::now();
auto const SLOWER_THRESHOLD = std::chrono::seconds(5) ;
auto const FASTER_THRESHOLD = std::chrono::seconds(10) ;

while (split ::max()) {
if (split % print_mask == 0) {
double progress_percentage { (split/(double)std::numeric_limits::max()) * 100.0 };
std::cout (now - lastPrintTime);
lastPrintTime = now;

if (diff FASTER_THRESHOLD && print_mask > 10) print_mask /= 2;
}

std::vector va;
std::vector vb;

uint32_t mask {1};
for (int i=0; i<32; i++) {
((mask & split) != 0 ? va : vb).push_back(i);
mask = mask << 1;
}

int sum_a;
int sum_b;

sum_a = std::accumulate(va.begin(), va.end(), 0, [](auto x, auto y){return x + y;});
sum_b = std::accumulate(vb.begin(), vb.end(), 0, [](auto x, auto y){return x + y;});
if (sum_a != sum_b) goto next;

sum_a = std::accumulate(va.begin(), va.end(), 0, [](auto x, auto y){return x + y*y;});
sum_b = std::accumulate(vb.begin(), vb.end(), 0, [](auto x, auto y){return x + y*y;});
if (sum_a != sum_b) goto next;

sum_a = std::accumul

Use Functions

There is a ton of repetition in your code. You could make it much better by just factoring out the common parts.

Printing

You don't like how you print your vector? There's a function for that:

template 
std::ostream& operator const& xs) {
    bool first = true;
    os << '{';
    for (T const& x : x) {
        if (!first) os << ", ";
        os << x;
        first = false;
    }
    return os << '}';
}

And now you can just do:

std::cout << "A = " << va << ", B = " << vb << std::endl;

Checking Summation

There is a huge amount of repetition here. Effectively, we're summing f(x) on each vector, for differing x. So we can write a function for that:

template 
int accumulate(std::vector const& xs, F f) {
    int sum = 0;
    for (int x : xs) {
        sum += f(x);
    }
    return sum;

    // aka return boost::accumulate(xs | transformed(f), 0);
}

bool matches(std::vector const& A, std::Vector const& B, F f) {
    return accumulate(A, f) == accumulate(B, f);
}

Don't use goto

There is hardly ever a reason to use goto and this is not it. Once you refactor everything, you can just write out your test:

if (matches(va, vb, [](int x){ return x; }) &&
    matches(va, vb, [](int x){ return x*x; }) &&    
    matches(va, vb, [](int x){ return x*x*x; }) &&
    matches(va, vb, [](int x){ return x*x*x*x; }))
{
    std::cout << "Found: A=" << va << ", B=" << vb << std::endl;
    break;
}

No goto needed.

Use a for loop

You are looping on split from 0 to the max uint32_t value. This isn't obvious because you're using the wrong loop:

for (uint32_t split=0; split ::max(); ++split)

Returning from main

You don't have to use return EXIT_SUCCESS; or return 0;. As a special case for main, return 0 is implied.

Better algorithm

Looping over a few billion elements isn't going to be the best approach... especially when there are only ~300 million unique sets to check to begin with (those that have 16 elements on each side, ignoring mirrored duplicates for which one ends up being A).

StackExchange Code Review Q#111722, answer score: 7