Last active
August 4, 2022 23:07
-
-
Save bhatiaabhinav/15da3a947310cfdbdb62971627de1b4a to your computer and use it in GitHub Desktop.
Julia implementation of 100-prisoners cycle-following strategy.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.