

The Problem

 100 prisoners are individually numbered 1 to 100
 A room having a cupboard of 100 opaque drawers numbered 1 to 100, that cannot be seen from outside.
 Cards numbered 1 to 100 are placed randomly, one to a drawer, and the drawers all closed; at the start.
 Prisoners start outside the room
 They can decide some strategy before any enter the room.
 Prisoners enter the room one by one, can open a drawer, inspect the card number in the drawer, then close the drawer.
 A prisoner can open no more than 50 drawers.
 A prisoner tries to find his own number.
 A prisoner finding his own number is then held apart from the others.
 If all 100 prisoners find their own numbers then they will all be pardoned. If any don't then all sentences stand. 


The task

 Simulate several thousand instances of the game where the prisoners randomly open drawers
 Simulate several thousand instances of the game where the prisoners use the optimal strategy mentioned in the Wikipedia article, of:
 First opening the drawer whose outside number is his prisoner number.
 If the card within has his number then he succeeds otherwise he opens the drawer with the same number as that of the revealed card. (until he opens his maximum).


Show and compare the computed probabilities of success for the two strategies, here, on this page.




References

 The unbelievable solution to the 100 prisoner puzzle standupmaths (Video).
 wp:100 prisoners problem
 100 Prisoners Escape Puzzle DataGenetics.
 Random permutation statistics#One hundred prisoners on Wikipedia.


100H:
/* PARAMETERS */
DECLARE N$DRAWERS  LITERALLY '100';  /* AMOUNT OF DRAWERS */
DECLARE N$ATTEMPTS LITERALLY '50';   /* ATTEMPTS PER PRISONER */
DECLARE N$SIMS     LITERALLY '2000'; /* N. OF SIMULATIONS TO RUN */ 
DECLARE RAND$SEED  LITERALLY '193';  /* RANDOM SEED */
 
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0, 0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9, S); END PRINT;
 
/* PRINT NUMBER */
PRINT$NUMBER: PROCEDURE (N);
    DECLARE S (6) BYTE INITIAL ('.....$');
    DECLARE (P, N) ADDRESS, C BASED P BYTE;
    P = .S(5);
DIGIT:
    P = P - 1;
    C = N MOD 10 + '0';
    N = N / 10;
    IF N > 0 THEN GO TO DIGIT;
    CALL PRINT(P);
END PRINT$NUMBER;
 
/* RANDOM NUMBER GENERATOR */
RAND$BYTE: PROCEDURE BYTE;
    DECLARE (X, A, B, C) BYTE 
        INITIAL (RAND$SEED, RAND$SEED, RAND$SEED, RAND$SEED);
    X = X+1;
    A = A XOR C XOR X;
    B = B+A;
    C = C+SHR(B,1)+A;
    RETURN C;
END RAND$BYTE;
 
/* GENERATE RANDOM NUMBER FROM 0 TO MAX */
RAND$MAX: PROCEDURE (MAX) BYTE;
    DECLARE (X, R, MAX) BYTE;
    X = 1;
    DO WHILE X < MAX;
        X = SHL(X,1);
    END;
    X = X-1;
    DO WHILE 1;
        R = RAND$BYTE AND X;
        IF R < MAX THEN RETURN R;
    END;
END RAND$MAX;
 
/* PLACE CARDS RANDOMLY IN DRAWERS */
INIT$DRAWERS: PROCEDURE (DRAWERS);
    DECLARE DRAWERS ADDRESS, (D BASED DRAWERS, I, J, K) BYTE;
    DO I=0 TO N$DRAWERS-1;
        D(I) = I;
    END;
    DO I=0 TO N$DRAWERS-1;
        J = I + RAND$MAX(N$DRAWERS-I);
        K = D(I);
        D(I) = D(J);
        D(J) = K;
    END;
END INIT$DRAWERS;
 
