import Pkg; Pkg.add("Random")     # Library for generating random data
Pkg.add("Formatting") # Library for formatting output

using Random      # A module for shuffling arrays (shuffle!), obtaining random samples (randperm)
using Formatting  # Functionality for beautiful output formatting (for example, format(...))

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

Выполняет указанное число (n) симуляций ситуации задачи '100 prisoners',
using a RANDOM search strategy. Each prisoner opens 50 random boxes.

Returns the percentage of cases (out of n attempts) when all 100 prisoners found their cards.
"""
function randomplay(n::Int64, numprisoners::Int64=100)
    pardoned = 0       # The counter of successful simulations
    
    for i in 1:n              # Running a cycle for all simulations
        indrawer = collect(1:numprisoners)  # Creating a list of cards inside the boxes [1, 2, ..., 100]
        shuffle!(indrawer)                  # Shuffle the cards (simulate a random distribution)

        found_all = true         # We assume that everyone will find their cards.
        
        for prisoner in 1:numprisoners           # We go through each prisoner
            found = false                        # Initially, we believe that this prisoner did not find the card.

            # We select 50 random mailbox numbers:
            for reveal in randperm(numprisoners)[1:div(numprisoners, 2)]  
                
                if indrawer[reveal] == prisoner   # A card with the required number was found
                    found = true
                    break                         # The prisoner has successfully completed the search
                end
            end
            
            if !found                          # If the current prisoner did NOT find it, then the WHOLE group lost.
                found_all = false
                break                            # There's no point playing anymore
            end
        end

        if found_all                           # If everyone has done well, we increase the victory counter.
            pardoned += 1
        end
    end

    return 100.0 * pardoned / n                 # Converting a share to a percentage
end

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

Выполняет указанное число (n) симуляций ситуации задачи '100 prisoners',
using an OPTIMAL strategy: each prisoner starts with a box of his own number and continues to move 
according to the sequence where the next number is taken from the found card.

Returns the percentage of cases (out of n attempts) when all 100 prisoners found their cards.
"""
function optimalplay(n::Int64, numprisoners::Int64=100)
    pardoned = 0          # Successful Game Counter

    for i in 1:n
        indrawer = collect(1:numprisoners)  # Initialize the array with the card numbers
        shuffle!(indrawer)                   # We lay them out randomly as follows

        found_all = true                     # Initial assumption: everything is successful
        
        for prisoner in 1:numprisoners        # Busting prisoners
            reveal = prisoner                 # Starting step: open the box with the prisoner's number.
            found = false                     

            # We open up to 50 boxes
            for j in 1:div(numprisoners, 2)
                card = indrawer[reveal]         # We are looking at the contents of the current mailbox
                
                if card == prisoner             # If the card you are looking for is there, success!
                    found = true                
                    break
                else
                    reveal = card               # Let's move on to the mailbox with the number we just saw.
                end
            end

            if !found                           # If someone fails, the whole group loses
                found_all = false
                break
            end
        end

        if found_all                            # If no one made a mistake, the group was verified.
            pardoned += 1
        end
    end

    return 100.0 * pardoned  / n                 # Percentage of successful games
end

const N = 100_000                              # The number of repetitions of the simulation (can be changed)

println("Simulation count: $N")               # Notification of the number of simulations
println("Random play wins: ", 
        format(randomplay(N), precision=3),    # The result of a random strategy with formatted output
        "% of simulations.")                   
println("Optimal play wins: ", 
        format(optimalplay(N), precision=3),   # The result of an optimal strategy
        "% of simulations.")