Any ideas for this program?

[shummis]

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!

 

[joel76]

You should search on this forum, I think it's already in it !
Remember that you build 12 with 1 * 10 + 2, it may help.

 

[shummis]

I have looked all the threads in this forum but found nothing what would help me. If I missed one maybe could you give me a link? I still have no ideas.. Very grateful for any help.

 

[kahleen]

Maybe this link would help you:

http://www.tek-tips.com/viewthread.cfm?qid=1598839

It's not exactly what you need, but ...

 

[shummis]

Thank you.

% 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.

 

[kahleen]

First you need to generate either '+' signs or '-' signs, not just '+' signs. For that, you need to understand where '+' signs are generated.

The second and the third 'insert' rules do that:

insert([H | T], [H, '+' | T1]) :-
    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

value(L, X) :-
    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.

 

[shummis]

Thank you very much. I have done insert with "-" sign, but have some problems with 'value' predicate.

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

 

[kahleen]

Ok, you should not reproduce code and use the trial and error technique, maybe maybe it will work . You need to understand what happens.

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:

value(L, X) :-
    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:

value(L, X) :-
    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.

 

[shummis]

Thank kahleen very much. You did a great job. I am in a big respect of you. I wrote the third rule, it was very easy after your help. The program solves the problem correctly