DIRECTORY BasicTime, IO, ViewerIO, UnsafeStorage; Puzzle: PROGRAM IMPORTS BasicTime, IO, UnsafeStorage, ViewerIO = BEGIN out: IO.STREAM = ViewerIO.CreateViewerStreams["Puzzle.log", NIL, "Puzzle.log", FALSE].out; 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]; M, N: PUBLIC Position; I, J, K: PUBLIC [0..13]; Kount: PUBLIC INT; TrialDepth: INT; MaxTrialDepth: INT; Fit: PUBLIC PROC [I: Piecetype, J: Position] RETURNS [FitResult: BOOL] = { K: Position; FitResult _ FALSE; {FOR K IN [0..Piecemax^[I]] DO IF P^[I][K] THEN IF Puzzle^[J + K] THEN GO TO Label1 ENDLOOP; FitResult _ TRUE EXITS Label1 => NULL} }; Place: PUBLIC PROC [I: Piecetype, J: Position] RETURNS [PlaceResult: Position] = { K: Position; FOR K IN [0..Piecemax^[I]] DO IF P^[I][K] THEN Puzzle^[J + K] _ TRUE ENDLOOP; Piececount^[Class^[I]] _ Piececount^[Class^[I]] - 1; {FOR K IN [J..Size] DO IF NOT Puzzle^[K] THEN {PlaceResult _ K; GO TO Label1} ENDLOOP; PlaceResult _ 0 EXITS Label1 => NULL} }; Remove: PUBLIC PROC [I: Piecetype, J: Position] = { K: Position; FOR K 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] = { I: Piecetype; K: Position; TrialDepth _ TrialDepth + 1; IF TrialDepth > MaxTrialDepth THEN MaxTrialDepth _ TrialDepth; {FOR I IN [0..Typemax] DO IF Piececount^[Class^[I]] # 0 THEN IF Fit[I, J] THEN {K _ Place[I, J]; IF Trial[K] OR K = 0 THEN { TrialResult _ TRUE; GO TO Label1} ELSE Remove[I, J]} ENDLOOP; TrialResult _ FALSE EXITS Label1 => NULL}; Kount _ Kount + 1; TrialDepth _ TrialDepth - 1; }; PuzzleRun: PUBLIC PROC = { startPulses: BasicTime.Pulses = BasicTime.GetClockPulses[]; 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 { } ELSE { }; IO.PutF[out, "elapsed user time: %g secs\n", [real[BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[] - startPulses]]]]; }; PuzzleRun[]; END. <PUZZLE.mesa Copyright c 1984 by Xerox Corporation. All rights reserved. Pascal-to-Mesa translator output, translated at 19-Dec-82 18:02:55 PST slightly modified by Russ Atkinson, March 26, 1984 12:07:48 pm PST (removed PascalRuntime dependence by eliminating I/O) Russ Atkinson, July 19, 1984 11:31:24 pm PDT an undocumented, compute-bound program from forest baskett IO.PutRope[out, "puzzle filled\n"]; IO.PutF[out, "piece %g at %g\n", [integer[I + 1]], [integer[K + 1]] ]; IO.PutF[out, "success in %g trials\n", [integer[Kount]]]; IO.PutRope[out, "failure\n"]; ʘšœ ™ Jšœ Ïmœ1™Jšœ žœžœ žœ˜/—š œ žœžœžœžœžœ žœ ˜?Jšœ žœžœ žœ ˜-—šœžœžœžœžœžœ žœžœ˜8Jš œ žœžœ žœžœ˜(—šžœžœžœžœžœžœ žœžœ žœžœ˜FJš œ žœžœ žœžœ žœžœ˜;—Jšžœžœžœ ˜Jšžœžœžœžœ ˜Jšœžœžœ˜Jšœ žœ˜Jšœžœ˜J˜šÏnœžœž˜Jš œžœ žœ žœ žœ˜9Jšžœ ˜ J˜Jšœ žœ˜š œžœžœžœžœžœ˜Jšžœžœžœžœžœžœ žœžœžœžœžœ˜4Jšžœ˜ Jšœ ž˜šž˜Jšœ žœ˜——J˜J˜—š œžœž˜Jšœžœ žœ žœ˜?Jšžœ ˜ J˜š žœžœžœžœžœ˜Jšžœžœžœžœžœ žœžœž˜&Jšžœ˜ —Jšœžœžœ˜5š œžœžœžœžœžœ˜šžœžœ žœžœ˜šœžœ˜Jšžœžœ˜ ——Jšžœ˜Jšœ#™#J˜šž˜Jšœ žœ˜——J˜J˜—š  œžœžœžœ žœ˜3Jšžœ ˜ J˜š žœžœžœžœžœ˜Jšžœžœžœžœžœ žœžœž˜'Jšžœ˜ —Jšœžœžœ˜3J˜J˜—Jš  œžœžœžœ žœžœ˜@˜Jšžœ ˜Jšžœ ˜ J˜Jšœ˜Jšžœžœ˜>J˜š œžœžœžœžœ˜šžœžœžœ˜#šžœžœžœžœ˜šœžœ žœžœ˜šžœžœžœžœ˜šžœ˜Jšœ*žœžœ ™FJšœžœ˜Jšžœžœ˜ —šžœ˜Jšœžœžœ˜ —————Jšžœ˜ Jšœž˜šž˜Jšœ žœ˜——J˜Jšœ˜J˜J˜J˜—š  œžœžœ˜Jšœ;˜;Jšœ˜Jšœ˜šžœžœžœ žœ˜Jšœžœž˜Jšžœ˜ —šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš œžœžœžœžœžœž˜$Jšž˜—Jšž˜—Jšžœ˜ —šžœžœžœžœ˜šžœžœžœ žœ˜Jšžœžœžœž˜Jšž˜—Jšžœ˜ —šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜!Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜&šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜"Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜'šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜"Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜'šžœžœžœžœ˜šžœžœžœžœ˜šžœžœžœžœ˜Jš žœžœžœžœžœžœž˜"Jšž˜—Jšž˜—Jšžœ˜ —J˜Jšœžœžœžœ˜'J˜J˜J˜J˜Jšžœžœžœ˜J˜ šžœžœ˜ Jšžœžœ žœ˜Jšžœžœ˜ —šžœžœ˜ šžœ˜Jšžœ7™9J˜—šžœ˜Jšžœ™J˜——šžœ*˜,JšœM˜M—J˜J˜—J˜ J˜Jšžœ˜J˜J˜——…—&ä