import random
import time
import math
from typing import List, Tuple

class Player:
    """
    Базовый класс игрока
    """
    def __init__(self, name: str):
        self.name = name

    def make_move(self, current_number: int, target_number: int) -> int:
        """
        Метод, который должен быть переопределен в подклассах
        для реализации стратегии игрока
        """
        pass


class HumanPlayer(Player):
    """
    Класс, представляющий игрока-человека
    """
    def make_move(self, current_number: int, target_number: int) -> int:
        # Получаем все возможные ходы
        possible_moves = self._get_possible_moves(current_number)

        # Выводим информацию о текущем состоянии игры
        print(f"\nТекущее число на доске: {current_number}")
        print(f"Цель: достигнуть {target_number} или больше")
        print(f"Возможные ходы: {', '.join(str(move) for move in possible_moves)}")

        # Запрашиваем ход у пользователя
        while True:
            try:
                choice = int(input(f"{self.name}, выберите новое число: "))
                if choice in possible_moves:
                    return choice
                else:
                    print("Недопустимый ход! Выберите число из списка возможных ходов.")
            except ValueError:
                print("Введите корректное число!")

    def _get_possible_moves(self, current_number: int) -> List[int]:
        """
        Вычисляет все возможные ходы для текущего числа на доске
        """
        moves = []
        # Находим все делители текущего числа
        for i in range(1, current_number + 1):
            if current_number % i == 0:
                moves.append(current_number + i)
        return moves


class ComputerPlayer(Player):
    """
    Класс, представляющий компьютерного игрока
    """
    def __init__(self, name: str, difficulty: str = "medium"):
        super().__init__(name)
        self.difficulty = difficulty  # Уровень сложности: "easy", "medium", "hard"

    def make_move(self, current_number: int, target_number: int) -> int:
        # Получаем все возможные ходы
        possible_moves = self._get_possible_moves(current_number)

        print(f"\n{self.name} думает...")
        time.sleep(1)  # Добавляем задержку для имитации "размышления"

        # В зависимости от уровня сложности выбираем стратегию
        if self.difficulty == "easy":
            # Простой уровень: выбор случайного хода
            choice = random.choice(possible_moves)
        elif self.difficulty == "medium":
            # Средний уровень: выбор между случайным и оптимальным ходом
            if random.random() < 0.5:
                choice = self._get_best_move(current_number, possible_moves, target_number)
            else:
                choice = random.choice(possible_moves)
        else:  # hard
            # Сложный уровень: всегда выбирает наилучший ход
            choice = self._get_best_move(current_number, possible_moves, target_number)

        print(f"{self.name} выбирает число: {choice}")
        return choice

    def _get_possible_moves(self, current_number: int) -> List[int]:
        """
        Вычисляет все возможные ходы для текущего числа на доске
        """
        moves = []
        # Находим все делители текущего числа
        for i in range(1, current_number + 1):
            if current_number % i == 0:
                moves.append(current_number + i)
        return moves

    def _get_best_move(self, current_number: int, possible_moves: List[int], target_number: int) -> int:
        """
        Определяет наилучший ход с использованием стратегии
        """
        # Если можем выиграть - выигрываем
        winning_moves = [move for move in possible_moves if move >= target_number]
        if winning_moves:
            return min(winning_moves)  # Выбираем наименьшее выигрышное число

        # Ищем выигрышные позиции для нас
        for move in possible_moves:
            if self._is_winning_position(move, target_number):
                return move

        # Если нет выигрышной стратегии, выбираем ход, дающий максимальное число
        return max(possible_moves)

    def _is_winning_position(self, position: int, target_number: int) -> bool:
        """
        Определяет, является ли позиция выигрышной с помощью анализа игры
        """
        # Если позиция уже достигла или превысила целевое число - это выигрыш
        if position >= target_number:
            return True

        # Находим все возможные ходы противника из этой позиции
        opponent_moves = []
        for i in range(1, position + 1):
            if position % i == 0:
                opponent_moves.append(position + i)

        # Если хотя бы один ход противника ведёт к проигрышной для нас позиции,
        # то текущая позиция не является выигрышной
        for opponent_move in opponent_moves:
            if not self._can_win_from_position(opponent_move, target_number):
                return False

        # Если все ходы противника ведут к выигрышной для нас позиции,
        # то текущая позиция является выигрышной
        return True

    def _can_win_from_position(self, position: int, target_number: int) -> bool:
        """
        Проверяет, можно ли выиграть из данной позиции
        Это упрощенная проверка для ограничения глубины анализа
        """
        # Если позиция уже достигла или превысила целевое число - это выигрыш
        if position >= target_number:
            return True

        # Рассматриваем только простые случаи для ограничения вычислительной сложности
        # Проверяем, есть ли делитель, который позволит достичь целевое число за один ход
        for i in range(1, position + 1):
            if position % i == 0 and position + i >= target_number:
                return True

        return False


