"""Rules for vanishing tic-tac-toe.

Each seat may have at most MAX_PIECES on the board. With a full set, your oldest
piece is removed as your turn starts, so you have at most MAX_PIECES - 1 pieces down
while placing and may place on the square it left.
"""

LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),  # rows
    (0, 3, 6), (1, 4, 7), (2, 5, 8),  # columns
    (0, 4, 8), (2, 4, 6),             # diagonals
]
MAX_PIECES = 3


class Game:
    def __init__(self):
        self.first = 0  # seat that moves first this round; alternates on rematch
        self.new_round()

    @classmethod
    def from_history(cls, history, turn):
        """Rebuild a round from each seat's cells (oldest first). Raises ValueError if invalid."""
        try:
            hx, ho = (list(h) for h in history)
        except (TypeError, ValueError):
            raise ValueError("Invalid position")
        cells = hx + ho
        if (turn not in (0, 1)
                or any(type(c) is not int or not 0 <= c < 9 for c in cells)
                or len(set(cells)) != len(cells)
                or len(hx) > MAX_PIECES or len(ho) > MAX_PIECES):
            raise ValueError("Invalid position")
        game = cls()
        game.history = (hx, ho)
        game.turn = turn
        for seat, hist in enumerate(game.history):
            for c in hist:
                game.board[c] = seat
        for seat in (0, 1):
            line = game._winning_line(seat)
            if line:
                game.winner, game.win_line = seat, line
        if game.winner is None and len(game.history[turn]) == MAX_PIECES:
            raise ValueError("Invalid position")  # the mover's oldest should already be gone
        return game

    def new_round(self):
        self.board = [None] * 9          # None, 0 (X) or 1 (O)
        self.history = ([], [])          # per seat, oldest cell first
        self.turn = self.first
        self.winner = None
        self.win_line = None
        self.rematch_votes = set()

    def doomed(self):
        """The waiting player's oldest piece, which vanishes when their turn starts."""
        if self.winner is not None:
            return None
        hist = self.history[1 - self.turn]
        return hist[0] if len(hist) == MAX_PIECES else None

    def play(self, seat, cell):
        """Place a piece. Returns an error string, or None on success."""
        if self.winner is not None:
            return "The round is over"
        if seat != self.turn:
            return "Not your turn"
        if not isinstance(cell, int) or not 0 <= cell < 9:
            return "Invalid square"
        if self.board[cell] is not None:
            return "That square is taken"

        self.board[cell] = seat
        self.history[seat].append(cell)

        line = self._winning_line(seat)
        if line:
            self.winner = seat
            self.win_line = line
        else:
            self.turn = 1 - seat
            hist = self.history[self.turn]
            if len(hist) == MAX_PIECES:
                self.board[hist.pop(0)] = None
        return None

    def _winning_line(self, seat):
        for line in LINES:
            if all(self.board[i] == seat for i in line):
                return list(line)
        return None

    def vote_rematch(self, seat):
        if self.winner is None:
            return
        self.rematch_votes.add(seat)
        if self.rematch_votes >= {0, 1}:
            self.first = 1 - self.first
            self.new_round()

    def to_dict(self):
        return {
            "board": self.board,
            "history": self.history,
            "turn": self.turn,
            "winner": self.winner,
            "winLine": self.win_line,
            "doomed": self.doomed(),
            "rematch": [0 in self.rematch_votes, 1 in self.rematch_votes],
        }