# Pre-calculate the winning combinations for an n-sized tic tac toe board using C++ functional programming

This code pre-calculates the winning combinations for an n-sized tic tac toe board.

I first created my function using an imperative approach. This is just how I naturally write code most of the time. I then tried to think about the problem using a "What I want to accomplish?" approach, rather than "What do I want it to do?" In the end I think I still ended up with an imperative approach, just using STL algorithms as loops.

Imperative approach:

std::vector<std::vector<int>> rules3(const int x){
using namespace std;

vector<vector<int>> seqs;
for(int n=0; n<x; ++n){
vector<int> seq;
for(int m=0; m<x; ++m){
seq.push_back(n*x+m);
}
seqs.push_back(seq);
}
for(int n=0; n<x; ++n){
vector<int> seq;
for(int m=0; m<x; ++m){
seq.push_back(n+x*m);
}
seqs.push_back(seq);
}
vector<int> seq;
for(int n=0; n<x; ++n){
seq.push_back(n*x+n);
}
seqs.push_back(seq);
seq.clear();
for(int n=0; n<x; ++n){
seq.push_back(x-1+n*(x-1));
}
seqs.push_back(seq);

return seqs;
}


Getting more functional:

std::vector<std::vector<int>> rules2(const int x){
using namespace std;

vector<vector<int>> seqs;
vector<int> iter(x);
iota(iter.begin(), iter.end(), 0);

for(auto n: iter){
vector<int> seq;
for(auto m: iter){
seq.push_back(n*x+m);
}
seqs.push_back(seq);
}
for(auto n: iter){
vector<int> seq;
for(auto m: iter){
seq.push_back(n+x*m);
}
seqs.push_back(seq);
}
vector<int> seq;
seq.clear();
for(auto n: iter){
seq.push_back(n*x+n);
}
seqs.push_back(seq);
seq.clear();
for(auto n: iter){
seq.push_back(x-1+n*(x-1));
}
seqs.push_back(seq);

return seqs;
}


Functional approach? (still feels imperative):

std::vector<std::vector<int>> rules1(const int x){
using namespace std;

vector<vector<int>> seqs;
vector<int> iter(x);
iota(iter.begin(), iter.end(), 0);

transform(iter.begin(), iter.end(), back_inserter(seqs), [&](const int& n){
vector<int> seq;
transform(iter.begin(), iter.end(), back_inserter(seq), [&](const int& m){
return n*x+m;
});
return seq;
});
transform(iter.begin(), iter.end(), back_inserter(seqs), [&](const int& n){
vector<int> seq;
transform(iter.begin(), iter.end(), back_inserter(seq), [&](const int& m){
return n+x*m;
});
return seq;
});
vector<int> seq;
transform(iter.begin(), iter.end(), back_inserter(seq), [&](const int& n){
return n*x+n;
});
seqs.push_back(seq);
seq.clear();
transform(iter.begin(), iter.end(), back_inserter(seq), [&](const int& n){
//return (x-n-1)*x+n; // 6,4,2
return x-1+n*(x-1); // 2,4,6
});
seqs.push_back(seq);

return seqs;
}


Output when printing:

rules3
std::vector(0, 1, 2)
std::vector(3, 4, 5)
std::vector(6, 7, 8)
std::vector(0, 3, 6)
std::vector(1, 4, 7)
std::vector(2, 5, 8)
std::vector(0, 4, 8)
std::vector(2, 4, 6)
rules2
std::vector(0, 1, 2)
std::vector(3, 4, 5)
std::vector(6, 7, 8)
std::vector(0, 3, 6)
std::vector(1, 4, 7)
std::vector(2, 5, 8)
std::vector(0, 4, 8)
std::vector(2, 4, 6)
rules1
std::vector(0, 1, 2)
std::vector(3, 4, 5)
std::vector(6, 7, 8)
std::vector(0, 3, 6)
std::vector(1, 4, 7)
std::vector(2, 5, 8)
std::vector(0, 4, 8)
std::vector(2, 4, 6)

• Is the Ranges library a possibility? Commented Jul 9, 2019 at 12:02
• @L.F. Yes, I have been using boost in other areas of my code. I have been wanting to experiment with that. Did you have something specific in mind? Commented Jul 9, 2019 at 13:29

Here are some suggestions. This answers uses the Range-v3 library and assumes

#include <range/v3/all.hpp>

namespace view = ranges::view;

1. Please include the #includes and supply a small test program in the future. You probably have written them anyway, so why not post them to save reviewers' time? :)

