155 lines
4 KiB
Text
155 lines
4 KiB
Text
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
|