Summing up ints in vectors for education

Question

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 <vector>
#include <iostream>
#include <numeric>
#include <chrono>
#include <iomanip>
#include <cstdlib>

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 < std::numeric_limits<uint32_t>::max()) {
        if (split % print_mask == 0) {
            double progress_percentage { (split/(double)std::numeric_limits<uint32_t>::max()) * 100.0 };
            std::cout << "Currently checking " << std::setw(20) << std::setfill(' ') << split << ", " << std::fixed << progress_percentage << '%' << std::endl;

            auto now = std::chrono::system_clock::now();
            auto diff = std::chrono::duration_cast<std::chrono::seconds>(now - lastPrintTime);
            lastPrintTime = now;

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

        std::vector<int> va;
        std::vector<int> 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::accumulate(va.begin(), va.end(), 0, [](auto x, auto y){return x + y*y*y;});
        sum_b = std::accumulate(vb.begin(), vb.end(), 0, [](auto x, auto y){return x + y*y*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*y*y;});
        sum_b = std::accumulate(vb.begin(), vb.end(), 0, [](auto x, auto y){return x + y*y*y*y;});
        if (sum_a != sum_b) goto next;

        std::cout << "A = " << sum_a << " = [";
        for (auto v: va) {
            std::cout << v << ", ";
        }
        std::cout << ']' << std::endl << "B = " << sum_b << " = [";
        for (auto v: vb) {
            std::cout << v << ", ";
        }
        std::cout << ']' << std::endl;
        break;

        next:
        split++;
    }

    puts("Win");

    return EXIT_SUCCESS;
}

I am especially unhappy with the way I print the vectors. I have seen some code examples about ostream_iterators, but these looked even worse to me.

Answer 1

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 <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> 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 <typename F>
int accumulate(std::vector<int> 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<int> const& A, std::Vector<int> 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 < std::numeric_limits<uint32_t>::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).

Answer 2

• Remove the gotos: they increase reading difficulty level (avoid them when you can). In this case, you can use continue in place of each goto, while doing the increment before that, keeping it all within the if statement.

  if (sum_a != sum_b)
  {
      split++;
      continue;
  }
  

• There's a little inconsistency here:

  uint32_t split {0};
  uint32_t print_mask { 2048 };
  

  Either form of the curly braces use is okay, but just stick with one. I personally like the latter because it's a little easier to read.

  The semicolons are separated just here:

  auto const SLOWER_THRESHOLD = std::chrono::seconds(5) ;
  auto const FASTER_THRESHOLD = std::chrono::seconds(10) ;
  

  It may be minor, but this can show a lack of finer detail to the code. Again, pick one form and stick with it.

• You can consider separating lastPrintTime from the rest of the code to make it easier to tell where the timer starts. You can also rename this to something like start, but it's up to you.

• Since you're not using using namespace std (and it's good that you're not), be sure to prepend uint32_t with std::. You should also be including <cstdint> for these integer types.

• This could use more spacing:

  for (int i=0; i<32; i++) {
  

  It's more readable to put whitespace between each operator as such:

  for (int i = 0; i < 32; i++) {
  

  You can also use ++i instead since this is just an int. This concept is called pre/post increment/decrement. They will only really make a difference when you use the variable to do something else within the same expression.

  With pre-increment, the variable will be incremented and then used for the evaluation. With post-increment, it is used at its current value and then incremented after the expression is evaluated.

  There can also be a slight performance penalty when using the post-increment with classes as opposed to native types.

• There's no need for std::endl unless you really need to flush the buffer as well. Otherwise, use "\n" instead to just print a newline. More info about that can be found here.

• It's best to avoid putting everything into main(). Plus, the while loop is doing a lot of work and it's hard to determine the different tasks that are being done in it. You should consider at least putting the printing into separate functions. It's good to separate computation from printing.

• Since you already have <iostream>, you might as well use that instead of puts() at the end.

Answer 3

Prefer the standard library algorithms

Library code already works with the language features you are implementing, is written with a shorter footprint in your own code, has been tested, and offers a higher level of abstraction. Printing could be written using std::copy with std::experimental::ostream_joiner<> or your own ostream joiner.

Prefer suitable abstractions

Use functions/classes to represent application concepts. Code you write should be short (5-15 lines is normal) and clear. Abstractions can easily be tested to ensure correctness.

Consider refactoring some of your code into their abstractions (split tracking, sequence generation, etc).

Keeps scopes small

Prevents the accidental misuse of values, minimizes resource retention, and improves the readability of your code.

Refactoring your code into tighter abstractions will take care of this.

Avoid UPPERCASE names

These names should be reserved for macros and the avoidance of such naming schemes prevents issues like unintended macro substitutions.

Always initialize an object

Protect yourself from the undefined behavior related to used-before-set errors.

Declare objects const/constexpr unless you want mutability

Prevent accidental modifications to constant values.

Prefer for instead of while when utilizing loop variables

Minimizes scope of the loop variable and the logic is immediately visible at the control structure.

Avoid goto

goto is a powerful control structure that makes code difficult to follow and causes the state to become indeterminate. Usage of goto can always be refactored into one of the alternative flow control options.

Prefer using symbolic constants over magic constants

Unnamed constants are often hard to understand and sometimes overlooked.

Avoid std::endl

If you want to print end-of-line, prefer ’/n’. If you intended to flush the buffer, be explicit and indicate your intention by using std::flush.

Use a consistent naming style

Being consistent with your naming style for improved readability.

Organize your headers

When maintaining code, linear searches through long unsorted includes becomes very slow and problematic. Prefer to group libraries from local to global with each group ordered lexicographically. From local to global:

• Prototype/Interface headers
• Project-level headers
• Non-Standard headers
• Standard Headers
• System headers

Note: Some system headers are poorly written and will require specific ordering due to external dependencies and those cases should be mentioned via comment.

Wrap long lines of code to a reasonable length

Helps with readability. It is much easier to scroll vertically than horizontally.