home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / SOLVLOG.ZIP / SOLVLOG2.PRO < prev   
Encoding:
Prolog Source  |  1987-02-26  |  5.4 KB  |  108 lines
  1. /*
  2. USING TURBO PROLOG TO SOLVE LOGIC PROBLEMS -- AN ALTERNATIVE
  3. BY: RICHARD S. NOWAKOWSKI
  4.  
  5.      This is an alternative solution to Garry Vass's "logic problem".  For a 
  6. statement of the problem, its clues, an excellent analysis and Vass's solution 
  7. see the accompanying file SOLVLOG.PRO by Garry Vass.
  8.  
  9.      My approach to this type of problem is to use a simple, list structure and 
  10. to let Prolog's unification and bactracking mechanisms find the solution.  The 
  11. three key predicates, i.e., member, append and permute, are all standard C&M 
  12. fare.  To run this program, give the goal "final" during interactive mode.  
  13. Then, the start time, the solution, and the end time will be displayed.  On my 8
  14. Mhz AT compatible this takes 0.11 seconds to find and print the solution, 
  15. whereas Vass's version takes about 17 seconds.
  16.  
  17.      I am a newcomer to Prolog, and there is no doubt that my solution could be 
  18. improved and/or generalized.  Leave a message for me with your comments on the 
  19. SSNJ BBS (201-729-7410)  or on the Turbo Prolog SIG on the POLICE STATION BBS 
  20. (201-963-3115). */
  21.  
  22.  
  23. DOMAINS
  24.   list = symbol*                                 /* lists for names, items */
  25.   intlist = integer*                             /* list for costs */
  26.   set = set (symbol, symbol, symbol, integer)    /* data structure for each purchase */
  27.   setlist = set*                                 /* list for solutions */
  28.  
  29. PREDICATES
  30.   member (set, setlist)                     /* determine membership in a list */
  31.  
  32.   append (list, list, list)                 /* append two lists */
  33.   append (intlist, intlist, intlist)  
  34.   
  35.   permute (list, list)                      /* rearranges a list */
  36.   permute (intlist, intlist)  
  37.   
  38.   fnamelist (list)                          /* use lists for facts */
  39.   lnamelist (list)
  40.   itemlist (list)
  41.   costlist (intlist)
  42.  
  43.   isvalidsolution (setlist)                 /* generates valid solutions */
  44.   resolution (setlist)                      /* resolution of facts with clues */
  45.   final                                     /* timing loop and printing control */
  46.  
  47. CLAUSES
  48.   member (X, [X|_]).                        /* standard list processing predicate */
  49.   member (X, [_|Tail]) :- member (X, Tail).
  50.  
  51.   append ([], L, L).                        /* standard list processing predicate */
  52.   append ([X|L1], L2, [X|L3]) :- append (L1, L2, L3).
  53.  
  54.   permute ([], []).                         /* standard list processing predicate */
  55.   permute (L, [H|T]) :- append(V,[H|U],L),  
  56.                         append(V,U,W), 
  57.                         permute(W,T).
  58.  
  59.   fnamelist ([garry, john, ron]).           /* facts for each data type */
  60.   lnamelist ([vass, ross, clark]).
  61.   itemlist ([modem, monitor, keyboard]).
  62.   costlist ([150, 200, 250]).
  63.   
  64.   isvalidsolution ([set (FName1, LName1, Item1, Cost1),        /* Each valid solution is a list  */
  65.                     set (FName2, LName2, Item2, Cost2),        /* with three members.            */
  66.                     set(FName3, LName3, Item3, Cost3)]) :-     
  67.      fnamelist ([FName1, FName2, FName3]),                     /* Order of first names is fixed. */
  68.      lnamelist (LNamelist),                                    /* Last names can be in any order.*/
  69.      permute (LNamelist, [LName1, LName2, LName3]),
  70.      itemlist (Itemlist),                                      /* Items can be in any order.     */
  71.      permute (Itemlist, [Item1, Item2, Item3]),
  72.      costlist (Costlist),                                      /* Costs can be in any order.     */
  73.      permute (Costlist, [Cost1, Cost2, Cost3]).
  74.      
  75.   resolution (Solution) :- isvalidsolution (Solution),         /* Solution must be valid.        */
  76.      member (set (_,_,monitor,150), Solution),                 /* Clue 1: monitor is cheapest.   */
  77.      member (set (ron,_,Item4ron,_), Solution),                /* Clue 2: Ron did not buy        */
  78.      Item4ron<>"modem",                                        /*         the modem.             */
  79.      member (set (garry, _, _, Cost4garry), Solution),         /* Clue 3: Gary spent less        */
  80.      member (set (_, ross, Item4ross, Cost4ross), Solution),   /*         than Ross, and Ross    */
  81.      Cost4garry < Cost4ross,                                   /*         did not buy the        */ 
  82.      Item4ross <> "keyboard",                                  /*         the keyboard.          */
  83.      member (set (_, clark, _, 250), Solution).                /* Clue 4: Clark paid $250.       */
  84.  
  85.   final:- time (Starthrs, Startmins, Startsecs,Starthunds),nl, /* Begin timing */
  86.        write ("Beginning at ",Starthrs,":",Startmins,":",
  87.               Startsecs,":",Starthunds), nl,
  88.        resolution ([set (FName1, LName1, Item1, Cost1),        /* Find solution */
  89.                     set (FName2, LName2, Item2, Cost2), 
  90.                     set(FName3, LName3, Item3, Cost3)]),
  91.        write (FName1," ",LName1," purchased a ",               /* Write solution */
  92.               Item1," for  $",Cost1), nl,
  93.        write (FName2," ",LName2," purchased a ",
  94.               Item2," for  $",Cost2), nl,
  95.        write (FName3," ",LName3," purchased a ",
  96.               Item3," for  $",Cost3), nl,
  97.        time (Endhrs,Endmins,Endsecs,Endhunds),                 /* End timing */
  98.        write ("Ending at ",Endhrs,":",Endmins,":",
  99.                Endsecs,":",Endhunds), nl.
  100.          
  101.          
  102. /*
  103. goal
  104.      final.
  105. */             
  106.  
  107. /* remove comment marks around goal for autorun or to compile to EXE file */
  108.