Julia implementation of 100-prisoners cycle-following strategy.

100-prisoners.jl

"""
Decription: A simulation of the cycle-following strategy for the 100-prisoners problem (https://en.wikipedia.org/wiki/100_prisoners_problem), which provides a survival probability of more than 30%.
Author: Abhinav Bhatia <abhinav.bhatia.me@gmail.com>
"""

using Random
using Base.Threads: @threads, Atomic, atomic_add!

"""returns whether successful or not"""
function simulate_cycle_strategy_for_all_prisoners(game::Vector{Int})::Bool
    num_cards::Int = length(game)
    @assert iseven(num_cards)
    function simulate_cycle_strategy_for_one_prisoner(prisoner_id::Int)::Bool
        max_cards::Int = num_cards ÷ 2
        num_cards_lifted::Int = 0
        next_card_to_explore::Int = prisoner_id
        while num_cards_lifted < max_cards
            card_result = @inbounds game[next_card_to_explore]
            if card_result == prisoner_id
                return true
            end
            num_cards_lifted += 1
            next_card_to_explore = card_result
        end
        return false
    end
    for prisoner_id in 1:num_cards
        if simulate_cycle_strategy_for_one_prisoner(prisoner_id) == false
            return false
        end
    end
    return true
end

"""Returns empirical success rate after `num_trials` trials."""
function run_trials(num_cards::Int, num_trials::Int=1000000)::Float64
    num_successes = Atomic{Int}(0)
    @threads for trial_number in 1:num_trials
        game::Vector{Int} = shuffle(1:num_cards)
        successful = simulate_cycle_strategy_for_all_prisoners(game)
        if successful atomic_add!(num_successes, 1) end
    end
    return num_successes[] / num_trials
end


const NUM_CARDS = 100
success_rate = run_trials(NUM_CARDS)
println("Empirical success rate for $(NUM_CARDS)-prisoners problem with the cycle-following strategy = ", success_rate)

To avail multithreading, run the code as julia -t 8 100-prisoners.jl. Replace 8 with whatever number of threads you want.
On my machine (an i5-11300H), simulating 1 million trials takes <1s with 8 threads.