Checking for a match in each element of a 2d vector

Question

I'm creating text based TicTacToe in C++ and need to create a function that checks for a win.

Right now, I have a vector of all the moves player X has made:

std::vector<int> x_vector = {1, 2, 3, 5, 7};

I also have a 2d vector of win conditions:

std::vector<std::vector> > wins = {{1, 2, 3}, {4, 5, 6}, {7, 8, 8}};

In this case, each element of the wins vector represents a win condition. If player X ever has a combination of inputs in their vector that includes one of the win conditions, I'm trying to get a bool function to return true.

I'm new to C++ and coding in general, so all patience is appreciated, and the simpler the solution you can help me find the better.

Answer 1

You can iterate through your list of known wins, checking each to see if it is a subset of the list of user's moves. The std::includes function will do this test – but note that the two 'lists' need to be sorted.

To avoid having to manually sort the list of user's moves after each input, you can use the std::set container (which is inherently sorted), instead of std::vector.

The following snippet shows a relatively simple implementation of an isWin() function using this approach, along with some rudimentary test cases:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm> // For std::includes

bool isWin(const std::set<int>& test)
{
    static std::vector<std::set<int>> winlist = { 
        {1, 2, 3}, {4, 5, 6}, {7, 8, 9},    // Horizontal lines
        {1, 4, 7}, {2, 5, 8}, {3, 6, 9},    // Vertical lines
        {1, 5, 9}, {3, 5, 7},               // Diagonal lines
    };

    for (auto win : winlist) {
        if (std::includes(test.begin(), test.end(), win.begin(), win.end()))  {
            return true; // Match - Win!
        }
    }
    return false; // Didn't get a match - no win
}

int main()
{
    std::set<int> s1{ 1, 2 }; // Trivial "No win" (only 2 moves)
    std::cout << "s1: " << isWin(s1) << "\n";

    std::set<int> s2{ 1, 2, 3 }; // Trivial "Win" (top row)
    std::cout << "s2: " << isWin(s2) << "\n";

    std::set<int> s3{ 2, 4, 1, 5 }; // " No Win"
    std::cout << "s3: " << isWin(s3) << "\n";

    std::set<int> s4{ 5, 2, 4, 6 }; // "Win" (middle row)
    std::cout << "s4: " << isWin(s4) << "\n";

    std::set<int> s5{ 5, 1, 3, 6, 9 }; // "Win" (diagonal)
    std::cout << "s5: " << isWin(s5) << "\n";

    return 0;
}

Note that this approach may not be the best for checking wins in a Tic-Tac-Toe game; however, if your purpose is to learn about vectors, sets and looking for matching sub-sequences, it may provide a useful starting-point.

---

For your actual user input, you would declare and initialize an empty set and then add moves using the insert member function of the std::set container class; something like this:

int main()
{
    std::set<int> user{}; // Empty Set
    user.insert(5);
    user.insert(2);
    user.insert(4);
    user.insert(6);
    std::cout << "user (1): " << isWin(user) << "\n";
    user.clear();
    user.insert(2);
    user.insert(4);
    user.insert(1);
    user.insert(5);
    std::cout << "user (2): " << isWin(user) << "\n";
    return 0;
}