zero sum game

[jjtolton]

The following code works, although I'm not convinced it's the most elegant way to approach the problem. However, as you can see in the output, there's a bigger problem -- the output continually appends zeros, making the answer incorrect, unless I use once/1. I have tried various methods to fix this, but they end up resulting in nontermination.

For example, if I modify the main predicate like so:

% ls1_ls2_sum(Ls1, Ls2, R): Ls1 and Ls2 are "reversed" polynomial lists, R the reversed polynomial list of the sum
% of polynomials Ls1 and Ls2.
ls1_ls2_sum(Ls1, Ls2, Rs) :-
        ls_base10_rev(Ls1, N0),
        ls_base10_rev(Ls2, N1),
        #N0 + #N1 #= #Sum0,
        ls_base10_rev(Rs, Sum0),
        % modification below -- fail on anything with a trailing zero
        reverse(Rs, Fwd), 
        Fwd=[Fwd0|_],
        Fwd0 #> 0.

?- ls1_ls2_sum([0,0,1],[0,0,1], Sum). 
%@    Sum = [0,0,2]
%@ ;     nontermination

%% but without those last 3 lines:
?- ls1_ls2_sum([0,0,1],[0,0,1], Sum). 
%@    Sum = [0,0,2]
%@ ;  Sum = [0,0,2,0]    undesirable!!! 
%@ ;  Sum = [0,0,2,0,0]    
%@ ;  Sum = [0,0,2,0,0,0]
%@ ;  Sum = [0,0,2,0,0,0,0]
%@ ;  ... .

I have tried using if_ in various ways, but the result is the same.
The only methods I have found so far that work are once/1 and !/0, (which are 👎 /0 if you know what I'm sayin').
I have a feeling there's some really fundamental logical principles going on here that I'm just overlooking, but my brain isn't seeing it.

Edit: I have also tried using failure-slices and debug:$/1 -- I've gathered enough to realize that the constraint solver is now searching for a new answer without a trailing zero, but this is impossible, which is why it will never terminate. What I can't figure out is how to make Prolog or clpz aware that it is impossible there could be any more meaningful answers and thus all choice points should be exhausted.

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   https://leetcode.com/problems/add-two-numbers/description/

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
 

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(debug)).

% ls_base10(ListOfIntegers, IntegerValue): Convert the list of integers, which describes the polynomial
% X_N*10^N + X_(N-1)*10^(N-1) + ... X_0*10^0, to the corresponding integer sum of the polynomial
% ls_base10(ListOfIntegers, IntegerValue, PlaceValue): PlaceValue used for calculation passing only
ls_base10([], 0).
ls_base10(Ls, Total) :-
        ls_base10(Ls, Total, _).
ls_base10([], 0, 0).
ls_base10([X|Xs], Total, N) :-
        #N0 #= #N - 1,
        #Total #= #Total0 + #X * 10 ^ #N0,
        X in 0..9,
        ls_base10(Xs, Total0, N0).

% ls_base10_rev(ReversedListOfIntergers, IntegerValue): as ls_base10/2, but `Ls` is reversed
% (per problem requirements)
ls_base10_rev(Ls, Total) :-
        reverse(Ls, Sl),
        ls_base10(Sl, Total).

?- once(ls_base10_rev(Ls, 123)).


% ls1_ls2_sum(Ls1, Ls2, R): Ls1 and Ls2 are "reversed" polynomial lists, R is the integer sum
% of the addition of the polynomials
ls1_ls2_sum(Ls1, Ls2, R) :-
        ls_base10_rev(Ls1, N0),
        ls_base10_rev(Ls2, N1),
        #N0 + #N1 #= #Sum0,
        ls_base10_rev(R, Sum0).

?- once(ls1_ls2_sum([2,4,3],[5,6,4], Sum)).
%@    Sum = [7,0,8].

?- ls1_ls2_sum([2,4,3],[5,6,4], Sum).
%@    Sum = [7,0,8]
%@ ;  Sum = [7,0,8,0]
%@ ;  Sum = [7,0,8,0,0]
%@ ;  Sum = [7,0,8,0,0,0]
%@ ;  ... .


?- ls1_ls2_sum([9,9,9,9,9,9,9], [9,9,9,9], Sum).
%@    Sum = [8,9,9,9,0,0,0,1]
%@ ;  Sum = [8,9,9,9,0,0,0,1,0]
%@ ;  Sum = [8,9,9,9,0,0,0,1,0,0]
%@ ;  Sum = [8,9,9,9,0,0,0,1,0,0,0]
%@ ;  ... .

[bakaq]

You can limit the length of the list before. This helps with non-termination at least:

% In this case the sum can have at most 4 digits.
?- N in 3..4, label([N]), length(Sum, N), ls1_ls2_sum([2,4,3],[5,6,4], Sum).
   N = 3, Sum = [7,0,8]
;  N = 4, Sum = [7,0,8,0]. % Still need to prune this out.

[jjtolton]

Good point, I suppose if I were clever I could figure out how to determine how many coefficients the polynomial list representing the place values would have and use that as a limit.