examples/examples.old/search.log

   1 PROGRAM BACKTRACKING;\r
   2   UNIT BACKTRACK: CLASS;\r
   3     HIDDEN SE,ELEM,TOP;\r
   4     VAR  ROOT:NODE,SEARCH:SE,FOUND,OPT:NODE,\r
   5          NUMBER_OF_NODES,NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;\r
   6 \r
   7     UNIT NODE: COROUTINE(FATHER:NODE);\r
   8       VAR NSONS,LEVEL: INTEGER , DEADEND:BOOLEAN;\r
   9       UNIT VIRTUAL LEAF:  FUNCTION :BOOLEAN;\r
  10       END LEAF;\r
  11       UNIT VIRTUAL ANSWER :FUNCTION :BOOLEAN;\r
  12       END ANSWER;\r
  13       UNIT VIRTUAL LASTSON: FUNCTION : BOOLEAN;\r
  14       END LASTSON;\r
  15       UNIT VIRTUAL NEXTSON: FUNCTION : NODE;\r
  16       END NEXTSON;\r
  17       UNIT VIRTUAL EQUAL : FUNCTION (W:NODE):BOOLEAN;\r
  18       END EQUAL;\r
  19       UNIT VIRTUAL COST: FUNCTION :REAL;\r
  20       END COST;\r
  21     BEGIN\r
  22       IF FATHER =/= NONE\r
  23       THEN\r
  24         LEVEL:=FATHER.LEVEL+1\r
  25       ELSE\r
  26         LEVEL:=0\r
  27       FI;\r
  28    END NODE;\r
  29 \r
  30     UNIT OK: FUNCTION (V:NODE):BOOLEAN;\r
  31       VAR W:NODE;\r
  32     BEGIN\r
  33       IF V=NONE THEN RESULT:=FALSE; RETURN FI;\r
  34       RESULT:=TRUE; W:=V.FATHER;\r
  35       WHILE W =/= NONE\r
  36       DO\r
  37         IF V.EQUAL(W) THEN RESULT:=FALSE; RETURN FI;\r
  38         W:=W.FATHER\r
  39       OD\r
  40     END OK;\r
  41 \r
  42     UNIT PURGE: PROCEDURE (V:NODE);\r
  43       VAR W: NODE;\r
  44     BEGIN\r
  45       IF V=NONE THEN RETURN FI;\r
  46       DO\r
  47         W:=V.FATHER; KILL(V);\r
  48         IF W=NONE THEN RETURN FI;\r
  49         W.NSONS:=W.NSONS-1;\r
  50         IF W.NSONS =/= 0 THEN RETURN FI;\r
  51         V:=W\r
  52       OD;\r
  53     END PURGE;\r
  54 \r
  55     VAR TOP:ELEM;\r
  56 \r
  57     UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);\r
  58     END ELEM;\r
  59 \r
  60     UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);\r
  61     BEGIN\r
  62       TOP:=NEW ELEM(TOP,V);\r
  63     END INSERT;\r
  64 \r
  65     UNIT VIRTUAL DELETE: FUNCTION :NODE;\r
  66       VAR E:ELEM;\r
  67     BEGIN\r
  68       IF TOP =/= NONE\r
  69       THEN\r
  70         RESULT:=TOP.V;\r
  71         E:=TOP; TOP:=TOP.NEXT; KILL(E);\r
  72       FI;\r
  73     END DELETE;\r
  74 \r
  75     UNIT SE: COROUTINE ;\r
  76       VAR I:INTEGER,V,W:NODE;\r
  77     BEGIN\r
  78       RETURN; CALL INSERT(ROOT);\r
  79       DO\r
  80         V:=DELETE;\r
  81         IF V=NONE THEN EXIT FI;\r
  82         ATTACH(V);\r
  83         IF V.ANSWER\r
  84         THEN\r
  85           NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;\r
  86           FOUND:=V;\r
  87           IF OPT=NONE ORIF V.COST < OPT.COST\r
  88           THEN\r
  89              OPT:=V\r
  90           FI;\r
  91           DETACH;\r
  92           (* HERE THE USER OF BACKTRACK MAY UNDERTAKE SOME ACTIONS\r
  93              ON THE ANSWER NODES. IF NOT NECESSARY DO ATTACH      *)\r
  94         ELSE\r
  95           IF V.DEADEND\r
  96           THEN\r
  97             NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;\r
  98             CALL PURGE(V);\r
  99           ELSE\r
 100             DO\r
 101               W:=V.NEXTSON; V.NSONS:=V.NSONS+1;\r
 102               NUMBER_OF_NODES:=NUMBER_OF_NODES+1;\r
 103               IF OK(W)\r
 104               THEN\r
 105                 W.DEADEND:=W.LEAF; CALL INSERT(W);\r
 106               FI;\r
 107               IF V.LASTSON THEN EXIT FI;\r
 108             OD;\r
 109           FI;\r
 110         FI;\r
 111       OD;\r
 112       FOUND:=NONE;\r
 113     END SE;\r
 114 \r
 115 \r
 116     UNIT KILLALL :PROCEDURE;\r
 117       VAR V:NODE;\r
 118     BEGIN\r
 119       DO\r
 120         V:=DELETE;\r
 121         IF V=NONE THEN RETURN FI;\r
 122         CALL PURGE(V);\r
 123       OD;\r
 124     END KILLALL;\r
 125 \r
 126   BEGIN\r
 127     SEARCH:=NEW SE;\r
 128     INNER;\r
 129     KILL(SEARCH); CALL KILLALL;\r
 130   END BACKTRACK;\r
 131 \r
 132 \r
 133 UNIT BESTSEARCH: BACKTRACK CLASS;\r
 134   (*  BESTSEARCH USES A PRIORITY QUEUE FOR NODES.\r
 135       QUEUE IS ORGANIZED AS A HEAP IN THE ARRAY A.\r
 136       THE FIRST ELEMENT A(1) IS THE LEAST ONE. *)\r
 137   HIDDEN A,B,X,K,M,I,J;\r
 138   VAR A,B:ARRAYOF EX_NODE,   X : EX_NODE, K,M,I,J:INTEGER;\r
 139     (*M- CURRENT ARRAY A LENTGTH\r
 140       K- CURRENT HEAP LENGTH\r
 141       B- SRATCH ARRAY *)\r
 142 \r
 143   UNIT  EX_NODE : NODE CLASS;\r
 144     UNIT VIRTUAL  LESS : FUNCTION (X: EX_NODE) : BOOLEAN;\r
 145     END  LESS;\r
 146   END EX_NODE;\r
 147 \r
 148   UNIT VIRTUAL DELETE: FUNCTION :EX_NODE;\r
 149 \r
 150     BEGIN\r
 151       IF K=0 THEN RETURN FI;\r
 152       RESULT:=A(1); X:=A(K); K:=K-1;\r
 153       IF K=0\r
 154       THEN\r
 155         KILL(A); RETURN\r
 156       FI;\r
 157       IF K*2<M\r
 158       THEN\r
 159         ARRAY B DIM (1: M DIV 2);\r
 160         FOR I:=1 TO K DO B(I):=A(I) OD;\r
 161         KILL(A); M:=M DIV 2; A:=B\r
 162       FI;\r
 163       I:=1; J:=2;\r
 164       WHILE J <= K\r
 165       DO\r
 166         IF J+1 <= K ANDIF A(J+1).LESS( A(J))\r
 167         THEN\r
 168           J:=J+1\r
 169         FI;\r
 170         IF X.LESS( A(J)) THEN EXIT FI;\r
 171         A(I):=A(J); I:=J;  J:=2*I\r
 172       OD;\r
 173       A(I):=X\r
 174     END DELETE;\r
 175 \r
 176 \r
 177   UNIT VIRTUAL INSERT : PROCEDURE(X: EX_NODE);\r
 178    BEGIN\r
 179      IF K=0\r
 180      THEN\r
 181        ARRAY A DIM (1:2); M:=2;\r
 182      FI;\r
 183      IF K=M\r
 184      THEN\r
 185        ARRAY B DIM(1:2*M); FOR I:=1 TO M DO B(I):=A(I) OD;\r
 186        KILL(A); M:=2*M; A:=B;\r
 187      FI;\r
 188      K,J:=K+1;\r
 189      IF K=1 THEN A(1):=X; RETURN; FI;\r
 190      I:= J DIV 2;\r
 191      WHILE I>=1\r
 192      DO\r
 193        IF A(I).LESS( X ) THEN EXIT FI;\r
 194        A(J):=A(I); J:=I; I:= J DIV 2\r
 195      OD;\r
 196      A(J):=X\r
 197    END INSERT;\r
 198 \r
 199    BEGIN\r
 200      INNER;\r
 201      CALL KILLALL;\r
 202    END BESTSEARCH;\r
 203 \r
 204 \r
 205 \r
 206   VAR N,Q:INTEGER,H1,H2,H3:CHAR;\r
 207    (* Q - BOAT CAPACITY, N- NUMBER OF CANNIBALS, N- NUMBER OF MISSIONARIES *)\r
 208 \r
 209 BEGIN\r
 210   DO\r
 211     WRITE(" NUMBER OF PERSONS ");\r
 212     WRITE(" (IF END OF SESSION WRITE 0) =");\r
 213     READLN(N);\r
 214     IF N=0 THEN EXIT FI;\r
 215     WRITE(" BOAT CAPACITY=");\r
 216     READLN(Q);\r
 217 \r
 218     PREF BESTSEARCH BLOCK\r
 219     VAR M,C:INTEGER;\r
 220       (* M- NUMBER OF MISSIONARIES, C- NUMBER OF CANNIBALS ON THE BOAT *)\r
 221 \r
 222       UNIT STATE: EX_NODE CLASS(ML,CL:INTEGER);\r
 223       VAR MR,CR:INTEGER, LEFT:BOOLEAN;\r
 224 \r
 225          (* ML- NUMBER OF MISSIONARIES ON THE LEFT BANK OF THE RIVER\r
 226             MR- NUMBER OF MISSIONARIES ON THE RIGHT BANK OF THE RIVER\r
 227             CL- NUMBER OF CANNIBALS ON THE LEFT BANK OF THE RIVER\r
 228             CR- NUMBER OF CANNIBALS ON THE RIGHT BANK OF THE RIVER\r
 229             LEFT- TRUE IFF THE BOAT IS ON THE LEFT BANK OF THE RIVER *)\r
 230 \r
 231       UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;\r
 232       BEGIN\r
 233         RESULT:=ML=0 AND CL=0\r
 234       END ANSWER;\r
 235 \r
 236       UNIT VIRTUAL LEAF: FUNCTION : BOOLEAN;\r
 237       BEGIN\r
 238         IF  ML<0 ORIF MR<0 ORIF CL<0 ORIF CR<0 ORIF\r
 239             ML>N ORIF MR>N ORIF CL>N ORIF CR>N ORIF\r
 240             ML<CL AND ML>0 ORIF MR<CR AND MR>0\r
 241         THEN\r
 242           RESULT:=TRUE\r
 243         FI\r
 244       END LEAF;\r
 245 \r
 246 \r
 247       UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;\r
 248       BEGIN\r
 249         IF C=0 AND M=Q\r
 250         THEN\r
 251           RESULT:=TRUE; M:=0; C:=0;\r
 252         FI;\r
 253       END;\r
 254 \r
 255       UNIT VIRTUAL NEXTSON : FUNCTION :STATE;\r
 256       BEGIN\r
 257         C:=C+1;\r
 258         IF M=0\r
 259         THEN\r
 260           IF C>Q\r
 261           THEN\r
 262             C:=0; M:=1\r
 263           FI\r
 264         ELSE\r
 265           IF M<C ORIF M+C>Q\r
 266           THEN\r
 267             C:=0; M:=M+1;\r
 268           FI\r
 269         FI;\r
 270         IF LEFT\r
 271         THEN\r
 272           IF C+M<Q\r
 273           THEN\r
 274             RESULT:=NONE\r
 275           ELSE\r
 276             RESULT:=NEW STATE(THIS STATE,ML-M,CL-C)\r
 277           FI\r
 278         ELSE\r
 279           RESULT:=NEW STATE(THIS STATE,ML+M,CL+C)\r
 280         FI;\r
 281       END NEXTSON;\r
 282 \r
 283       UNIT VIRTUAL EQUAL: FUNCTION(S:STATE):BOOLEAN;\r
 284       BEGIN\r
 285         RESULT:=LEFT=S.LEFT AND ML=S.ML AND CL=S.CL;\r
 286       END EQUAL;\r
 287 \r
 288       UNIT VIRTUAL COST: FUNCTION :REAL;\r
 289       BEGIN\r
 290         RESULT:=LEVEL\r
 291       END COST;\r
 292 \r
 293       UNIT VIRTUAL LESS: FUNCTION (S:STATE): BOOLEAN;\r
 294       BEGIN\r
 295         RESULT:=ML+CL<S.ML+S.CL\r
 296       END LESS;\r
 297 \r
 298 \r
 299 \r
 300     BEGIN\r
 301       LEFT:=LEVEL MOD 2 = 0;\r
 302       MR:=N-ML; CR:=N-CL;\r
 303       RETURN;\r
 304       DO\r
 305         IF BOOL1 THEN CALL DISPLAY(THIS STATE) FI;\r
 306         DETACH;\r
 307       OD;\r
 308     END STATE;\r
 309 \r
 310 \r
 311     UNIT DISPLAY: PROCEDURE(V:STATE);\r
 312       VAR J,I:INTEGER, W:STATE,AT: ARRAYOF STATE;\r
 313     BEGIN\r
 314       IF V=NONE THEN WRITELN(" NO MORE SOLUTIONS"); RETURN FI;\r
 315       I:=V.LEVEL;\r
 316       ARRAY AT DIM (0:I);\r
 317       W:=V;\r
 318       FOR J:=I DOWNTO 0\r
 319       DO\r
 320         AT(J):=W; W:=W.FATHER\r
 321       OD;\r
 322       WRITELN("MOVE NUMBER    LEFT SIDE  DIRECTION   RIGHT SIDE");\r
 323       FOR J:=0 TO I\r
 324       DO\r
 325         WRITE(J); WRITE("     ");\r
 326         W:=AT(J);\r
 327         WRITE(W.ML,W.CL,"      ");\r
 328         IF W.LEFT\r
 329         THEN\r
 330           WRITE("->");\r
 331         ELSE\r
 332           WRITE("<-");\r
 333         FI;\r
 334         WRITELN("    ",W.MR,W.CR);\r
 335       OD;\r
 336       KILL(AT);\r
 337     END DISPLAY;\r
 338 \r
 339   VAR BOOL1:BOOLEAN;\r
 340 \r
 341   BEGIN\r
 342       ROOT:=NEW STATE(NONE,N,N);\r
 343       WRITE("DO YOU WANT TO OPTIMIZE ");\r
 344       WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");\r
 345       WRITELN(" (ANSWER OPT OR ALL)");\r
 346       READLN(H1,H2,H3);\r
 347       IF H1='O' AND H2='P' AND H3='T'\r
 348       THEN\r
 349         DO\r
 350           ATTACH(SEARCH);\r
 351           IF FOUND=NONE THEN EXIT FI;\r
 352           IF OPT =/= NONE ANDIF OPT.COST<FOUND.COST\r
 353           THEN\r
 354             EXIT\r
 355           FI;\r
 356         OD;\r
 357         IF OPT =/= NONE\r
 358         THEN\r
 359           CALL DISPLAY(OPT);\r
 360           WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 361           WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 362           WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);\r
 363         ELSE\r
 364           WRITELN("NO SOLUTIONS");\r
 365           WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 366           WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 367         FI;\r
 368       ELSE\r
 369         IF H1='A' AND H2='L' AND H3='L'\r
 370         THEN\r
 371           WRITELN("DO YOU WANT TO PRINT PARTIAL RESULTS?");\r
 372           READLN(H1,H2,H3);\r
 373           IF H1='Y' AND H2='E' AND H3='S'\r
 374           THEN\r
 375             BOOL1:=TRUE\r
 376           FI;\r
 377           DO\r
 378             ATTACH(SEARCH);\r
 379             CALL DISPLAY(FOUND);\r
 380             WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);\r
 381             WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);\r
 382             WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);\r
 383             IF FOUND=NONE THEN EXIT FI;\r
 384             WRITELN("DO YOU WANT TO CONTINUE?");\r
 385             READ(H1,H2);\r
 386             IF H1=/='Y' ORIF H2=/='E' THEN EXIT FI;\r
 387             READLN(H3);\r
 388             IF H3=/='S' THEN EXIT FI;\r
 389           OD;\r
 390         ELSE\r
 391           EXIT\r
 392         FI\r
 393       FI;\r
 394     END;\r
 395    OD;\r
 396 \r
 397  END;\r
 398 \r
 399 END\r
 400 \r
 401 \r
 402 \1a