prisoners_and_boxes_en.py

import random

wins_random_search = 0
wins_permutation_search = 0
prisoners = 100 #num of prisoners
allowed_boxes = prisoners // 2 #how many boxes each of them checks
N = 10000 #number of experiments to run

for _ in range(N):
    numbers_in_boxes = [i for i in range(prisoners)]
    random.shuffle(numbers_in_boxes) #randomly put numbers inside boxes
    all_found_numbers_naive = True
    all_found_numbers_smart = True
    for i in range(prisoners):
        #Let's try random search first for each prisoner to see the chances
        search_positions = random.sample(range(prisoners),allowed_boxes)
        all_found_numbers_naive = False
        for j in search_positions:
            if numbers_in_boxes[j] == i:
                all_found_numbers_naive = True
        if not all_found_numbers_naive:
            break
    if all_found_numbers_naive:
        wins_random_search += 1
    for i in range(prisoners):
        #And now let's try a more clever approach (based on permutations)
        all_found_numbers_smart = False
        cur_position = i
        for _ in range(allowed_boxes):
            if numbers_in_boxes[cur_position] == i:
                all_found_numbers_smart = True
            cur_position = numbers_in_boxes[cur_position]
        if not all_found_numbers_smart:
            break
    if all_found_numbers_smart:
        wins_permutation_search += 1
#Final results:
print('Wins with random search:', wins_random_search, '(', 100 * wins_random_search/ N, "%)")    
print('Wins with permutation-based search:', wins_permutation_search, '(', 100 * wins_permutation_search/ N, "%)") 

#------------------Example output:------------------
#Wins with random search: 0 ( 0.0 %)
#Wins with permutation-based search: 3155 ( 31.55 %)
#---------------------------------------------------