3
\$\begingroup\$

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)
Improve this question
\$\endgroup\$
  • \$\begingroup\$ Is the Ranges library a possibility? \$\endgroup\$ – L. F. Jul 9 '19 at 12:02
  • \$\begingroup\$ @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? \$\endgroup\$ – Demolishun Jul 9 '19 at 13:29
2
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
  • \$\begingroup\$ Thanks for taking a crack at this. You have given a lot to think about. \$\endgroup\$ – Demolishun Jul 10 '19 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.