PUZZLE.mesa
Copyright © 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
Puzzle:
PROGRAM
IMPORTS BasicTime, IO, UnsafeStorage, ViewerIO
= BEGIN
an undocumented, compute-bound program from forest baskett
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
};
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;
IO.PutRope[out, "puzzle filled\n"];
PlaceResult ← 0
};
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 {
IO.PutF[out, "piece %g at %g\n", [integer[I + 1]], [integer[K + 1]] ];
TrialResult ← TRUE;
GO TO Label1}
ENDLOOP;
TrialResult ← FALSE
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 {
IO.PutF[out, "success in %g trials\n", [integer[Kount]]];
}
ELSE {
IO.PutRope[out, "failure\n"];
};
IO.PutF[out, "elapsed user time: %g secs\n",
[real[BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[] - startPulses]]]];
};
PuzzleRun[];
END.