/* PRISONER OPENS RANDOM DRAWERS */
RANDOM$STRATEGY: PROCEDURE (DRAWERS, P) BYTE;
    DECLARE DRAWERS ADDRESS, D BASED DRAWERS BYTE;
    DECLARE (P, I, TRIES) BYTE;
 
    /* KEEP TRACK OF WHICH DRAWERS HAVE BEEN OPENED */
    DECLARE OPEN (N$DRAWERS) BYTE;
    DO I=0 TO N$DRAWERS-1;
        OPEN(I) = 0;
    END;
 
    /* OPEN RANDOM DRAWERS */
    TRIES = N$ATTEMPTS;
    DO WHILE TRIES > 0;
        IF NOT OPEN(I := RAND$MAX(N$DRAWERS)) THEN DO;
            /* IF WE FIND OUR NUMBER, SUCCESS */
            IF D(I) = P THEN RETURN 1;
            OPEN(I) = 1;    
            TRIES = TRIES - 1;
        END;
    END;
 
    RETURN 0; /* WE DID NOT FIND OUR NUMBER */
END RANDOM$STRATEGY;
 
/* PRISONER USES OPTIMAL STRATEGY */
OPTIMAL$STRATEGY: PROCEDURE (DRAWERS, P) BYTE;
    DECLARE DRAWERS ADDRESS, D BASED DRAWERS BYTE;
    DECLARE (P, I, TRIES) BYTE;
    TRIES = N$ATTEMPTS;
    I = P;
    DO WHILE TRIES > 0;
        I = D(I); /* OPEN DRAWER W/ CURRENT NUMBER */
        IF I = P THEN RETURN 1; /* DID WE FIND IT? */
        TRIES = TRIES - 1;
    END;
    RETURN 0;
END OPTIMAL$STRATEGY;
 
/* RUN A SIMULATION */
DECLARE RANDOM LITERALLY '0';
DECLARE OPTIMAL LITERALLY '1';
SIMULATE: PROCEDURE (STRAT) BYTE;
    DECLARE (STRAT, P, R) BYTE;
 
    /* PLACE CARDS IN DRAWERS */
    DECLARE DRAWERS (N$DRAWERS) BYTE;
    CALL INIT$DRAWERS(.DRAWERS);
 
    /* TRY EACH PRISONER */
    DO P=0 TO N$DRAWERS-1;
        DO CASE STRAT;
            R = RANDOM$STRATEGY(.DRAWERS, P);
            R = OPTIMAL$STRATEGY(.DRAWERS, P);
        END;
 
        /* IF ONE PRISONER FAILS THEY ALL HANG */
        IF NOT R THEN RETURN 0;
    END;
 
    RETURN 1; /* IF THEY ALL SUCCEED NONE HANG */
END SIMULATE;
 
/* RUN MANY SIMULATIONS AND COUNT THE SUCCESSES */
RUN$SIMULATIONS: PROCEDURE (N, STRAT) ADDRESS;
    DECLARE STRAT BYTE, (I, N, SUCC) ADDRESS;
    SUCC = 0;
    DO I=1 TO N;
        SUCC = SUCC + SIMULATE(STRAT);
    END;
    RETURN SUCC;
END RUN$SIMULATIONS;
 
/* RUN AND PRINT SIMULATIONS */
RUN$AND$PRINT: PROCEDURE (NAME, STRAT, N);
    DECLARE (NAME, N, S) ADDRESS, STRAT BYTE;
    CALL PRINT(NAME);
    CALL PRINT(.' STRATEGY: $');
    S = RUN$SIMULATIONS(N, STRAT);
    CALL PRINT$NUMBER(S);
    CALL PRINT(.' OUT OF $');
    CALL PRINT$NUMBER(N);
    CALL PRINT(.' - $');
    CALL PRINT$NUMBER( S*10 / (N/10) );
    CALL PRINT(.(37,13,10,'$'));
END RUN$AND$PRINT;
 
CALL RUN$AND$PRINT(.'RANDOM$', RANDOM, N$SIMS);
CALL RUN$AND$PRINT(.'OPTIMAL$', OPTIMAL, N$SIMS);
CALL EXIT;
EOF