#include <map>
#include <tuple>

/* This file specifies the (mandatory) interface. As usual, you can
 * add additional classes and additional attributes and methods to
 * existing classes. */

/* This class, ‹gttt› (short for generalized tic-tac-toe), provides
 * the entire interface of the game. */
class gttt {
    int players_count;
    int win_count;
    std::map<std::tuple<int, int, int>, int> board;
    int active_player;

public:
    /* Start a new game with a given number of players. The
     * ‹to_win› argument specifies how many consecutive symbols need
     * to be placed by the same player in order to win the game. The
     * number of players must be between 2 and 1000000 (inclusive).
     * Same limits apply to the length of the winning sequence. */
    gttt( int players, int to_win ) {
    players_count = players;
    win_count = to_win;
    active_player = 1;
    }

    /* Which player plays next. Players are numbered from 0 and play
     * in ascending order (player 0 goes first). */
    int next() const {
        if(active_player == players_count) {
            return 0;
        }
        return active_player;
    }


    void next_player() {
        if (players_count >= active_player) {
            active_player += 1;
        }
        active_player = 1;
    }

    /* Play the active player's round by placing a mark on the cell
     * given by (x, y, z). Returns true if the move was valid.
     * Returns false if the cell was already occupied (and does not
     * change the state in this case and the player's round is not
     * completed).  */
    bool play( int x, int y, int z ) {
        if (get(x, y, z) == 0) {
            board[std::tuple(x, y, z)] = active_player;
            next_player();
            return true;
        }
        return false;
    }

    /* Return true if the specified cell is empty, false otherwise. */
        bool empty( int x, int y, int z ) const {
        return !board.count(std::tuple(x, y, z));
        //return board.at(std::tuple(x, y, z)) == 0;
    }

    int get(int x, int y, int z) const {
        if (!empty(x, y, z)) { return 0; }
        return board.at(std::tuple(x, y, z));
    }
    /* Return the identifier of the player who owns (placed their
     * mark on) the given cell. The behaviour is unspecified if the
     * cell is empty. */
        int owner( int x, int y, int z ) const {
        int own = board.at(std::tuple(x, y, z));
        if (own != 0) {
            return own;
        }
        return -1;
        //TODO non-defiend
    }


    bool line_check(int c_x, int c_y, int c_z, int d_x, int d_y, int d_z, int player) const {
        int count = 1;
        bool left = true;
        bool right = true;

        while (!left && !right) {
            if (right) {
                if (get(c_x + d_x, c_y + d_y, c_z + d_z) == player) {
                    ++count;
                } else {
                    right = false;
                }
            }
            if (left) {
                            if (get(c_x - d_x, c_y - d_y, c_z - d_z) == player) {
                                    ++count;
                            } else {
                                    left = false;
                            }
                    }
            if (count == win_count) {
                return true;
            }
        }
        return false;
    };

    /* True iff there is a winning sequence on the grid. */
        bool finished() const {
        for (auto itr = board.begin(); itr != board.end(); ++itr) {
            if (is_winnable_from(std::get<0>(itr->first), std::get<1>(itr->first),std::get<2>(itr->first))) {
                return true;
            }
        }
        return false;
    };

    /* The player who won. Undefined unless finished() is true. */
        int winner() const {
        if (finished() ) {
            if(active_player != 1) {
                return active_player - 1;
            }
            return players_count;
        }
        return -1;
        //TODO

    }

    /* Returns true if the next player can immediately win the game
     * by placing their mark strategically. */
        bool may_win() const {
        for (auto itr = board.begin(); itr != board.end(); ++itr) {
                        if (itr->second == active_player) {

                        }
                }
                return false;

    }


    bool is_winnable_from(int c_x, int c_y, int c_z) const {
        for(int i = -1; i <= 1; ++i) {
                    for(int j = -1; j <= 1; ++j) {
                            for(int k = -1; k <= 1; ++k) {
                                    if (line_check(c_x, c_y, c_z, i, j, k, get(c_x, c_y, c_z))) { return true;}
                            }
                    }
        }
        return false;
    }

};