100 Prisoners Puzzle - Network Solution Test

prisoners.py

# Prisoner puzzle sim
# Robert Jones, October 2022
# 
# 100 prisoners numbered 1-100
# Room with 100 boxes numbered 1-100
# Each box contains a slip of paper with a number (1-100)
# Each prisoner goes in one at a time and searches 50 boxes
# If they find their number they exit the room, leaving it as they found it
# No communication allowed to the prisoners that have not taken their turn
# Prisoners are allowed to strategize prior to searching
# If every prisoner finds their number, the entire group goes free
# If even one prisoner does not find their number, the entire group is executed
#
# Naive strategy results in p = 0.5^100 (each prisoner randomly looks in 
#   up to 50 boxes looking for their number, so they have a 50% chance of 
#   finding it)
#
# Network strategy says p = 0.31
# This script uses the network strategy - each prisoner starts with the
#   box corresponding to their number.  They look inside and check the slip.
#   If the slip matches their prisoner number then they leave the room,
#   else they go to the box with the label that matches the slip value
#   This continues until they either find their number or they complete
#   50 looks.
# 
# This approach is amazing!  Thanks to the Veritasium Youtube channel.
#   See more on this interesting puzzle at:
#   https://www.youtube.com/watch?v=iSNsgj1OCLA

from random import sample

domain = range(0, 100)

# Dict key=box#, value=slip#
boxes = {}

# Total number of times all 100 prisoners find their number
success_total = 0

# Number of simulations to run
#   10,000 takes about 7 seconds on my circa 2015 Intel i7 @ 4GHz
sim_count = 10000

for sim in range(0, sim_count):

    # Totals for number of prisoners that find (or don't find) their number
    success_prisoner = 0
    fail_prisoner = 0
    
    # Generate random but unique slips to put in each box
    #   random.sample(sequence, k)
    #   sequence: list, tuple, string or set
    #          k: integer value of the length of the sample
    #   Returns k length new list of elements chosen from the sequence
    #
    slips = sample(domain, 100)

    # Place the random slips into the boxes labeled 0-99
    for label in domain:
        boxes[label] = slips[label]

    for prisoner in range(0,100):
        look_count = 0
        look_index = prisoner # starting box to look into
        while boxes[look_index] != prisoner and look_count < 50:
            look_index = boxes[look_index] # this is the next box to look at
            look_count += 1
        if look_count == 50:
            fail_prisoner += 1
        else:
            success_prisoner += 1

    if success_prisoner == 100:
        success_total += 1

print("Success: {}  Fail: {}  ({}%)".format(success_total, sim_count - success_total, 100*success_total/sim_count ))