current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question

1 Answer 1

up vote 1 down vote

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].
share|improve this answer
    
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. –  YonCho Apr 3 at 5:59
    
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). –  mat Apr 3 at 10:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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