3

The task is to find if there exists at least one combination of numbers from given list and operators to obtain target number. No usemodule allowed numbers([3,4,1,2], 7) → true. (cause 4 + 3 = 7) numbers([1,7,7,3], 24) → true. (cause (7 - 3) * (7 - 1) = 24)

Tried member if target is already in the list. But lost further

1
  • 1
    you didn't specify the allowed operators Dec 24, 2022 at 10:42

2 Answers 2

3

Building upon https://professor-fish.blogspot.com/2009/11/countdown-with-prolog.html

solve_countdown(Ns, SumWanted, TsUniq) :-
    findall(T, (
        any_comb(Ns, Sub),
        num_combs(Sub, T),
        SumWanted is T
    ), Ts),
    sort(Ts, TsUniq).

any_comb(_, []).
any_comb([H|T], [E|Comb]) :-
    select(E, [H|T], Lst0),
    any_comb(Lst0, Comb).

num_combs([N], N).
num_combs(As, T) :-
    split_list_in_2(As, As1, As2),
    num_combs(As1, T1),
    num_combs(As2, T2),
    % Break symmetry, since 5+2 is same as 2+5
    (   T1 @=< T2,
        (   T = T1 + T2
        ;   T1 > 1, T = T1 * T2
        )
    ;   T = T1 - T2
    ;   T = T1 / T2
    ),
    R is T,
    integer(R),
    R @> 0.

split_list_in_2([H1, H2|T], [H1|Start], Remainder) :-
    split_list_in_2_(T, H2, Start, Remainder).
    
split_list_in_2_(L, H2, [], [H2|L]).
split_list_in_2_([H|T], H2, [H2|Start], Remainder) :-
    split_list_in_2_(T, H, Start, Remainder).

Result in swi-prolog:

?- time(solve_countdown([1,7,7,3], 24, Ts)).
% 10,996 inferences, 0.002 CPU in 0.002 seconds (99% CPU, 5236642 Lips)
Ts = [3*(1+7), (7-1)*(7-3)].

select/3 code is here.

2

Squeezing the lemon. I get a slightly faster version. The logic replicates this paper: https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf But adds forward checking:

% solve(+Integer, -Term, +Integer, +List, -List)
solve(1, N, N, P, Q) :- !, select(N, P, Q).
solve(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve2(I, E, A, P, H),
   forward(E, A, F, B, G, N),
   solve(L, F, B, H, Q).

forward(E, A, F, B, E+F, N) :- N > A, B is N-A, A =< B.
forward(E, A, F, B, E-F, N) :- A > N, B is A-N.
forward(E, A, F, B, E*F, N) :- N mod A =:= 0, B is N div A, A =< B, A =\= 1.
forward(E, A, F, B, E/F, N) :- A mod N =:= 0, B is A div N, B =\= 1.

% solve2(+Integer, -Term, -Integer, +List, -List)
solve2(1, N, N, P, Q) :- !, select(N, P, Q).
solve2(K, G, N, P, Q) :-
   J is K-1,
   between(1, J, I),
   L is K-I,
   solve2(I, E, A, P, H),
   solve2(L, F, B, H, Q),
   combine(E, A, F, B, G, N).

combine(E, A, F, B, E+F, N) :- A =< B, N is A+B.
combine(E, A, F, B, E-F, N) :- A > B, N is A-B.
combine(E, A, F, B, E*F, N) :- A =< B, A =\= 1, N is A*B.
combine(E, A, F, B, E/F, N) :- B =\= 1, A mod B =:= 0, N is A div B.

Example run with SWI-Prolog 9.1.4:

% time((between(1,6,N), solve(N, E, 999, [1,3,5,10,25,50], _), fail; true)).
% % 2,618,953 inferences, 0.234 CPU in 0.242 seconds (97% CPU, 11174199 Lips)
% true.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.