import Pkg; Pkg.add("Random")     # 用于生成随机数据的库
Pkg.add("Formatting") # 用于格式化输出的库

using Random      # 用于洗牌数组的模块（shuffle！），获得随机样本（randperm）
using Formatting  # 漂亮的输出格式的功能（例如，格式（。..))

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

Выполняет указанное число (n) симуляций ситуации задачи '100名囚犯',
采用随机搜索策略。 每个囚犯打开50个随机盒子。

返回所有100名囚犯发现他们的卡片时（n次尝试中）的百分比。
"""
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名囚犯',
使用最优策略：每个囚犯从一个自己数量的盒子开始，并继续移动 
根据从找到的卡片中取出下一个数字的顺序。

返回所有100名囚犯发现他们的卡片时（n次尝试中）的百分比。
"""
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.")