home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / prolog / 2344 < prev    next >
Encoding:
Text File  |  1993-01-08  |  1.9 KB  |  59 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!infonode!ingr!capalo!quintus!quintus!ludemann
  3. From: ludemann@quintus.com (Peter Ludemann)
  4. Subject: Re: British coinage problem
  5. Message-ID: <1993Jan8.220355.3496@quintus.com>
  6. Keywords: iterative deepening, DCG
  7. Sender: news@quintus.com (USENET news account)
  8. Nntp-Posting-Host: ebisu
  9. Organization: Quintus Corporation, Palo Alto, CA
  10. References: <1993Jan7.141322.22240@ecrc.de> <8118@skye.ed.ac.uk>
  11. Date: Fri, 8 Jan 1993 22:03:55 GMT
  12. Lines: 45
  13.  
  14. /* Problem: to find the smallest number of old British coins
  15.    that sum up to some amount.
  16.  
  17.    Technique: iterative deepening, with a limit from the first
  18.    solution found.  (If the limit isn't provided, there would
  19.    be infinite backtracking if you tried to use this predicate
  20.    to find all solutions.)  The iterative deepening calls sum//1
  21.    with the lists [_], [_,_], [_,_,_] up to the limit length.
  22. */
  23.  
  24. shortest_sum(Sum, Coins) :- 
  25.     sum(Sum, Coins1), !, /* we want one solution for a bound */
  26.     length(Coins1, MaxLength),
  27.     shortest_sum(Sum, Coins, 1, MaxLength),
  28.     !. /* and no need to compute any more solutions */
  29.  
  30. shortest_sum(Sum, Coins, Length, MaxLength) :-
  31.     Length =< MaxLength,
  32.     shortest_sum2(Sum, Coins, Length, MaxLength).
  33.  
  34. shortest_sum2(Sum, Coins, Length, _) :-
  35.     length(Coins, Length), /* create Coins list of given Length */
  36.     sum(Sum, Coins).
  37. shortest_sum2(Sum, Coins, Length, MaxLength) :-
  38.     Length2 is Length + 1,
  39.     shortest_sum(Sum, Coins, Length2, MaxLength).
  40.  
  41. /* Here is John Dowding's DCG method for generating lists of
  42.    possible solutions (I've removed one cut from his code): */
  43.  
  44. sum(Sum, Coins) :- phrase(sum(Sum), Coins).
  45.  
  46. sum(Sum) --> coin(V), {V =< Sum, Rest is Sum-V}, sum(Rest).
  47. sum(0) --> [].
  48.  
  49. coin(120) --> ['ten shilling note'].
  50. coin(30)  --> ['half-crown'].
  51. coin(24)  --> [florin].
  52. coin(12)  --> [shilling].
  53. coin(6)   --> [sixpence].
  54. coin(3)   --> ['threepenny bit'].
  55. coin(1)   --> [penny].
  56.  
  57. - Peter Ludemann
  58.  
  59.