Intersection of two strings in Prolog

Question

Tried before, but it is still kind of a mess for me. Thought it was longest subsequence, but it actually isn't. So writing it with better examples. I am trying to write a Prolog predicate to compare two strings to see if they have the same elements and to print them out (only once per member). Currently I have written this to get the strings into 2 different lists for easier checking:

However, I am having trouble finding the right way to compare EVERY element in those two lists no matter where they are. I have found ways to compare till it founds one and it returns true, but I need it to compare every element in both lists and output them. I know it has to do with heads and comparing them, then adding the next first list member as the new head etc. But I can't figure out a way to do it. Also, intersection kinda does what I need, but it gives me every element (even mutliple times). I need it to stop after it finds the matching element so it finds them all only once.

plates(X,Y,Mem,Num):-
    atom_chars(X,Xs),
    atom_chars(Y,Ys),
    compare_list(Xs,Ys,Mem),
    length(Mem,Num).

compare_list([], _, []).    
compare_list([H1|T1], L, R) :-
    (check_element(H1, L)
    ->R = [H1|R]
    ;R = R
    ),
    compare_list(T1, L, R).

check_element(_, []).   
check_element(X, [H|T]) :-
   X = H,
   check_element(X, T).

Example1:

?-plates('111AXB','112XXX', Mem, Num).

Should output:

Mem = ['1','1','X'],
Num = 3.

Example2:

?-plates('456XYZ','678ABC', Mem, Num).

Should output:

Mem = ['6'],
Num = 1.

I tried implementing the solution here: PROLOG Comparing 2 lists

My test:

 ?- plates('ABC123','123ABC',Mem,Num).

My output:

Mem = [],
Num = 0.

Expected:

Mem = ['A', 'B', 'C', '1', '2', '3'],
Num = 6.

But I couldn't get it to work the way I wanted it to... Any help would be very appreciated!

coder coder · Accepted Answer · 2016-10-11T05:43:18

You could write something like:

plates(X,Y,Mem,Num):-
    atom_chars(X,Xs),
    atom_chars(Y,Ys),
    inter(Xs,Ys,Mem),
    length(Mem,Num),!.

inter(_,[],[]).
inter([],_,[]).
inter([H|T],L,[H|T1]):-
          member(H,L),
          delete(H,L,L1),
          inter(T,L1,T1).
inter([H|T],L,List):- \+member(H,L),inter(T,L,List).          

delete(H,[H|T],T).
delete(H,[X|T1],[X|T]):-dif(H,X),delete(H,T1,T).

Where inter finds the intersection and by checking if an element of first list occurs in second and then adds it to third list and deletes it from the second.Some examples:

?- plates('112XXX','111AXB', Mem, Num).
Mem = ['1', '1', 'X'],
Num = 3.

?- plates('111AXB','112XXX', Mem, Num).
Mem = ['1', '1', 'X'],
Num = 3.

?- plates('456XYZ','678ABC', Mem, Num).
Mem = ['6'],
Num = 1.

?- plates('ABC123','123ABC',Mem,Num).
Mem = ['A', 'B', 'C', '1', '2', '3'],
Num = 6.

?- plates('123ABC','345DEF',Mem,Num).
Mem = ['3'],
Num = 1.

Intersection of two strings in Prolog

1 Answers