Arithmetic puzzle
Rap...@gmail.com
to insert arithmetic signs (operators) between numbers to get right
equations. Now I have similar task, I need to put plus or minus sign
between different digits to get given answer, lets say I have such
query:
?- find([1,2,3,4,7], 30).
30 = 1 + 2 + 34 - 7
Yes, if you don't put any sign between two digits, you get two digit
number. It can be three digit, even whole given list can be one number,
for example:
?- find([1,2,3,4], 1234).
1234 = 1234.
So, I'm thinking about multiway tree, root is first digit, first node
from left is second digit, and between root and its child there is
nothing so it makes two digit number, middle node has second digit, and
between root and this child, there is plus sign, and another node for
the minus sign. And a problem I have, that I don't know ho to implement
that... Can anybody help me with this? Maybe there is a better solution
than multiway tree. Thanks in advance;)
Jussi Piitulainen
> Hello guys, I think a lot of you know arithmetic puzzle, where you need
> to insert arithmetic signs (operators) between numbers to get right
> equations. Now I have similar task, I need to put plus or minus sign
> between different digits to get given answer, lets say I have such
> query:
> ?- find([1,2,3,4,7], 30).
> 30 = 1 + 2 + 34 - 7
>
> Yes, if you don't put any sign between two digits, you get two digit
> number. It can be three digit, even whole given list can be one number,
> for example:
> ?- find([1,2,3,4], 1234).
> 1234 = 1234.
>
> So, I'm thinking about multiway tree, root is first digit, first
You know how arithmetic expressions in Prolog are tree-structured
terms already, do you? Those (-)/2 and (+)/2 in there are functors.
You could just declare a new operator for concatenation, or maybe use
an existing non-arithmetic operator for that, like (.)/2, so that your
example would be ((1 + 2) + [3|4]) - 7, say. That is a binary tree
with your numbers as leaves. (As usual, [3|4] = .(3,4)).
I don't know if there is a way to extend is/2, but it is an easy
exercise to implement a similar evaluator with standard rules for a
handful of standard operators and an extra rule to evaluate [3|4] as
10*3 + 4.
russell kym horsell
> Hello guys, I think a lot of you know arithmetic puzzle, where you need
> to insert arithmetic signs (operators) between numbers to get right
> equations. Now I have similar task, I need to put plus or minus sign
> between different digits to get given answer, lets say I have such
> query:
> ?- find([1,2,3,4,7], 30).
> 30 = 1 + 2 + 34 - 7
I think the simplest stategy is to create a plan (with an
accumulation param) as a "find" helper predicate recurses.
I.e. to find plan to convert X,Y|Restofdigits into Result (number)
you can try to append X to next digit Y, put + sign between X and next digit Y,
or put - sighn between X and next digit Y. So "find" will be a predicate
with at leat 3 choices. When it finally runs out of digits it will
have the plan in its accumulation param. The plan can be as simple as
a Prolog expression -- which can then be evaluated (e.g. wih "is")
numerically compared against Result.
This solution may be vague due to eggnog overload. Sorrick.
arv832
find(List,Res) :-
signs(List,Sum,SignVars),
SignVars in [-1,1],
Res ?= Sum.
signs([],0,[]).
signs([X|XT],(S * X + SumTail),[S|ST]) :-
signs(XT,SumTail,ST).
arv832
ronaldo
I am quite novice in prolog and I have been trying to do it by
myself while following this thread. This is the solution I have
elaborated:
------------------------------------------------------------------------------------
% Visual representations of operators
operator(sum,' + ').
operator(rest,' - ').
operator(con,'').
% Definition of every operator used
sum(N1,N2,R) :- R is N1+N2.
rest(N1,N2,R):- R is N1-N2.
con(N1,N2,R) :- R is N1*10+N2.
% Predicates for inserting operators between numbers
insert_op(L, N, [N|[sum|L]]).
insert_op(L, N, [N|[rest|L]]).
insert_op(L, N, [N|[con|L]]).
% This is used for printing the resulting list
writeOp([]).
writeOp([O|LT]):-operator(O,OP), !, write(OP), writeOp(LT).
writeOp([L|LT]):-write(L), writeOp(LT).
% Rules for calculating the arithmetic result of the generated
operation
calculate([N1|[OP|[N2|LT]]], R) :-
!, call(OP,N1,N2,RES),
calculate([RES|LT], R).
calculate([R], R).
% Rules for generating every possible operation with numbers
generate([],[]).
generate([L|LT],LOP):-
generate(LT,O),
( O \= []
-> insert_op(O, L, LOP)
; LOP = [L]
).
% Find rule which generates operations until it finds a correct one
find(L,R) :-
generate(L,OP),
calculate(OP, R),
write(R), write(' = '), writeOp(OP).
------------------------------------------------------------------------------------
Could you please give me constructive comments?
Many Thanks in advance :)
bart demoen
> Hello guys,
>
> I am quite novice in prolog and I have been trying to do it by
> myself while following this thread. This is the solution I have
> elaborated:
...
>
> Could you please give me constructive comments?
> Many Thanks in advance :)
Maybe we can first agree on what to expect - the query
?- find([1,2,3],4).
fails for your program, while my program prints as answers
4 = 2 - 1 + 3
Yes ;
4 = 2 + 3 - 1
Yes ;
4 = 3 - 1 + 2
Yes ;
4 = 3 + 2 - 1
Yes ;
No more !
Your generate uses the numbers only in the order of the inputlist.
Did you intend the failure ?
Cheers
Bart Demoen
Jussi Piitulainen
> operator(sum,' + ').
...
> sum(N1,N2,R) :- R is N1+N2.
...
> insert_op(L, N, [N|[sum|L]]).
...
I think it's better to build arithmetic expressions than lists,
possibly modified to have lists of digits as an expression type.
For one thing, you would learn something about Prolog terms and
operators. For another, arithmetic expressions have a nice written
representation already.
> calculate([N1|[OP|[N2|LT]]], R) :-
> !, call(OP,N1,N2,RES),
> calculate([RES|LT], R).
> calculate([R], R).
It's better to write [N1,OP,N2|LT] than [N1|[OP|[N2|LT]]].
The power of call/N is not needed here. You could write a single
predicate to evaluate all your operators:
eval(sum, N1, N2, R) :- R is N1 + N2.
...
However, if you used (3 + (14 + 1)) in place of [3,sum,14,sum,1],
you could just hand it to is/2 for evaluation: R is E.
And if you used something like (3 + (con(1,4) + 1)), you could
easily write your own version of is/2 so:
calculate(N, N) :-
number(N).
calculate(L + R, V) :-
calculate(L, M),
calculate(R, N),
V is M + N.
calculate(con(E,G), V) :-
% we should be careful about con(3,con(1,4)), though:
% don't want 3*10 + 1*10 + 4 but 3*100 + 1*10 + 4;
% oops; one way is to allow only con(con(3,1),4)
% when building the expression.
...
This kind of recursion follows the structure of the data, which is
usually nice. Try some expressions:
(L + R) = (3 + 1 + 4 - 1 + 5 + 9)
(L + R) = (one + two)
Incidentally, I wrote my own solution, and it turned out rather
nice when I simply either treated a digit sequence as a possible
expression (with a special rule to evaluate it but not using any
special concatenation operator after all) or split it in two,
treating the parts recursively to get L and R and making L + R and
L - R out of those.
ronaldo
about prolog is even less than I thought :).
Many thanks for your interest. I will think about your propositions to
start learning to think in prolog.
Bart: It was intended. I thought the problem was just to introduce
signs between the numbers, without changing their order. Of course, if
you find solutions with numbers in a different order, you are solving a
more general case. Really interesting :).
Peter Van Weert
I wrote a small program myself (cf attachment). I have been playing with
a bit, so the version attached is a tiny bit more general then the
original problem, and will find somewhat more solutions. But it is easy
enough to play with different settings: you can disallow the extra
operators, disallow permutations, disallow the adding of sign operators,
etc. by some simple changes to the program.
Cheers,
Peter
bart demoen
> find(Nums, Outcome, Expression) :-
> permutation(Nums, Perm),
> generate(Perm, Expression),
> Outcome is Expression.
>
> generate(Ns, Expr) :- generate_(Ns, Expr).
> generate(Ns, -Expr) :- generate_(Ns, Expr).
>
> generate_([N], N).
> generate_([N|Ns], Expr) :-
> operator(Op),
> generate(Ns, ExprX),
> ( Expr =.. [Op,N,ExprX] ; Expr =.. [Op,ExprX,N] ).
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Since you already permute the input, this disjunction is just generating
duplicate answers, right ?
Cheers
Bart Demoen
Richard Szopa
On Dec 11, 10:19 pm, Peter Van Weert <Peter.VanWe...@cs.kuleuven.be>
wrote:
> find(Nums, Outcome, Expression) :-
> permutation(Nums, Perm),
[...]
> operator(/).
In some situations your program generates a division by zero error:
?- find([1,2,3,5], 1235, E).
ERROR: //2: Arithmetic: evaluation error: `zero_divisor'
I would probably suffice if your predicate caught it and then failed.
Anyway, I couldn't resist the temptation of writing my own program
solving the puzzle ;-)
expression --> number.
expression --> number, op, expression.
op --> [+].
op --> [-].
op --> [*].
op --> [/].
op --> ['']. % concatenation
number --> [1].
number --> [2].
number --> [3].
number --> [4].
number --> [5].
number --> [6].
number --> [7].
number --> [8].
number --> [9].
% put gaps between the numbers for the operators.
prepare_expression([X, Y], [X, _, Y]).
prepare_expression([H|T],[H, _|Rest]) :-
prepare_expression(T, Rest).
list_to_term(L, T) :- % is there anything built-in that does this?
concat_atom(L, A),
term_to_atom(T, A).
arithmetic_puzzle(Numbers, Result, ToEval) :-
permutation(Numbers, NumbersPerm),
prepare_expression(NumbersPerm, Expression),
expression(Expression, []),
list_to_term([Result, =:=|Expression], ToEval),
call(ToEval).
Any comments?
Cheers,
-- Richard
Peter Van Weert
Not quite. If we do not have this disjunction, the first operand can
never be an expression. So answers like:
?- find([1,2,3], 2, X).
...
X = (1+3)/2 ;
X = (3+1)/2 ;
...
are excluded. Of course, this is only interesting if you have
non-commutative operators, like /.
Cheers,
Peter
Peter Van Weert
In a way you do not add parentheses, so you do not get answers like:
?- find([1,2,3], 2, X).
...
X = (1+3)/2 ;
X = (3+1)/2 ;
...
This is also how you 'avoid' the division by zero at first glimpse (also
by not including zero as a number of course). You will never get things
like x / (y - y).
Cheers,
Peter
Richard Szopa
puzzle (i.e. allowing bracket constructions). While trying to do it, I
managed to make better (or at least shorter) the old predicate :-).
As always, comments are welcome.
% the old problem, better
expression([X])--> [X].
expression([H|T]) --> [H], op, expression(T).
op --> [+].
op --> [-].
op --> [*].
op --> [/].
op --> ['']. % concatenation
arithmetic_puzzle(Numbers, Result, ToEval) :-
permutation(Numbers, NumbersPerm),
expression(NumbersPerm, Expression, []),
concat_atom([Result, =:=|Expression], At),
term_to_atom(ToEval, At),
call(ToEval).
% Peters extension: we allow bracket constructions
number([X]) --> [X].
number([H|T]) --> [H], number(T).
expr_brackets(X) --> number(X).
expr_brackets([H|T])--> {append(Left, Right, T),
Right\=[]}, ['('],
expr_brackets([H|Left]), [')'], opbr, ['('],
expr_brackets(Right), [')'].
opbr --> [+].
opbr --> [-].
opbr --> [*].
opbr --> [/].
arithmetic_puzzle_2(Numbers, Result, ToEval) :-
permutation(Numbers, NumbersPerm),
expr_brackets(NumbersPerm, Expression, []),
concat_atom([Result, '=:= '|Expression], At),
term_to_atom(ToEval, At),
catch(ToEval, error(evaluation_error(zero_divisor),_), fail). %
we catch division by zero
The only thing I'm not sure is whether my grammar for making
bracket-expressions is the best possible. Could this be done without
using append/3?
Cheers,
-- Richard
Markus Triska
> % Peters extension: we allow bracket constructions
>
> number([X]) --> [X].
> number([H|T]) --> [H], number(T).
>
> expr_brackets(X) --> number(X).
> expr_brackets([H|T])--> {append(Left, Right, T),
> Right\=[]}, ['('],
> expr_brackets([H|Left]), [')'], opbr, ['('],
> expr_brackets(Right), [')'].
Given the way expr_brackets/3 is used in your program, you can write:
expr_brackets(Es) --> Es.
expr_brackets(Es) -->
{ append([L|Ls], [R|Rs], Es) },
['('], expr_brackets([L|Ls]), [')'],
opbr,
['('], expr_brackets([R|Rs]), [')'].
All the best,
Markus.
Richard Szopa
> expr_brackets(Es) --> Es.
> expr_brackets(Es) -->
> { append([L|Ls], [R|Rs], Es) },
> ['('], expr_brackets([L|Ls]), [')'],
> opbr,
> ['('], expr_brackets([R|Rs]), [')'].
Thank you! I wouldn't have thought about it. Your article made some
gears in my head move and now I think I understand DCG in Prolog a bit
better.
-- Richard