2. int may be too small for indexes. Consider using std::size_t. You can define a type alias for flexibility.

using index_t = std::size_t;

3. The type std::vector<std::vector<index_t>> occurs many times. Save time by writing

using rule_t = std::vector<index_t>
using rules_t = std::vector<rule_t>;

4. The concept "$$\n \times n\$$ board" only makes sense when $$\n\$$ is a positive integer. Therefore, enforce the pre-condition $$\n \ge 1\$$. Also, the name x is a bit vague. size may be better.

rules_t rules(index_t size)
{
if (size == 0)
throw std::invalid_argument{"..."};
// ...
}

5. rules(1) currently returns {{0}, {0}, {0}, {0}}, which is definitely wrong. It should return {{0}}. Your general logic is "$$\n\$$ rows + $$\n\$$ columns + $$\2\$$ diagonals", which only applies to $$\n \ge 2\$$. The easiest approach would be a special case:

rules_t rules(index_t size)
{
// ...
else if (size == 1)
return {{0}};
}

6. Following the previous bullet, why not make separate functions to make your logic clear?

rules_t rules(index_t size)
{
// ...
else {
auto rows = rules_row(size);
auto columns = rules_column(size);
auto diagonals = rules_diagonal(size);
return ranges::to<rules_t>(view::concat(rows, columns, diagonals));
}
}


where view::concat concatenates the three vectors and ranges::to converts the result to the desired return type. (Note that view::concat is disabled with rvalues to prevent dangling iterators, so we first store the subvectors.)

7. The rules_row function is easy to write:

rules_t rules_row(index_t size)
{
return view::ints(index_t(0), size * size) | view::chunk(size);
}


view::ints generate a left-inclusive sequence of integers {0, 1, 2, ..., size * size - 1}, and view::chunk(size) breaks it into chunks each of size size.

8. The rules_column function is a bit tricky, because the Range library does not provide a function like chunk that splits like this. We do have a function stride, so we can write a manual "loop": (it took me quite a while to figure this out, so tell me if there is a better way!)

rules_t rules_column(index_t size)
{
return view::ints(index_t(0), size) |
view::transform([=](index_t col) {
return view::ints(index_t(col), size * size) | view::stride(size);
});
}


view::ints(index_t(0), size) generates the column numbers. Each of them is passed to the lambda. The lambda returns the corresponding rule for each column.

9. The rules_diagonal function is moderately simple:

rules_t rules_diagonal(index_t size)
{
return {
view::ints(index_t(0), size) |
view::transform([=](index_t r) { return r * (size + 1); }),
view::ints(index_t(1), size + 1) |
view::transform([=](index_t r) { return r * (size - 1); })
};
}


Here, we always have two rules: one for the primary diagonal

{0 * size + 0, 1 * size + 1, 2 * size + 2, ..., (size - 1) * size + (size - 1)}


which is equivalent to

{0, 1, 2, ..., size - 1} * (size + 1)


and the other for the secondary diagonal

{size - 1, 2 * size - 2, 3 * size - 3, ... size * size - (size - 1)}


which is equivalent to

{1, 2, 3, ..., size + 1} * (size - 1)

10. Putting everything together:

#include <vector>
#include <range/v3/all.hpp>

namespace view = ranges::view;

using index_t = std::size_t;
using rule_t = std::vector<index_t>;
using rules_t = std::vector<rule_t>;

rules_t rules_row(index_t size)
{
return view::ints(index_t(0), size * size) | view::chunk(size);
}

rules_t rules_column(index_t size)
{
return view::ints(index_t(0), size) |
view::transform([=](index_t col) {
return view::ints(index_t(col), size * size) | view::stride(size);
});
}

rules_t rules_diagonal(index_t size)
{
return {
view::ints(index_t(0), size) |
view::transform([=](index_t r) { return r * (size + 1); }),
view::ints(index_t(1), size + 1) |
view::transform([=](index_t r) { return r * (size - 1); })
};
}

rules_t rules(index_t size)
{
if (size == 0)
throw std::invalid_argument{"A board cannot have size zero"};
else if (size == 1)
return {{0}};
else {
auto rows = rules_row(size);
auto columns = rules_column(size);
auto diagonals = rules_diagonal(size);
return view::concat(rows, columns, diagonals);
}
}


(live demo, tests the function for size = 1, 2, 3, ..., 10)

• Thanks for taking a crack at this. You have given a lot to think about. Commented Jul 10, 2019 at 14:44