class Game:
    """
    Класс, представляющий игру Strat30
    """
    def __init__(self, start_number: int = 10, target_number: int = 60):
        self.start_number = start_number
        self.target_number = target_number
        self.current_number = start_number
        self.players = []
        self.current_player_index = 0

    def add_player(self, player: Player):
        """
        Добавляет игрока в игру
        """
        self.players.append(player)

    def start_game(self):
        """
        Запускает игру
        """
        print(f"\n=== Начало игры Strat30 ===")
        print(f"Начальное число: {self.start_number}")
        print(f"Цель: достигнуть {self.target_number} или больше")
        print(f"Игроки: {', '.join(player.name for player in self.players)}")

        # Основной игровой цикл
        while True:
            current_player = self.players[self.current_player_index]

            # Игрок делает ход
            new_number = current_player.make_move(self.current_number, self.target_number)

            # Обновляем число на доске
            self.current_number = new_number

            # Проверяем условие победы
            if self.current_number >= self.target_number:
                print(f"\n=== {current_player.name} победил! ===")
                print(f"Финальное число на доске: {self.current_number}")
                break

            # Переходим к следующему игроку
            self.current_player_index = (self.current_player_index + 1) % len(self.players)


def get_game_setup() -> Tuple[int, int, list]:
    """
    Функция для настройки параметров игры через консольный интерфейс
    """
    print("\n=== Настройка игры Strat30 ===")

    # Запрашиваем начальное число
    while True:
        try:
            start_number = int(input("Введите начальное число n (рекомендуется 10-30): "))
            if start_number > 0:
                break
            else:
                print("Число должно быть положительным!")
        except ValueError:
            print("Введите корректное число!")

    # Запрашиваем целевое число
    while True:
        try:
            target_number = int(input(f"Введите целевое число (рекомендуется не менее {start_number*2}): "))
            if target_number > start_number:
                break
            else:
                print(f"Целевое число должно быть больше начального ({start_number})!")
        except ValueError:
            print("Введите корректное число!")

    # Создаем список игроков
    players = []

    # Запрашиваем количество человек-игроков
    while True:
        try:
            num_human_players = int(input("Введите количество человек-игроков (0-4): "))
            if 0 <= num_human_players <= 4:
                break
            else:
                print("Количество должно быть от 0 до 4!")
        except ValueError:
            print("Введите корректное число!")

    # Создаем человек-игроков
    for i in range(num_human_players):
        name = input(f"Введите имя игрока {i+1}: ")
        if not name:
            name = f"Игрок {i+1}"
        players.append(HumanPlayer(name))

    # Запрашиваем количество компьютерных игроков
    while True:
        try:
            num_computer_players = int(input("Введите количество компьютерных игроков (0-4): "))
            if 0 <= num_computer_players <= 4 and (num_human_players + num_computer_players) > 0:
                break
            else:
                print("Количество должно быть от 0 до 4 и общее количество игроков должно быть не менее 1!")
        except ValueError:
            print("Введите корректное число!")

    # Создаем компьютерных игроков
    for i in range(num_computer_players):
        # Запрашиваем уровень сложности для каждого компьютерного игрока
        while True:
            difficulty = input(f"Выберите уровень сложности для Компьютер {i+1} (easy/medium/hard): ").lower()
            if difficulty in ["easy", "medium", "hard"]:
                break
            else:
                print("Неверный уровень сложности! Выберите один из: easy, medium, hard")

        players.append(ComputerPlayer(f"Компьютер {i+1}", difficulty))

    # Перемешиваем порядок игроков для случайного первого хода
    random.shuffle(players)

    return start_number, target_number, players


def main():
    """
    Основная функция для запуска игры
    """
    print("Добро пожаловать в игру Strat30!")
    print("Правила игры:")
    print("1. Изначально на доске написано число n.")
    print("2. Игрок в свой ход может прибавить к числу на доске любой его натуральный делитель, стереть старое число и записать новое.")
    print("3. Побеждает тот, кто получит после своего хода число, не меньшее заданного целевого числа.")

    # Настраиваем игру
    start_number, target_number, players = get_game_setup()

    # Создаем и настраиваем игру
    game = Game(start_number, target_number)
    for player in players:
        game.add_player(player)

    # Запускаем игру
    game.start_game()

    # Спрашиваем о новой игре
    while True:
        play_again = input("\nХотите сыграть еще раз? (да/нет): ").lower()
        if play_again in ["да", "yes", "y", "д"]:
            # Настраиваем и запускаем новую игру
            start_number, target_number, players = get_game_setup()
            game = Game(start_number, target_number)
            for player in players:
                game.add_player(player)
            game.start_game()
        elif play_again in ["нет", "no", "n", "н"]:
            print("Спасибо за игру! До свидания!")
            break
        else:
            print("Пожалуйста, введите 'да' или 'нет'.")


if __name__ == "__main__":
    main()