Saturday, November 22, 2008

Project Euler, problem 31

I solved another Project Euler problem today using constraints. The problem was to figure out how many ways you can combine English coins to form £2. Here's the constraint variant.

currency(List, Sum) :-
List = [N1,N2,N5,N10,N20,N50,N100,N200],
200 #= N1 + N2 * 2 + N5 * 5 + N10 * 10 + N20 * 20 + N50 * 50 + N100 * 100 + N200 * 200,
N1 #>= 0, N2 #>= 0, N5 #>= 0, N10 #>= 0,
N20 #>= 0, N50 #>= 0, N100 #>= 0, N200 #>= 0,
fd_labeling(List).

ways(Sum, Number) :-
findall(List, currency(List, Sum), Ways),
length(Ways).

Note that you have to explicitly inform the solver to use 0 or more coins of each denomination.

Edit: replaced "Sum" with 200 in the currency/2 predicate.

No comments: