Given a list of numbers L, use operations +,-,*,/ to obtain a result of Result. Use each number of L exactly one time.
Code:
j24([X],R,H) :- !, X =:= R,H=X.
j24(L,R,H) :- select(X1,L,L1), x2(X1,Op,X2,R),
j24(L1,X2,H1),H =..[Op,X1,H1],tj24(Op,X1,H1).
tj24(Op,X1,H1) :- member(Op,['+','*']),
H1 =..[Op,Y1,_],integer(X1),integer(Y1),!,X1 =< Y1.
tj24(_,_,_) :- true.
x2(X1,'+',X2,R) :- X2 is R - X1, X1 =< X2.
x2(X1,'-',X2,R) :- X2 is X1 - R.
x2(X1,'*',X2,R) :- X1 =\= 0, X2 is R / X1, X1 =< X2.
x2(X1,'/',X2,R) :- R =\= 0, X2 is X1/R.
Example:
?- j24([2,5,7,11,20],280,L).
L = 5+11*(7+(20-2)) ;
L = 5+11*(7-(2-20)) ;
L = 5+11*(20-(2-7)) ;
L = 5*(20+2*(7+11)) ;
L = 7-(2-11*(5+20)) and so on.
A little more complex:
?- j24([2,3,4,7,11,13,17,23,27,31],7239,Solution).
Solution = 2+(3+(11+31*(7-(17-27/(4/(13+23))))))
When L = [2,3,4,7,11,13,17,23,27,31,37,43,47] and Result is 1117239 one solution is
2+(3+(4+(27+(47+23*(43+13*(37+7*(11*(17+31))))))))
Edited: I made a small change to prune solutions:
x2(X1,'+',X2,R) :- X2 is R - X1, X1 =< X2.
x2(X1,'-',X2,R) :- X2 is X1 - R,X2 > 0.
x2(X1,'\*',X2,R) :- X1 =\= 0, X2 is R / X1, X1 =< X2.
x2(X1,'/',X2,R) :- integer(R),R =\= 0, 0 is X1 mod R, X2 is X1/R.
The program does not compute all the solution. When the parameter Result is relatively small is easier to obtain a problem with many solution, so the algorithm is fast.
The Prolog program computes a solution in one or two seconds, how would be a similar python program to solve this problem in less than 10 lines?
The Prolog program computes a solution in one or two seconds, how would be a similar python program to solve this problem in less than 10 lines?