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:
The total size is 5, and we have two
1
, therefore we have2
white boxes to play around with (1 must be between the numbers), I have another function that calculates that "free space".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]
.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.
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.
'\n'
compared tostd::endl
makes your program much faster \$\endgroup\$std::endl
early on as it is much slower than printing a new line ('\n'
). That's why I believed it is good for you to know😁 \$\endgroup\$iterators_number = 2
anditerators_range = 3
. There is repetition in the output, is this fine? \$\endgroup\$