the 100 prisoners problem

cycle.py

import itertools
import random

def cycle_len(boxes, num):
    steps = 1
    position = num
    while boxes[position] != num:
        steps += 1
        position = boxes[position]
    return steps

def works(boxes, num):
    return cycle_len(boxes, num) <= len(boxes) // 2

def works_all(boxes):
    for num in range(len(boxes)):
        if not works(boxes, num):
            return False
    return True

def random_perm(n):
    perm = list(range(n))
    random.shuffle(perm)
    return perm

def ratio(n):
    good = 0
    bad = 0
    for perm in itertools.permutations(range(n)):
        if works_all(perm):
            good += 1
        else:
            bad += 1
    print("good:", good)
    print("bad:", bad)
    print("ratio:", good / (good + bad))

def ratio_rand(n, samples):
    good = 0
    bad = 0
    for _ in range(samples):
        perm = random_perm(n)
        if works_all(perm):
            good += 1
        else:
            bad += 1
    print("good:", good)
    print("bad:", bad)
    print("ratio:", good / (good + bad))

ratio_rand(1000, 10000)