11/22/2009

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

1 comment: