2
\$\begingroup\$

The problem is adding two lists as numbers L1 = [1,9,9] and L2 = [0,9,9]:

?- sum([1,9,9],[0,9,9], Lo).  
Lo = [2,9,8]

But I also wanted to add this:

?- sum([8,1,9],[1,8,2],Lo).
Lo = [1, 0, 0, 1].

I used the backtracking method I've learned:

link([],L,L).
link([Head|Tale],L2,L3):- link(Tale,L2,L), L3=[Head|L].

inve([],[]):-!.
inve([X|Xs],L):- inve(Xs,L2), link(L2,[X],L).


sum(L1,L2,L3):- inve(L1,LI1),inve(L2,LI2), sumID(LI1,LI2,L), inve(L,[Li|LIs]),
                     Li > 9, Li2 is Li-10 , L3 = [1,Li2|LIs] ,!.
sum(L1,L2,L3):- inve(L1,LI1),inve(L2,LI2), sumID(LI1,LI2,L), inve(L,L3),!.


sumID([],[],[]):- !.
sumID([X|[Xs|Xss]],[Y|Ys],[L|Ls] ):- XY is X+Y , XY > 9 , Head is XY - 10,
                                  L = Head, Xs1 is Xs + 1,
                              sumID([Xs1|Xss], Ys, LTail) ,Ls = LTail,!.

sumID([X|Xs],[Y|Ys],[L|Ls]):- L is X+Y, sumID(Xs,Ys,LTail),
                           Ls = LTail.

A friend told me to invest list and add from *Left to Right*, and later invest the final list. How can I improve this solution in order not to be so long? I'd appreciate a better idea to solve this problem, too. I made it in more than 2 hours and in the exam this is supposed to be in 20min.

\$\endgroup\$
1
\$\begingroup\$

When describing lists, always consider using DCGs. In this case, try for example:

sum(Xs0, Ys0, Ls) :-
    reverse(Xs0, Xs),
    reverse(Ys0, Ys),
    phrase(sum(Xs, Ys, 0), Ls0),
    reverse(Ls0, Ls).

sum([], [], Carry) -->
    (   { Carry > 0 } -> [Carry]
    ;   []
    ).
sum([X|Xs], [Y|Ys], Carry0) -->
    { N0 is X + Y + Carry0,
      (  N0 > 9 ->  N is N0 - 10, Carry = 1
      ;  N = N0, Carry = 0
      ) },
    [N],
    sum(Xs, Ys, Carry).

Exampe queries and their results:

?- sum([1,9,9], [0,9,9], Ls).
Ls = [2, 9, 8].

?- sum([8,1,9], [1,8,2], Ls).
Ls = [1, 0, 0, 1].
\$\endgroup\$
  • \$\begingroup\$ About DCGs, I know what you mean by ''always'' ,but can you translate into normal definite clauses in Prolog without "{ } , --> ". For now, is not required DCGs, i'd appreciate normal clauses because I don't understand it very well. \$\endgroup\$ – YonCho Apr 3 '15 at 5:59
  • \$\begingroup\$ Just let the Prolog system do this for you: In SWI-Prolog, use ?- listing(sum//3). to get the expanded version. To use the expanded version in your program, copy&paste it instead of the DCG version, and write sum(Xs, Ys, 0, Ls0, []) instead of phrase(sum(Xs, Ys, 0), Ls0). \$\endgroup\$ – mat Apr 3 '15 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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