There are four types of common coins in   US   currency:

   quarters   (25 cents)
   dimes   (10 cents)
   nickels   (5 cents),   and 
   pennies   (1 cent) 


There are six ways to make change for 15 cents:

   A dime and a nickel 
   A dime and 5 pennies
   3 nickels
   2 nickels and 5 pennies
   A nickel and 10 pennies
   15 pennies


Task

How many ways are there to make change for a dollar using these common coins?     (1 dollar = 100 cents).



Optional

Less common are dollar coins (100 cents);   and very rare are half dollars (50 cents).   With the addition of these two coins, how many ways are there to make change for $1000?

(Note:   the answer is larger than   232).



References

 an algorithm from the book Structure and Interpretation of Computer Programs.
 an article in the algorithmist.
 Change-making problem on Wikipedia.


:- module coins.
:- interface.
:- import_module int, io.
:- type coin ---> quarter; dime; nickel; penny.
:- type purse ---> purse(int, int, int, int).
 
:- pred sum_to(int::in, purse::out) is nondet.
 
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module solutions, list, string.
 
:- func value(coin) = int.
value(quarter) = 25.
value(dime) = 10.
value(nickel) = 5.
value(penny) = 1.
 
:- pred supply(coin::in, int::in, int::out) is multi.
supply(C, Target, N) :- upto(Target div value(C), N).
 
:- pred upto(int::in, int::out) is multi.
upto(N, R) :- ( nondet_int_in_range(0, N, R0) -> R = R0 ; R = 0 ).
 
sum_to(To, Purse) :-
	Purse = purse(Q, D, N, P),
	sum(Purse) = To,
	supply(quarter, To, Q),
	supply(dime, To, D),
	supply(nickel, To, N),
	supply(penny, To, P).
 
:- func sum(purse) = int.
sum(purse(Q, D, N, P)) =
	value(quarter) * Q + value(dime) * D +
	value(nickel) * N + value(penny) * P.
 
main(!IO) :-
	solutions(sum_to(100), L),
	show(L, !IO),
	io.format("There are %d ways to make change for a dollar.\n",
                  [i(length(L))], !IO).
 
:- pred show(list(purse)::in, io::di, io::uo) is det.
show([], !IO).
show([P|T], !IO) :-
	io.write(P, !IO), io.nl(!IO),
	show(T, !IO).