import Pkg; Pkg.add("Random")     # Библиотека для генерации случайных данных
Pkg.add("Formatting") # Библиотека для форматирования вывода

using Random      # Модуль для перемешивания массивов (shuffle!), получения случайных выборок (randperm)
using Formatting  # Функциональность для красивого форматирования вывода (например, format(...))

"""
randomplay(n::Int64, numprisoners::Int64=100)

Выполняет указанное число (n) симуляций ситуации задачи '100 заключенных',
используя СЛУЧАЙНУЮ стратегию поиска. Каждый заключённый открывает 50 случайных ящиков.

Возвращает процент случаев (из n попыток), когда все 100 заключённых нашли свои карточки.
"""
function randomplay(n::Int64, numprisoners::Int64=100)
    pardoned = 0       # Счётчик успешных симуляций
    
    for i in 1:n              # Запускаем цикл по всем симуляциям
        indrawer = collect(1:numprisoners)  # Создаем список карточек внутри ящиков [1, 2, ..., 100]
        shuffle!(indrawer)                  # Перемешиваем карточки (имитируем случайное распределение)

        found_all = true         # Предполагаем, что все найдут свои карточки
        
        for prisoner in 1:numprisoners           # Проходимся по каждому заключённому
            found = false                        # Изначально считаем, что этот заключённый не нашёл карточку

            # Выбираем 50 случайных номеров ящиков:
            for reveal in randperm(numprisoners)[1:div(numprisoners, 2)]  
                
                if indrawer[reveal] == prisoner   # Найдена карточка с нужным номером
                    found = true
                    break                         # Заключённый успешно закончил поиск
                end
            end
            
            if !found                          # Если текущий заключённый НЕ нашёл, то ВСЯ группа проиграла
                found_all = false
                break                            # Больше играть нет смысла
            end
        end

        if found_all                           # Если все справились, увеличиваем счётчик побед
            pardoned += 1
        end
    end

    return 100.0 * pardoned / n                 # Преобразовываем долю в процент
end

"""
optimalplay(n::Int64, numprisoners::Int64=100)

Выполняет указанное число (n) симуляций ситуации задачи '100 заключенных',
используя ОПТИМАЛЬНУЮ стратегию: каждый заключённый начинает с ящика своего номера и продолжает двигаться 
по последовательности, где следующий номер берётся из найденной карточки.

Возвращает процент случаев (из n попыток), когда все 100 заключённых нашли свои карточки.
"""
function optimalplay(n::Int64, numprisoners::Int64=100)
    pardoned = 0          # Счетчик успешных игр  

    for i in 1:n
        indrawer = collect(1:numprisoners)  # Инициализируем массив с номерами карточек
        shuffle!(indrawer)                   # Раскладываем их случаем образом

        found_all = true                     # Исходное допущение: все успешно
        
        for prisoner in 1:numprisoners        # Перебор заключённых
            reveal = prisoner                 # Стартовый шаг: открываем ящик с номером самого заключенного
            found = false                     

            # Открываем до 50 коробок
            for j in 1:div(numprisoners, 2)
                card = indrawer[reveal]         # Смотрим содержимое текущего ящика
                
                if card == prisoner             # Если там лежит искомая карточка – успех!
                    found = true                
                    break
                else
                    reveal = card               # Переходим к ящику с тем номером, который мы только что увидели
                end
            end

            if !found                           # Если кто-то провалился – вся группа теряет
                found_all = false
                break
            end
        end

        if found_all                            # Если никто не ошибся – группа прошла проверку
            pardoned += 1
        end
    end

    return 100.0 * pardoned  / n                 # Процент успешных игр
end

const N = 100_000                              # Число повторений моделирования (можно изменять)

println("Simulation count: $N")               # Сообщение о количестве симуляций
println("Random play wins: ", 
        format(randomplay(N), precision=3),    # Результат случайной стратегии с форматированным выводом
        "% of simulations.")                   
println("Optimal play wins: ", 
        format(optimalplay(N), precision=3),   # Результат оптимальной стратегии
        "% of simulations.")