home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / lang / prolog / 2325 < prev    next >
Encoding:
Internet Message Format  |  1993-01-06  |  2.1 KB
  1. Path: sparky!uunet!pipex!unipalm!uknet!rook.ukc.ac.uk!merlin.ukc.ac.uk!arc1
  2. From: arc1@ukc.ac.uk (Tony Curtis)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: ye ancient British coinage problem
  5. Keywords: prolog, coins
  6. Message-ID: <5502@merlin.ukc.ac.uk>
  7. Date: 6 Jan 93 17:07:10 GMT
  8. Sender: arc1@ukc.ac.uk
  9. Organization: Computing Lab, University of Kent at Canterbury, UK.
  10. Lines: 72
  11. Nntp-Posting-Host: merlin.ukc.ac.uk
  12.  
  13. Here's a (hopefully right) solution to Ken's minimum-coin-count problem
  14. for old British coins.
  15.  
  16. tony
  17.  
  18. %
  19. % No guarantees, use it if you will.  If you do, please
  20. % acknowledge the source.  If you make money from the code
  21. % then give me a share too!
  22. %
  23. % Tony Curtis
  24. %
  25.  
  26. %
  27. % these have to be sorted mono. descending
  28. %
  29. coin('ten shilling note', 120).
  30. coin(       'half-crown',  30).
  31. coin(           'florin',  24).
  32. coin(         'shilling',  12).
  33. coin(         'sixpence',   6).
  34. coin(   'threepenny bit',   3).
  35. coin(            'penny',   1).
  36.  
  37. %
  38. % entry point
  39. %
  40. %           solve(+Sum, ?Coins)
  41. %
  42. % Generate a list of all the possible starting coins <= the
  43. % initial value.
  44. %
  45. solve(0, []).
  46. solve(Sum, Coins) :-
  47.         Sum > 0,
  48.     findall((Value, [Coin]), ok_coin(Coin, Value, Sum), FirstValues),
  49.     search(FirstValues, Sum, Coins).
  50.  
  51. %
  52. % generate solutions until the required sum appears
  53. % in the coin list
  54. %
  55. search(Values, Sum, Coins) :-
  56.     member((Sum, Coins), Values),
  57.     !.
  58. search(Values, Sum, Coins) :-
  59.     iterate_solution(Values, Sum, VClist),
  60.     search(VClist, Sum, Coins).
  61.  
  62. %
  63. % each member of the list is (Value, [Coins]).  Value tracks
  64. % the accumulated total of the coins in Coins.  Coins is a list
  65. % of coin names
  66. %
  67. % for each value-coins pair, get the next lowest coin which can be
  68. % used, and add its value to Value and the name to Coins.
  69. %
  70. iterate_solution([], _, []).
  71. iterate_solution([(Value, Coins) | T1], Sum, [(NewValue, NewCoins) | T2]) :-
  72.     SumLeft is Sum - Value,
  73.     ok_coin(Coin, ThisValue, SumLeft),
  74.     !,
  75.     NewValue is ThisValue + Value,
  76.     append(Coins, [Coin], NewCoins),
  77.     iterate_solution(T1, Sum, T2).
  78.  
  79. %
  80. % A coin is ok if it is <= the current sum
  81. %
  82. ok_coin(Coin, Value, Sum) :-
  83.     coin(Coin, Value),
  84.     Value =< Sum.
  85.