hackerrank knights on a chessboard

knitsonboard.py

""" we are the knits of the round table ... """

from typing import Tuple


class ChessBoard:
    """
    simple hackerrank style chessboard game with mulitple knights

    - approach use Sprague Grundy Theorem to determine the winner of a
    simple game
    """

    N = 15
    MOVES = [(-2, 1), (-2, -1), (1, -2), (-1, -2)]

    def __init__(self, knights: list[Tuple[int, int]]) -> None:
        assert all(
            [ChessBoard.is_valid(knight) for knight in knights]
        ), "Invalid knight position"
        self.knights = knights
        self.grundy = [
            [-1 for _ in range(ChessBoard.N + 1)] for _ in range(ChessBoard.N + 1)
        ]
        # precompute grundy table
        for i in range(1, ChessBoard.N + 1):
            for j in range(1, ChessBoard.N + 1):
                self.calculate_grundy((i, j))

    def calculate_grundy(self, position: Tuple[int, int]) -> int:
        if not ChessBoard.is_valid(position):
            return 0

        x, y = position
        if self.grundy[x][y] != -1:
            return self.grundy[x][y]

        s = set()
        for move in self.MOVES:
            s.add(self.calculate_grundy((position[0] + move[0], position[1] + move[1])))

        self.grundy[x][y] = ChessBoard.calculate_mex(s)
        return self.grundy[x][y]

    def determine_winner(self) -> str:
        xor_sum = 0
        for kpos in self.knights:
            g = self.calculate_grundy(kpos)
            xor_sum ^= g
        return "First" if xor_sum != 0 else "Second"

    @staticmethod
    def is_valid(position: Tuple[int, int]) -> int:
        """is a valid point"""
        x, y = position
        return 0 < x and x <= ChessBoard.N and 0 < y and y <= ChessBoard.N

    @staticmethod
    def calculate_mex(s: set) -> int:
        """calculate the minimum excludant of set s"""
        mex = 0
        while mex in s:
            mex += 1
        return mex


if __name__ == "__main__":
    knights = [(1, 1), (1, 3), (1, 4), (1, 1)]
    board = ChessBoard(knights)
    print(board.determine_winner())