gistfile1.txt

# boxes are numbered from 1 to 100 (hence all the +1...)

import random

prisoners=24
attempts=prisoners//2

DEBUG = True


def debug(*msg):
    if DEBUG:
        print(*msg)


swap_boxes = False

def loop_stats_with_swap(orig_papers):

    loops = []
    for p in range(prisoners):

        papers = orig_papers.copy()

        debug(f"### Prisoner {p+1}")
        debug("papers", papers)

        curr_loop = []
        curr_box = p+1

        # swap with tmp
        tmp = papers[curr_box - 1]
        print(f"in my box [{curr_box}] I found", tmp)

        swap_with_zero = True
        if swap_with_zero:
            other = prisoners
        else:
            other = tmp

        print(f"in the other box [{other}] there is {papers[other - 1]}")
        print(f"let's put {papers[other - 1]} in my box and {tmp} in box[{other - 1}]")
        papers[curr_box - 1] = papers[other - 1]
        papers[other - 1] = tmp
        print("post swap", papers)

        debug(f"stats: starting at [{curr_box}]")
        while True:
            #print("papers", papers)
            curr_paper = papers[curr_box-1]
            debug(f"stats: Opening box [{curr_box}] with value {curr_paper}")
            if curr_paper < 0:
                if not curr_loop:
                    debug("stats: already done, skip")
                    break
                debug("Closed loop at:", curr_paper, orig_papers[curr_box-1])
                debug("Closed loop at length:", len(curr_loop))
                loops.append(curr_loop)
                break

            #debug(f"stats: Moving to box [{curr_paper}]")
            papers[curr_box - 1] = -papers[curr_box - 1]    #mark as done
            curr_loop.append(curr_paper)
            curr_box = curr_paper

    max_loop = max([len(l) for l in loops])
    debug("loops", loops)
    return loops, max_loop

def loop_stats(orig_papers):

    papers = orig_papers.copy()

    loops = []
    for p in range(prisoners):
        curr_loop = []
        curr_box = p+1

        debug(f"stats: starting at [{curr_box}]")
        while True:
            #print("papers", papers)
            curr_paper = papers[curr_box-1]
            debug(f"stats: Opening box [{curr_box}] with value {curr_paper}")
            if curr_paper < 0:
                if not curr_loop:
                    debug("stats: already done, skip")
                    break
                debug("Closed loop at:", curr_paper, orig_papers[curr_box-1])
                debug("Closed loop at length:", len(curr_loop))
                loops.append(curr_loop)
                break

            #debug(f"stats: Moving to box [{curr_paper}]")
            papers[curr_box - 1] = -papers[curr_box - 1]    #mark as done
            curr_loop.append(curr_paper)
            curr_box = curr_paper
    max_loop = max([len(l) for l in loops])
    debug("loops", loops)
    return loops, max_loop

def gioco(my_number):

    curr_box = my_number
    for i in range(1, attempts+1):
        debug(f"{i}: Opening box [{curr_box}]")
        curr_paper = papers[curr_box-1]
        debug(f"{i}: Paper says {curr_paper}")
        if curr_paper == my_number:
            debug(f"{i}: ### Found {curr_paper} at [{curr_box}], my_number: {my_number}")
            return True
        curr_box = curr_paper

    debug("### Failed", curr_box, curr_paper, my_number)
    return False



if __name__ == '__main__':

    RUN_GAME = False

    random.seed(12345)

    loops_max_len = []
    loops_count = []
    all_loops = []

    true_attempts = attempts
    if swap_boxes:
        true_attempts = attempts - 1

    runs = 100
    num_successes = 0
    num_successes_from_stats = 0
    for r in range(runs):

        debug(r, "### Start")

        if r % 1000 == 0:
            print(r, "### Running...")

        papers = list(range(1, prisoners+1))
        random.shuffle(papers)
        debug("papers", papers)

        loops, max_loop = loop_stats(papers)
        print("max loop", max_loop)

        loops_max_len.append(max_loop)
        loops_count.append(len(loops))
        all_loops.extend(loops)

        if max_loop <= true_attempts:
            num_successes_from_stats += 1

        if RUN_GAME:
            total_success = 0
            for p in range(1, prisoners+1):
                debug("Run game:", p)
                found = gioco(p)
                if found:
                    total_success += 1

            print("found, total_success", found, total_success)

            print("max_loop, attempts", max_loop, true_attempts)
            if total_success == prisoners:
                assert max_loop <= true_attempts
                num_successes += 1
            else:
                assert max_loop > true_attempts

            print(r, "### End", total_success == prisoners)

    print("num_successes_from_stats", num_successes_from_stats)
    if RUN_GAME:
        print("num_successes", num_successes)
        assert num_successes == num_successes_from_stats

    from matplotlib import pyplot as plt
    import numpy as np

    print("Average loops_max_len", np.mean(loops_max_len))
    above_max = len([l for l in all_loops if len(l) > true_attempts])
    print("Loops above_max", above_max)

    print(sorted(np.unique(loops_max_len)))

    marks = np.array(loops_max_len)
    fig, axis = plt.subplots(figsize=(20, 10))
    axis.hist(marks, bins=range(105), rwidth=0.8)
    #plt.show()