# BSD 3-Clause License
#
# Copyright 2025 RJE-Productions and E.R. van Veldhoven
#
# Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
# following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
#    disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
#    following disclaimer in the documentation and/or other materials provided with the distribution.
#
# 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
#    products derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
# INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
# USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

from enum import Enum

# We define a board of 10 by 10 fields as shown in the figure below. This board consists of an actual 8 by 8
# chessboard, surrounded by an outer ring of 'invalid' fields. The black fields of the chessboard are not used.
# In the figure, both the 'invalid' and the 'unused' fields have their numbers surrounded by brackets.
#
#   +----+----+----+----+----+----+----+----+----+----+
#   | (0)| (1)| (2)| (3)| (4)| (5)| (6)| (7)| (8)| (9)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(10)| 11 |(12)| 13 |(14)| 15 |(16)| 17 |(18)|(19)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(20)|(21)| 22 |(23)| 24 |(25)| 26 |(27)| 28 |(29)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(30)| 31 |(32)| 33 |(34)| 35 |(36)| 37 |(38)|(39)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(40)|(41)| 42 |(43)| 44 |(45)| 46 |(47)| 48 |(49)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(50)| 51 |(52)| 53 |(54)| 55 |(56)| 57 |(58)|(59)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(60)|(61)| 62 |(63)| 64 |(65)| 66 |(67)| 68 |(69)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(70)| 71 |(72)| 73 |(74)| 75 |(76)| 77 |(78)|(79)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(80)|(81)| 82 |(83)| 84 |(85)| 86 |(87)| 88 |(89)|
#   +----+----+----+----+----+----+----+----+----+----+
#   |(90)|(91)|(92)|(93)|(94)|(95)|(96)|(97)|(98)|(99)|
#   +----+----+----+----+----+----+----+----+----+----+
#
# The figure below only shows the numbers of the 32 used fields:
#
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 11 |    | 13 |    | 15 |    | 17 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 22 |    | 24 |    | 26 |    | 28 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 31 |    | 33 |    | 35 |    | 37 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 42 |    | 44 |    | 46 |    | 48 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 51 |    | 53 |    | 55 |    | 57 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 62 |    | 64 |    | 66 |    | 68 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 71 |    | 73 |    | 75 |    | 77 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 82 |    | 84 |    | 86 |    | 88 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#
# White starts on the fields 11, 13, 15, and 17. We store the positions of the white pieces in the 'whitePositions'
# array. Black starts on field 84, and we store its position in the 'blackPosition' variable.
#
# White can make the following two moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
#
# Black can make the following four moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
# 3. one field diagonally up to the left: this corresponds to a decrease of the field number by 11.
# 4. one field diagonally up to the right: this corresponds to a decrease of the field number by 9.
#
# A move is only valid if there is not already a piece on the destination field and the destination field is not on
# the outer ring. A field lies on the outer ring if any of the following conditions hold:
# - the field number is less than 10;
# - the field number is at least 90;
# - the field number modulo 10 equals 0;
# - the field number modulo 10 equals 9.
#
# We store the result for each game situation in the variable "outcomes". This variable contains the outcome for
# each combination (player to move, position of black, positions of white pieces 1 to 4). We map the 32 possible
# field numbers to the range [0..31] as follows:
#
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |  0 |    |  1 |    |  2 |    |  3 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |  4 |    |  5 |    |  6 |    |  7 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |  8 |    |  9 |    | 10 |    | 11 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 12 |    | 13 |    | 14 |    | 15 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 16 |    | 17 |    | 18 |    | 19 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 20 |    | 21 |    | 22 |    | 23 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    | 24 |    | 25 |    | 26 |    | 27 |    |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    | 28 |    | 29 |    | 30 |    | 31 |    |
#   +----+----+----+----+----+----+----+----+----+----+
#   |    |    |    |    |    |    |    |    |    |    |
#   +----+----+----+----+----+----+----+----+----+----+


