Countdown with Prolog
I was just going through G. Hutton's Haskell code for the (simplified) countdown problem which I plan to mention in a class on functional programming. The aforementioned code is discussed in the wonderful book "Programming in Haskell". The development of the brute-force model looks verbose and detouring however. (This is probably because the problem serves some pedagogical purposes.) Here is a simple Prolog-based solution. It is much faster than the brute-force Haskell-based solution, also because some optimizations are naturally achieved by a straightforward solution. I am sure others have tried this because it is so strikingly obvious.
Suppose you want to compute a given number X, by applying the arithmetic operations addition, subtraction, multiplication, and division to numbers picked from a given sequence of positive natural numbers, while using any candidate at most once, and all intermediate results must be positive natural numbers again.
For instance: 765 = (25-10)*(50+1)
?- solve([1,10,25,50],765,Ts).
Ts = [ (25-10)* (1+50), (25-10)* (50+1), (1+50)* (25-10), (50+1)* (25-10)].
% Solutions Ts for countdown problem with numbers Ns, result X solve(Ns,X,Ts) :- findall(T,( sublist(L,Ns), permutation(L,P), compute(P,T), X is T ),Ts). % Generate all sublists of a given list sublist([],[]). sublist(Z,[H|T]) :- sublist(Y,T), ( Z = Y ; Z = [H|Y] ). % Generate all permutations of a given list permutation([],[]). permutation([H|T1],L) :- permutation(T1,T2), append(T2a,T2b,T2), append(T2a,[H|T2b],L). % Complete sequences of numbers into arithmetic expressions compute([R],R). compute(As,T) :- As = [_,_|_], append(As1,As2,As), As1 = [_|_], As2 = [_|_], compute(As1,T1), compute(As2,T2), ( T = T1 + T2 ; T = T1 - T2 ; T = T1 * T2 ; T = T1 / T2 ), R is T, R > 0, integer(R).
Regards,
PF
Very nice, thank you!
ReplyDeleteRavi