Any ideas for this program?
Any ideas for this program?
(OP)
Hello,
I am quite new to prolog and need to write this program, but have no ideas. I would be very grateful for any help.
"Add signs"
The list of the digits (1-9) is given. You need to add operation signs (+, -), that expression of the arithmetic would be the given number (digits in a row makes the number)
add_signs([1,2,3,4,5,6,7,8,9], 4, result).
result is 12-3+45-67+8-9 = 4
Thank you in advance!
I am quite new to prolog and need to write this program, but have no ideas. I would be very grateful for any help.
"Add signs"
The list of the digits (1-9) is given. You need to add operation signs (+, -), that expression of the arithmetic would be the given number (digits in a row makes the number)
add_signs([1,2,3,4,5,6,7,8,9], 4, result).
result is 12-3+45-67+8-9 = 4
Thank you in advance!
RE: Any ideas for this program?
Remember that you build 12 with 1 * 10 + 2, it may help.
RE: Any ideas for this program?
RE: Any ideas for this program?
It's not exactly what you need, but ...
RE: Any ideas for this program?
% insert(L, R) - inserts any number of plus signs between
% elements in L, resulting R
insert([], []).
insert([H | T], [H, '+' | T1]) :-
T \= [],
insert(T, T1).
insert([H | T], [H | T1]) :-
insert(T, T1).
% decimal(L, X, N) - if L contains no '+' signs, computes
% in N the decimal value of L. X should be 0 at first call
decimal([], N, N).
decimal([H|T], Current, X) :-
Current1 is 10 * Current + H,
decimal(T, Current1, X).
% value(L, X) - computes in X the value of list L; there
% can be '+' signs in L, the computation is aware of them
value(L, X) :-
\+member('+', L),!,
decimal(L, 0, X).
value(L, X) :-
append(L1, ['+' | L2], L),!,
decimal(L1, 0, A),
value(L2, B),
X is A + B.
% writelist(L) - writes list L without the '[' and ']'
writelist([]).
writelist([H|T]) :-
write(H),writelist(T).
% solve(List, R) - main predicate
solve(List, R) :-
insert(List, List1),
value(List1, R),
writelist(List1),
nl.
solve([1,2,3,4], 28).
1+23+4
This code solves the problem, but just with plus sign. Where do I need to supplement the code to solve the task with the minus sign?
Thanks.
RE: Any ideas for this program?
The second and the third 'insert' rules do that:
CODE
T \= [],
insert(T, T1).
insert([H | T], [H | T1]) :-
insert(T, T1).
The second rule generates a '+' sign. The third rule doesn't generate a '+' sign. So together, at each step they generate the two available possibilities: either put '+' sign <there>, or don't put it. Now you have to add an additional rule between the two that allows for '-' signs to be added, so you will have 3 possibilities: '+', '-' or none.
After you do that, I recommend you test the 'insert' predicate in isolation, like this:
?- insert([1, 2, 3, 4], Result).
and press ';' after each solution to see that all possibilities are generated
Once you have the lists generated, you need to compute values and do the operations. With only '+' signs it's easy between addition is associative. Subtraction is not.
For example: 2 + 3 + 4 = 2 + (3 + 4)
But when you try with subtraction: 2 - 3 - 4 is not equal with 2 - (3 - 4)
The list value is computed by the 'value' predicate
?- value([1, '+', 2], R).
R = 3
CODE
append(L1, ['+' | L2], L),!,
decimal(L1, 0, A),
value(L2, B),
X is A + B.
What 'value' does is it uses 'append' to determine the first place in the list where a '+' sign is found. If such a sign is found, it's easy to determine L1 and L2 such that L1 appended with a '+' and with L2 will result in the whole list. So L1 is the list of digits at the left of '+' and L2 is the list of digits and possible other signs at the right of the '+'. This approach will not work with '-'. What you need to do is determine the last place in the list where a '-' or '+' sign is found and then perform the operation.
RE: Any ideas for this program?
I wrote:
value(L, X) :-
((member('+', L)) -> append(L1, ['+' | L2], L), decimal(L1, 0, A), value(L2,B), X is A + B);
((member('-', L)) -> append(L1, ['-' | L2], L), decimal(L1, 0, A), value(L2,B); decimal(L, 0, X));
X is A + B.
It doesn't work. Can anyone help me?
Thanks ;)
RE: Any ideas for this program?
Your 'value' predicate receives a list of digits and signs, either plus-es or minus-es. So your list will look something like this: [1, '+', 2, 3, '-', 4, '-', 5, 6, '+' 7]
The 'value' predicate should traverse this list and compute the expression 1 + 23 - 4 + 56 + 7. You can use most of the code that already exists in the 'value' predicate, for example whenever you have a sublist like [5, 6] that doesn't have any operators in it, only digits, the 'value' predicate will call 'decimal' to determine the value is 56. You already have that. What you don't have is a way to perform addition when a '+' sign is encountered and perform subtraction where a '-' sign is encountered.
First idea that comes to mind is to determine a '+' in the list above. You do that by calling append(L1, ['+' | L2], L) where L is the list above. If this append succeeds, L1 and L2 will be the sublists from the left and from the right of that '+'. Now you can call 'value' on L1, 'value' on L2, obtain an integer from each call and add them.
This only works for addition. For subtraction this idea works but only if your '-' sign is the last sign in the list. This is because your minus sign is left associative
3 - 2 - 1 = (3 - 2) - 1 ... correct
3 - 2 - 1 = 3 - (2 - 1) ... incorrect
For the plus sign, this problem never appears.
So if you have L = [3, '-', 2, '-', 1], you need to locate the last '-' sign, then you would have L1 = [3, '-', 2] and L2 = [1]. Now you can safely evaluate L1 to a number and L2 to another number, subtract the numbers and have the correct value.
I'll give you a quick fix of the 'value' predicate. It's not the best solution but I think it's close to the one you already have, so I believe you will understand it easier. I'll write just 2 rules for your 'value' predicate, and you will have to write the third rule yourself :)
First rule:
CODE
not(member('+', L)),
not(member('-', L)), !,
decimal(L, 0, X).
If your list contains no '+' and no '-', then we're happy, we can evaluate it easy using decimal.
Second rule:
CODE
append(L1, ['+' | L2], L),
not(member('-', L2)),
not(member('+', L2)),
!,
value(L1, A),
decimal(L2, 0, B),
X is A + B.
We split the list in L1 and L2 such that a '+' sign exists in between, but we also make sure that L2 contains no '+' and no '-'. This is how we make sure the '+' sign between L1 and L2 is the last sign from the whole list. After we have L1 and L2, we evaluate L1 to A using 'value' because it may contain other operators, we evaluate L2 to B using 'decimal' because we made sure L2 contains no operators, and then we add A and B to obtain X, the value of the entire list.
You have to add one more 'value' rule that deals with the '-' sign.
RE: Any ideas for this program?