NR_OF_POSITIONS = 32  # There are 32 fields on which the pieces can be positioned.
POSSIBLE_MOVES = [9, 11, -11, -9]

# Define a mapping of the 32 usable field numbers in the range [0..99] to the range [0..31].
MAPPING = [
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, -1, 2, -1,
    3, -1, -1, -1, -1, 4, -1, 5, -1, 6, -1, 7, -1, -1, 8, -1, 9, -1,
    10, -1, 11, -1, -1, -1, -1, 12, -1, 13, -1, 14, -1, 15, -1, -1,
    16, -1, 17, -1, 18, -1, 19, -1, -1, -1, -1, 20, -1, 21, -1, 22, -1,
    23, -1, -1, 24, -1, 25, -1, 26, -1, 27, -1, -1, -1, -1, 28, -1,
    29, -1, 30, -1, 31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
]


class Player(Enum):
    BLACK = 0
    WHITE = 1


class Outcome(Enum):
    NOT_CALCULATED = 0
    BLACK_CAN_ALWAYS_WIN = 1
    WHITE_CAN_ALWAYS_WIN = 2
    BEING_CALCULATED = 3


class CatAndMouseGame:
    def __init__(self):
        # 'outcomes' corresponds to C_white(player whose move it is, game situation)
        # and C_black(player whose move it is, game situation) in the puzzle explanation.
        self.outcomes = [[[[[[Outcome.NOT_CALCULATED for _ in range(NR_OF_POSITIONS)]
                            for _ in range(NR_OF_POSITIONS)]
                            for _ in range(NR_OF_POSITIONS)]
                           for _ in range(NR_OF_POSITIONS)]
                          for _ in range(NR_OF_POSITIONS)]
                         for _ in range(2)]

        self.black_position = 0  # Initialize with a default value
        self.white_positions = [0] * 4
        self.total = 0
        self.initialize_piece_positions()

    def initialize_piece_positions(self):
        self.black_position = 84
        self.white_positions = [11, 13, 15, 17]

    def show_progress(self):
        self.total += 1
        if self.total % 10000 == 0:
            print(self.total, end='\r')

    def is_usable_field(self, field_number):
        if field_number < 10 or field_number >= 90 or field_number % 10 == 0 or field_number % 10 == 9:
            # The field is on the outer ring
            return False
        else:
            # Check if in this row the usable fields have odd numbers (this holds for rows 2, 4, 6, and 8)
            odd_row = (field_number // 10) % 2 == 1
            return (odd_row and field_number % 2 == 1) or (not odd_row and field_number % 2 == 0)

    def is_move_allowed(self, piece_position: int, move: int) -> bool:
        new_piece_position = piece_position + move

        if not self.is_usable_field(new_piece_position):
            # A move outside the chessboard is not allowed
            return False

        if new_piece_position == self.black_position:
            # Black is on the new field, therefore the move is not allowed
            return False

        for white in range(4):
            if new_piece_position == self.white_positions[white]:
                # A white piece is on the new field, therefore the move is not allowed
                return False

        return True

    def black_has_won(self) -> bool:
        return self.black_position in [11, 13, 15, 17]

    def white_has_won(self) -> bool:
        # White wins if it blocks black in such a way that black cannot make any move anymore
        return not (self.is_move_allowed(self.black_position, POSSIBLE_MOVES[0]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[1]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[2]) or
                    self.is_move_allowed(self.black_position, POSSIBLE_MOVES[3]))

    def white_can_make_a_move(self) -> bool:
        return (self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[1]) or
                self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[0]) or
                self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[1]))

    def get_outcome(self, player: Player, black_position: int, white_positions: list) -> Outcome:
        # Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
        sorted_white_positions = sorted(white_positions)
        return self.outcomes[player.value][
            MAPPING[black_position]][
            MAPPING[sorted_white_positions[0]]][
            MAPPING[sorted_white_positions[1]]][
            MAPPING[sorted_white_positions[2]]][
            MAPPING[sorted_white_positions[3]]]

    def set_outcome(self, player: Player, black_position: int, white_positions: list, outcome: Outcome):
        # Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
        sorted_white_positions = sorted(white_positions)
        self.outcomes[player.value][
            MAPPING[black_position]][
            MAPPING[sorted_white_positions[0]]][
            MAPPING[sorted_white_positions[1]]][
            MAPPING[sorted_white_positions[2]]][
            MAPPING[sorted_white_positions[3]]] = outcome

    def white_move(self):
        self.show_progress()
        white_can_win = False
        black_can_win = False

        if self.white_can_make_a_move():
            for piece in range(4):
                for move in range(2):
                    if self.is_move_allowed(self.white_positions[piece], POSSIBLE_MOVES[move]):
                        # Perform the white move
                        tmp_position = self.white_positions[piece]
                        self.white_positions[piece] += POSSIBLE_MOVES[move]

                        # Now black is to move
                        outcome = self.get_outcome(
                            Player.BLACK, self.black_position, self.white_positions)

                        if outcome == Outcome.NOT_CALCULATED:
                            # This game situation has not been calculated yet
                            if self.white_has_won():
                                self.set_outcome(Player.BLACK, self.black_position,
                                                 self.white_positions, Outcome.WHITE_CAN_ALWAYS_WIN)
                            else:
                                self.black_move()

                            outcome = self.get_outcome(
                                Player.BLACK, self.black_position, self.white_positions)

                        if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                            white_can_win = True
                        elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                            black_can_win = True

                        # Restore the game situation
                        self.white_positions[piece] = tmp_position
        else:
            # If white cannot move, it must skip a turn
            # Now black is to move
            outcome = self.get_outcome(
                Player.BLACK, self.black_position, self.white_positions)

            if outcome == Outcome.NOT_CALCULATED:
                # Prevent endless loops
                self.set_outcome(Player.BLACK, self.black_position,
                                 self.white_positions, Outcome.BEING_CALCULATED)
                self.black_move()
                outcome = self.get_outcome(
                    Player.BLACK, self.black_position, self.white_positions)

            if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                white_can_win = True
            elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                black_can_win = True

        if white_can_win:
            self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
                             Outcome.WHITE_CAN_ALWAYS_WIN)
        elif black_can_win:
            self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
                             Outcome.BLACK_CAN_ALWAYS_WIN)

    def black_move(self):
        self.show_progress()
        black_can_win = False
        white_can_win = False

        for move in range(4):
            if self.is_move_allowed(self.black_position, POSSIBLE_MOVES[move]):
                # Perform the black move
                tmp_position = self.black_position
                self.black_position += POSSIBLE_MOVES[move]

                # Now white is to move
                outcome = self.get_outcome(
                    Player.WHITE, self.black_position, self.white_positions)

                if outcome == Outcome.NOT_CALCULATED:
                    # This game situation has not been calculated yet
                    if self.black_has_won():
                        self.set_outcome(Player.WHITE, self.black_position,
                                         self.white_positions, Outcome.BLACK_CAN_ALWAYS_WIN)
                    else:
                        self.white_move()

                    outcome = self.get_outcome(
                        Player.WHITE, self.black_position, self.white_positions)

                if outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
                    black_can_win = True
                elif outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
                    white_can_win = True

                # Restore the game situation
                self.black_position = tmp_position

        if black_can_win:
            self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
                             Outcome.BLACK_CAN_ALWAYS_WIN)
        elif white_can_win:
            self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
                             Outcome.WHITE_CAN_ALWAYS_WIN)


print("Creating game object...")
game = CatAndMouseGame()

print("Running game...")
game.black_move()

print(game.total)
game.initialize_piece_positions()
print(game.get_outcome(Player.BLACK, game.black_position, game.white_positions).name)