prolog - Checking equal digits of numbers between lists?

Question

What would be an efficient way to check how many equal ending digits have numbers between lists in prolog?

For example we have Lista = [4432,2345,3243] and Listb = [3345,3232].

In these two lists we have 4432 and 3232 which have 2 same ending digits and 3345 , 2345 which have 3 same ending digits. 3243 , 3232 have the same 2 starting digits but I don't count this as valid. I have solved this problem in the slowest way , by checking each number of Lista with each number of Listb, but this is very slow. How can I solve this problem more efficiently?

---

Edit 1: I applied some changes to the answer code I managed to find the same digits and the subtree remaining , however I cannot combine them in order to find exactly the numbers that the element of the one list has the same digits with them. Can you help me proceed?

same_ending(Tree, N /*4904*/, N-Len-Last) :-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, [], Fin, 0, Lens),
  pow2(Lens, Res1),
  Res is Res1-1,
  Len = Res,
  Last = Fin.

same_ending1([], _, Curr, Fin, Len, Len).
same_ending1([Dig|Digs], Tree, Curr, Fin, Len, Len2) :-
  ( select(Dig-SubTree, Tree, _) ->
    ( succ(Len, Len1), append([Dig], Curr, Currn),
      same_ending1(Digs, SubTree, Currn, Fin, Len1, Len2) ) 
    ; 
    Len2 = Len,
    Fin = Curr-Tree
  ).

---

Edit 2: For the final suggestion on @gusbro 's answer I created this code

ssame_endings(L1,[],Curr,Final):- Final=Curr.

ssame_endings(L1, L2,Curr,Final):-
  build_tree(L1, Tree),
  head(L2,H),
  tail(L2,T),  
  findall(Res,same_ending(Tree,H,Res) , Endings),
  append(Curr,Endings,Curr1),
  ssame_endings(L1,T,Curr1,Final).

head([A|_],A).
tail([_|A],A).

pow2(X,Z) :- Z is 2**X.

same_ending(Tree,N, N-Len/LItems):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len, SubTree),
  length(SDigs, Len),
  append(SDigs, _, RDigs),
  reverse(SDigs, RSDigs),
  same_ending2(SubTree, RSDigs, [], LItems).

same_ending1([], SubTree, Len, Len, SubTree1):-
  SubTree=[] -> SubTree1=[[]]; SubTree1=SubTree.
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (select(Dig-DigSubTree, Tree,Third) ->
    (succ(Len, Len1), same_ending1(Digs, DigSubTree, Len1, Len2, SubTree),same_ending1(Digs,Third,Len1,Len2,SubTree)) ;
    Len2-SubTree=Len-Tree
  ).

I used findall as suggested in order to combine all the answers given and I think that part is correct as I have written it. Then I used select after that which as I understand if we have the tree [1-[2-[3,4]] and we want both 1,2,3 and 1,2,4. if we have the number 5321 the third parameter will also give us 124. However the way I am using it does not produce the expected outcome. What I am doing wrong?

Answer 1

You can build a tree of reversed digits for the first list, then traverse the tree for each reversed item in the second list. This may be more efficient if the list have many items.

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  maplist(same_ending(Tree), L2, Endings).

same_ending(Tree, N, N-Len):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len).

same_ending1([], _, Len, Len).
same_ending1([Dig|Digs], Tree, Len, Len2):-
  (select(Dig-SubTree, Tree, _) ->
    (
        succ(Len, Len1), 
        same_ending1(Digs, SubTree, Len1, Len2)
    ) ;
    Len2=Len
  ).

build_tree(L, Tree):-
  foldl(add_tree, L, [], Tree).

add_tree(N, Tree, NTree):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  add_tree1(RDigs, Tree, NTree).

add_tree1([], Tree, Tree).
add_tree1([Dig|Digs], Tree, [Dig-SubTree1|Tree1]):-
  (select(Dig-SubTree, Tree, Tree1) -> true; SubTree-Tree1=[]-Tree),
  add_tree1(Digs, SubTree, SubTree1).

Test sample:

?- same_endings( [4432,2345,3243] , [3345,3232], Endings).
Endings = [3345-3, 3232-2].

You may modify this code a bit to obtain the actual items which have the same endings.

---

With a slight modification of the code above you can also list the actual numbers from the first list that have the same (maximum) ending on each item from the second list:

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  maplist(same_ending(Tree), L2, Endings).

same_ending(Tree, N, N-Len/LItems):-
  atom_chars(N, Digs),
  reverse(Digs, RDigs),
  same_ending1(RDigs, Tree, 0, Len, SubTree),
  length(SDigs, Len),
  append(SDigs, _, RDigs),
  reverse(SDigs, RSDigs),
  same_ending2(SubTree, RSDigs, [], LItems).

same_ending1([], SubTree, Len, Len, SubTree).
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (memberchk(Dig-DigSubTree, Tree) ->
    (
        succ(Len, Len1), 
        same_ending1(Digs, DigSubTree, Len1, Len2, SubTree)
    ) ;
    Len2-SubTree=Len-Tree
  ).

same_ending2([], _, LItems, LItems).
same_ending2([Dig-DigSubTree|SubTree], Digs, MItems, LItems):-
  (Dig=endmarker -> 
    (
        number_chars(Item, Digs), 
        NItems=[Item|MItems]
    ) ;
    same_ending2(DigSubTree, [Dig|Digs], MItems, NItems)
  ), 
  same_ending2(SubTree, Digs, NItems, LItems).

build_tree(L, Tree):-
  foldl(add_tree, L, [], Tree).

add_tree(N, Tree, NTree):-
  number_chars(N, Digs),
  reverse(Digs, RDigs),
  add_tree1(RDigs, Tree, NTree).

add_tree1([], Tree, [endmarker-[]|Tree]).
add_tree1([Dig|Digs], Tree, [Dig-SubTree1|Tree1]):-
  (select(Dig-SubTree, Tree, Tree1) -> true; SubTree-Tree1=[]-Tree),
  add_tree1(Digs, SubTree, SubTree1).

Test cases:

?- same_endings( [4432,2345,3243] , [3345,3232], Endings).
Endings = [3345-3/[2345], 3232-2/[4432]].
?- same_endings( [4432,2345,3243,2195345,2345] , [3345,3232,19232,2195345], Endings).
Endings = [3345-3/[2195345, 2345, 2345], 3232-2/[4432], 19232-2/[4432], 2195345-7/[2195345]].

There's no special treatment for the case when an item does not share any ending digit, the code just spits the whole list in that case.

---

If you want to get all the items with at least 1 matching ending digit, just change the procedures same_endings and same_endings1 with these ones:

same_endings(L1, L2, Endings):-
  build_tree(L1, Tree),
  findall(Ending, (member(N, L2), same_ending(Tree, N, Ending)), Endings).

same_ending1([], SubTree, Len, Len, SubTree).
same_ending1([Dig|Digs], Tree, Len, Len2, SubTree):-
  (select(Dig-DigSubTree, Tree, RestTree) ->
    ( 
     (
       Len=0, 
       RestTree = [], 
       Len2=Len, 
       SubTree=RestTree
     ) ;
     (
       succ(Len, Len1), 
       same_ending1(Digs, DigSubTree, Len1, Len2, SubTree)
     )
    ) ;
    Len2-SubTree=Len-Tree
  ).