I saw this ECLiPSe solution to the problem mentioned in this XKCD comic. I tried to convert this to pure Prolog.
go:-
Total = 1505,
Prices = [215, 275, 335, 355, 420, 580],
length(Prices, N),
length(Amounts, N),
totalCost(Prices, Amounts, 0, Total),
writeln(Total).
totalCost([], [], TotalSoFar, TotalSoFar).
totalCost([P|Prices], [A|Amounts], TotalSoFar, EndTotal):-
between(0, 10, A),
Cost is P*A,
TotalSoFar1 is TotalSoFar + Cost,
totalCost(Prices, Amounts, TotalSoFar1, EndTotal).
I don't think that this is the best / most declarative solution that one can come up with. Does anyone have any suggestions for improvement? Thanks in advance!
Your generate-and-test approach should be intelligible to any Prolog programmer with more than a few days experience. Here are some minor tweaks:
go(Amounts) :-
Prices = [580, 420, 355, 335, 275, 215],
totalCost(Prices, Amounts, 0, 1505),
write(Amounts), nl.
totalCost([], [], Total, Total).
totalCost([P|Prices], [A|Amounts], SoFar, Total):-
Upper is (Total-SoFar)//P,
between(0,Upper,A),
SoNear is SoFar + P*A,
totalCost(Prices, Amounts, SoNear, Total).
I changed go/0 to go/1 so that the Prolog engine will backtrack and produce all the solutions (there are two). The calls to length/2 could be omitted because totalCost/4 does the work of building list Amounts to have equal length with Prices. I used write/1 and nl/0 to make it a little more portable.
In totalCost/4 I shortened some of the variable/argument names and indulged in a slightly jokey name for the accumulator argument. The way I imposed the check that our accumulator doesn't exceed the desired Total uses your original call to between/3 but with a computed upper bound instead of a constant. On my machine it reduced the running time from minutes to seconds.
Added: I should mention here what was said in my comment above, that the menu items are now ordered from most expensive to least. Using SWI-Prolog's time/1 predicate shows this reduces the work from 1,923 inferences to 1,070 inferences. The main improvement (in speed) comes from using computed bounds on A rather than range 0 to 10 for every item.
time((go(A),false)).
Note the extra parentheses around the compound goal, as otherwise SWI-Prolog thinks we are calling an undefined time/2 predicate.