Combinatorics, C++ and optimization

Question

Note: I have a working solution, my question is about optimization and other approaches.

Problem Description

Hello, I'm re-writing an old program I made that solves nonograms. As part of solving it, I generate (for some of the lines) an array of all possible ways to fit the numbers in.

I want to create a piece of code, that will iterate all the positions in which I can put the spaces, for example: if there's a line with size 5, and the numbers are 1, 1, there are multiple ways do order the numbers, like 1-1--, 1--1-, 1---1, --1-1, ... (- is a white box, while 1 will be black).

Problem Breakdown

So if we look at the example above, we can describe the options like this:

1. The total size is 5, and we have two 1, therefore we have 2 white boxes to play around with (1 must be between the numbers), I have another function that calculates that "free space".

2. We can index the possible places for the spaces this way: [0] 1 [1] 1 [2], meaning the spaces can go in each of the [indexes].

3. All the options of placing the spaces can be solved with nested loops, but since the "free space" and the possible indexes are dynamic, this is not an option.

4. For solution I try to create "dynamic" nested loops, with any range and depth, the question is:

Is there a more efficient way of doing so?

Possible Solution

The scope my question refers to is not related specifically to solving a nonorgram or even a specific language, but since I'm writing this in C++, I will post my attempt for a code that does so:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.
    int move_index;

    vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";
        cout << endl;

        for (move_index = iterators_number - 1;
             (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1); move_index--);
        if (move_index < 0) break;
        int new_value = options_iteration[move_index] + 1;
        for (; move_index < iterators_number; move_index++) options_iteration[move_index] = new_value;
    }

    return 0;
}

Output:

0 0 0 
0 0 1 
0 0 2 
0 0 3 
0 1 1 
0 1 2 
0 1 3 
0 2 2 
0 2 3 
0 3 3 
1 1 1 
1 1 2 
1 1 3 
1 2 2 
1 2 3 
1 3 3 
2 2 2 
2 2 3 
2 3 3 
3 3 3 

If anyone is interested in the full implementation, once it's done and fully documented, I will upload it to my GitHub account.

Thanks in advance for the helpers and commentators.

Answer 1

Overall Observations

The more code you provide the better the reviews you will get. There are 2 statements, 1 in the question and 1 in the comments after the question that almost make it off-topic for the Code Review site:

1. ... my real code does not print for each iteration, this is for easy testing.
2. I have another function that calculates that "free space".

As provided in the question the code is almost unreadable and therefore would be a problem for maintenance. If I were an teacher grading this code the best grade I can give it is a C (70%) because it compiles and runs. The variable names are meaningful. In a professional environment if I were your manager we would have a long talk in private about why it is important to make the code more readable.

In a professional environment you are very unlikely to be the only one maintaining the code for multiple reasons:

1. You may get promoted and not assigned to maintain the code anymore.
2. You may quit and get another job.
3. A bug may exist in the code that needs to be fixed and you are assigned to a higher priority project so someone else will be assigned to fix the code.

There are more reasons than just the 3 above. For all these reasons I will be addressing coding style here.

Possible Optimizations

The first rule of optimization is don't optimize, the second is find all the bottlenecks in the code (bottlenecks being functions that slow down the code). The primary way to optimize C++ code is to use the built in compiler optimization using the -O through -O3 compiler command lines. This will generally produce very fast code. It will be very difficult to provide optimizations for this code as currently presented, but if you are compiling for debug one possible optimization might be to use the C++ iterators provided for each of the container classes such as vector.

You might also want to make the variables iterators_number and iterators_range constants since they don't change.

    const int iterators_number = 3;
    const int iterators_range = 3;

Avoid using namespace std;

If you are coding professionally you probably should get out of the habit of using the using namespace std; statement. The code will more clearly define where cout and other identifiers are coming from (std::cin, std::cout). As you start using namespaces in your code it is better to identify where each function comes from because there may be function name collisions from different namespaces. The identifiercout you may override within your own classes, and you may override the operator << in your own classes as well. This stack overflow question discusses this in more detail.

Declare Variable as Necessary

As far as I can tell the variable move_index does not need to maintain it's value between iterations of the while (true) loop so it should be declared within the loop, the declaration should include the initialization of the variable in almost all cases, but definitely in this case.

Don't Use One line for Loops or if Statements

The code contains this line:

        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";

On my first time through the code I missed the fact that the for loop had an action. This code should be on 2 lines at least but preferably 4. 2 lines:

        for (int i = 0; i < iterators_number; i++)
            cout << options_iteration[i] << " ";

Why 4 lines? One of the easiest mistakes to make when maintaining code is to add a statement to a for loop or if statement without adding the braces necessary to make it part of the loop. So when creating new code it is better to add the to begin with:

        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }

I didn't come up with this, it was forced on me by a company coding standard, however, I saw the value of it having made that kind of mistake a number of times.

This version of the code is slightly longer but muc more readable and easier to maintain:

#include <vector>
#include <iostream>

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.

    std::vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }
        std::cout << std::endl;

        int move_index = iterators_number - 1;
        for ( ;
            (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1);
            move_index--)
            ;
        if (move_index < 0)
            break;

        int new_value = options_iteration[move_index] + 1;
        for ( ; move_index < iterators_number; move_index++)
        {
            options_iteration[move_index] = new_value;
        }
    }

    return 0;
}