Prolog - Arithmetic and lists.

Author

Arithmetic and lists.

razvan.savu@gmail.com

2007-05-30, 4:07 am

Hello. I have the following problem. Given a list of numbers and a
result, I must find the relation between the numbers in the list to
make the given value.

Ex: 10,2,6,4 and 2

10-2x6+4 = 2

Any ideas how to do this? Any help or pointers much appreciated.
Thanks.

Peter Van Weert

2007-05-31, 8:04 am

razvan.savu@gmail.com wrote:
> Hello. I have the following problem. Given a list of numbers and a
> result, I must find the relation between the numbers in the list to
> make the given value.
>
> Ex: 10,2,6,4 and 2
>
> 10-2x6+4 = 2
>

This problem, or at least one very similar, has already been discussed
on this newsgroup some time ago. You can still find in e.g. on Google
groups:

http://groups.google.com/group/comp...34b46a485bf64aa

Cheers,
Peter

Markus Triska

2007-06-01, 4:20 am

razvan.savu@gmail.com writes:

> Given a list of numbers and a result, I must find the relation
> between the numbers in the list to make the given value.
>
> Ex: 10,2,6,4 and 2
>
> 10-2x6+4 = 2

Consider using Reverse Polish notation for simplicity:

ns_expr_v([], [], 0).
ns_expr_v([N|Ns], Es, V) :-
permutation([N|Ns], Ns1), nev(Ns1, Ns, Es, [], V).

nev([], [], [], [V], V).
nev([N|Ns], Os, [N|Es], S, V) :- nev(Ns, Os, Es, [N|S], V).
nev(Ns, [_|Os], [O|Es], [A,B|S], V) :-
op_a_b_r(O, B, A, R), nev(Ns, Os, Es, [R|S], V).

op_a_b_r(Op, A, B, R) :- member(Op, [+,-,*]), E =.. [Op,A,B], R is E.
op_a_b_r(rdiv, A, B, R) :- B =\= 0, R is A rdiv B.

Example:

%?- ns_expr_v([10,2,6,4], Es, 2).
%@ Es = [10, 2, 6, 4, +, -, +] ; Es = [10, 2, 6, 4, +, rdiv, *] ;
%@ Es = [10, 2, 6, -, 4, -, +] ; Es = [10, 2, 6, -, +, 4, -] ;
%@ Es = [10, 2, 6, *, 4, -, -] ; Es = [10, 2, 6, *, -, 4, +] a
%@ Yes

You can convert such solutions to infix syntax like this:

rpn_to_infix([], 0).
rpn_to_infix([N|Ns], E) :- rpn_to_infix(Ns, [N], E).

rpn_to_infix([], [E], E).
rpn_to_infix([N|Ns], S, E) :-
( number(N) -> rpn_to_infix(Ns, [N|S], E)
; S = [A,B|Rest], E0 =.. [N,B,A], rpn_to_infix(Ns, [E0|Rest], E)
).

Example:

%?- ns_expr_v([10,2,6,4], Es, 2), rpn_to_infix(Es, E).
%@ Es = [10, 2, 6, 4, +, -, +], E = 10+ (2- (6+4)) ;
%@ Es = [10, 2, 6, 4, +, rdiv, *], E = 10* (2 rdiv (6+4)) ;
%@ Es = [10, 2, 6, -, 4, -, +], E = 10+ (2-6-4) ;
%@ Es = [10, 2, 6, -, +, 4, -], E = 10+ (2-6)-4 ;
%@ Es = [10, 2, 6, *, 4, -, -], E = 10- (2*6-4) ;
%@ Es = [10, 2, 6, *, -, 4, +], E = 10-2*6+4 a
%@ Yes

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/

Carlo Capelli

2007-06-01, 4:20 am

It's a so called 'generate and test' program.
Generation is performed by member/2, test by is/2.

ops(Numbers,Result,Expression) :-
ins(Numbers,Expression),
% writeln(Expression),
Result is Expression.

ins([A,B|C],Expression) :-
member(Op, [+,-,*,/]),
Expression =.. [Op,A,RestOfExpression],
ins([B|C],RestOfExpression).
ins([N],N).

You should further test for division by 0, or renounce to divisor!
Bye Carlo

<razvan.savu@gmail.com> ha scritto nel messaggio
news:1180506683.689180.327320@u30g2000hsc.googlegroups.com...
> Hello. I have the following problem. Given a list of numbers and a
> result, I must find the relation between the numbers in the list to
> make the given value.
>
> Ex: 10,2,6,4 and 2
>
> 10-2x6+4 = 2
>
> Any ideas how to do this? Any help or pointers much appreciated.
> Thanks.
>

Carlo Capelli

2007-06-01, 4:20 am

"Carlo Capelli" <carlo.capelli@rdbos.it> ha scritto nel messaggio
news:2jQ7i.1507$BU3.879@tornado.fastwebnet.it...
> It's a so called 'generate and test' program.
> Generation is performed by member/2, test by is/2.
>
> ops(Numbers,Result,Expression) :-
> ins(Numbers,Expression),
> % writeln(Expression),
> Result is Expression.
>
> ins([A,B|C],Expression) :-
> member(Op, [+,-,*,/]),
> Expression =.. [Op,A,RestOfExpression],
> ins([B|C],RestOfExpression).
> ins([N],N).
>
> You should further test for division by 0, or renounce to divisor!

I've (for the firts time) tried ISO exception handling: it fits the needs!

ops(Numbers,Result,Expression) :-
ins(Numbers,Expression),
% writeln(Expression),
catch(Result is Expression,Exc,writeln(Exc)).

> Bye Carlo
>
> <razvan.savu@gmail.com> ha scritto nel messaggio
> news:1180506683.689180.327320@u30g2000hsc.googlegroups.com...
>
>

Sponsored Links