Puzzle.mesa
Copyright Ó 1984, 1986, 1987 by Xerox Corporation. All rights reserved.
Pascal-to-Mesa translator output, translated at 19-Dec-82 18:02:55 PST
Russ Atkinson (RRA) May 18, 1987 8:39:38 pm PDT
Improved to more natural Mesa code on March 18, 1986 11:50:12 am PST
Puzzle:
PROGRAM
IMPORTS BasicTime, IO, UnsafeStorage, ViewerIO
= BEGIN
useIO: BOOL = FALSE;
an undocumented, compute-bound program from forest baskett
out: IO.STREAM = IF useIO
THEN ViewerIO.CreateViewerStreams["Puzzle.log", NIL, "Puzzle.log", FALSE].out
ELSE NIL;
StaticZone: UNCOUNTED ZONE ← UnsafeStorage.GetSystemUZone[];
Size: PUBLIC CARDINAL = 511; -- d*d*d - 1
Classmax: PUBLIC CARDINAL = 3;
Typemax: PUBLIC CARDINAL = 12;
D: PUBLIC CARDINAL = 8;
Piececlass: PUBLIC TYPE = [0..Classmax];
Piecetype: PUBLIC TYPE = [0..Typemax];
Position: PUBLIC TYPE = [0..Size];
Piececount:
PUBLIC
LONG
POINTER
TO
ARRAY Piececlass
OF
INT [0..13] ←
StaticZone.NEW[ARRAY Piececlass OF INT [0..13]];
Class:
PUBLIC
LONG
POINTER
TO
ARRAY Piecetype
OF Piececlass ←
StaticZone.NEW[ARRAY Piecetype OF Piececlass];
Piecemax:
PUBLIC
LONG
POINTER
TO
ARRAY Piecetype
OF Position ←
StaticZone.NEW[ARRAY Piecetype OF Position];
Puzzle:
PUBLIC
LONG
POINTER
TO
ARRAY Position
OF
BOOL ←
StaticZone.NEW[ARRAY Position OF BOOL];
P:
PUBLIC
LONG
POINTER
TO
ARRAY Piecetype
OF
ARRAY Position
OF
BOOL ←
StaticZone.NEW[ARRAY Piecetype OF ARRAY Position OF BOOL];
Kount: PUBLIC INT;
TrialDepth: INT;
MaxTrialDepth: INT;
Fit:
PUBLIC
PROC [
I: Piecetype,
J: Position]
RETURNS [
BOOL] = {
FOR
K: Position
IN [0..Piecemax^[I]]
DO
IF P^[I][K] THEN IF Puzzle^[J + K] THEN RETURN [FALSE];
ENDLOOP;
RETURN [TRUE];
};
Place:
PUBLIC
PROC [
I: Piecetype,
J: Position]
RETURNS [Position] = {
FOR
K: Position
IN [0..Piecemax^[I]]
DO
IF P^[I][K] THEN Puzzle^[J + K] ← TRUE
ENDLOOP;
Piececount^[Class^[I]] ← Piececount^[Class^[I]] - 1;
FOR
K: Position
IN [J..Size]
DO
IF NOT Puzzle^[K] THEN RETURN [K];
ENDLOOP;
RETURN [0];
};
Remove:
PUBLIC
PROC [
I: Piecetype,
J: Position] = {
FOR
K: Position
IN [0..Piecemax^[I]]
DO
IF P^[I][K] THEN Puzzle^[J + K] ← FALSE
ENDLOOP;
Piececount^[Class^[I]] ← Piececount^[Class^[I]] + 1
};
Trial:
PUBLIC
PROC [
J: Position]
RETURNS [
TrialResult:
BOOL] = {
TrialDepth ← TrialDepth + 1;
IF TrialDepth > MaxTrialDepth THEN MaxTrialDepth ← TrialDepth;
{
FOR
I: Piecetype
IN [0..Typemax]
DO
IF Piececount^[Class^[I]] # 0
THEN
IF Fit[I, J]
THEN {
K: Position ← Place[I, J];
IF Trial[K]
OR K = 0
THEN GO TO Label1
ELSE Remove[I, J];
}
ENDLOOP;
TrialResult ← FALSE
EXITS Label1 => TrialResult ← TRUE;
};
Kount ← Kount + 1;
TrialDepth ← TrialDepth - 1;
};
PuzzleRun:
PUBLIC
PROC = {
startPulses: BasicTime.Pulses = BasicTime.GetClockPulses[];
M: Position;
N: Position;
I, J, K: PUBLIC [0..13];
TrialDepth ← 0;
MaxTrialDepth ← 0;
FOR M
IN [0..Size]
DO
Puzzle^[M] ← TRUE
ENDLOOP;
FOR I
IN [1..5]
DO
FOR J
IN [1..5]
DO
FOR K
IN [1..5]
DO
Puzzle^[I + D * (J + D * K)] ← FALSE
ENDLOOP
ENDLOOP
ENDLOOP;
FOR I
IN [0..Typemax]
DO
FOR M
IN [0..Size]
DO
P^[I][M] ← FALSE
ENDLOOP
ENDLOOP;
FOR I
IN [0..3]
DO
FOR J
IN [0..1]
DO
FOR K
IN [0..0]
DO
P^[0][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[0] ← 0;
Piecemax^[0] ← 3 + D * 1 + D * D * 0;
FOR I
IN [0..1]
DO
FOR J
IN [0..0]
DO
FOR K
IN [0..3]
DO
P^[1][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[1] ← 0;
Piecemax^[1] ← 1 + D * 0 + D * D * 3;
FOR I
IN [0..0]
DO
FOR J
IN [0..3]
DO
FOR K
IN [0..1]
DO
P^[2][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[2] ← 0;
Piecemax^[2] ← 0 + D * 3 + D * D * 1;
FOR I
IN [0..1]
DO
FOR J
IN [0..3]
DO
FOR K
IN [0..0]
DO
P^[3][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[3] ← 0;
Piecemax^[3] ← 1 + D * 3 + D * D * 0;
FOR I
IN [0..3]
DO
FOR J
IN [0..0]
DO
FOR K
IN [0..1]
DO
P^[4][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[4] ← 0;
Piecemax^[4] ← 3 + D * 0 + D * D * 1;
FOR I
IN [0..0]
DO
FOR J
IN [0..1]
DO
FOR K
IN [0..3]
DO
P^[5][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[5] ← 0;
Piecemax^[5] ← 0 + D * 1 + D * D * 3;
FOR I
IN [0..2]
DO
FOR J
IN [0..0]
DO
FOR K
IN [0..0]
DO
P^[6][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[6] ← 1;
Piecemax^[6] ← 2 + D * 0 + D * D * 0;
FOR I
IN [0..0]
DO
FOR J
IN [0..2]
DO
FOR K
IN [0..0]
DO
P^[7][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[7] ← 1;
Piecemax^[7] ← 0 + D * 2 + D * D * 0;
FOR I
IN [0..0]
DO
FOR J
IN [0..0]
DO
FOR K
IN [0..2]
DO
P^[8][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[8] ← 1;
Piecemax^[8] ← 0 + D * 0 + D * D * 2;
FOR I
IN [0..1]
DO
FOR J
IN [0..1]
DO
FOR K
IN [0..0]
DO
P^[9][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[9] ← 2;
Piecemax^[9] ← 1 + D * 1 + D * D * 0;
FOR I
IN [0..1]
DO
FOR J
IN [0..0]
DO
FOR K
IN [0..1]
DO
P^[10][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[10] ← 2;
Piecemax^[10] ← 1 + D * 0 + D * D * 1;
FOR I
IN [0..0]
DO
FOR J
IN [0..1]
DO
FOR K
IN [0..1]
DO
P^[11][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[11] ← 2;
Piecemax^[11] ← 0 + D * 1 + D * D * 1;
FOR I
IN [0..1]
DO
FOR J
IN [0..1]
DO
FOR K
IN [0..1]
DO
P^[12][I + D * (J + D * K)] ← TRUE
ENDLOOP
ENDLOOP
ENDLOOP;
Class^[12] ← 3;
Piecemax^[12] ← 1 + D * 1 + D * D * 1;
Piececount^[0] ← 13;
Piececount^[1] ← 3;
Piececount^[2] ← 1;
Piececount^[3] ← 1;
M ← 1 + D * (1 + D * 1);
Kount ← 0;
IF Fit[0, M]
THEN N ← Place[0, M]
ELSE ERROR;
IF Trial[N]
THEN {
IO.PutF[out, "success in %g trials\n", [integer[Kount]]];
}
ELSE {
IO.PutRope[out, "failure\n"];
};
IF useIO
THEN
IO.PutF[out, "elapsed user time: %g secs\n",
[real[BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[] - startPulses]]]];
};
PuzzleRun[];
END.