CODEWITHSUNDEEP
prolog
Monolith
Monolith

Reputation: 39

Prolog check if list contains 2 times the elements of another list

Soo the task is not that difficult, but the problem is, I cant use term or number comparisons or sorting to do this. I have made a checker too confirm that the 2 lists contain the same elements (so that part can be ignored), but i don't know how to make the check for the question specificly. Soo for example if I have this: List1 [1,2] and List2 [1,2,1,2] it should be true, if List2 is [1,2,2] or [1,2,1,2,1] should be false.

Upvotes: 1

Views: 835

Answers (2)

Reema Q Khan
Reema Q Khan

Reputation: 878

I've made my approach wrt "List1 [1,2] and List2 [1,2,1,2] it should be true, if List2 is [1,2,2] or [1,2,1,2,1] should be false."

1. The check2times predicate compares 2 lists, then calls the predicate check. check's job is to compare and give the total count of the pair occurring in the list as a List [1,1]. Then use sum predicate to sum the list (E.g. [1,1]=2 ). Then simply check if the sum=2 it should return true, else it will be false.

check2times([H|T],[H2|T2]):-
    check([H|T],[H2|T2],N),
    sum(N,S),
    S=2.

2. check predicate

check(_,[],[]).
check([A,B|T],[H1,H2|L],[N|R]):-
    [A,B]=[H1,H2],
    N is 1+0,
    check([A,B|T],L,R).
check([A,B|T],[H1,H2|L],N):-
     [A,B]\=[H1,H2],
    check([A,B|T],L,N).

3. sum predicate

sum([],0).
sum([H|T],S):-
    sum(T,S1),
    S is S1+H.

Putting it all together:

check2times([H|T],[H2|T2]):-
    check([H|T],[H2|T2],N),
    sum(N,S),
    S=2.    
check(_,[],[]).
check([A,B|T],[H1,H2|L],[N|R]):-
    [A,B]=[H1,H2],
    N is 1+0,
    check([A,B|T],L,R).
check([A,B|T],[H1,H2|L],N):-
     [A,B]\=[H1,H2],
    check([A,B|T],L,N).

sum([],0).
sum([H|T],S):-
    sum(T,S1),
    S is S1+H.

Examples:

?-check2times([1,2],[1,2,1,2]).
true
false
check2times([1,2],[1,2,1]).
false
?-check2times([2,2],[2,2,2,2]).
true
false
?-check2times([2,2],[2,2,2,2,2,2]).
false
?-check2times([2,2],[2,4,3,5,2,2,3,6,5,3,2,2]).
true
false
?-check2times([b,b],[b,b,a,d,f,g,w,q,b,b,h,y]).
true
false
?-check2times([b,b],[b,b,5,6,f,g,1,2,b,b,h,y]).
true
false
?-check2times([1,2,3,4],[1,2,3,4,1,2,3,4,1,2,3,4]).
false
?-check2times([1,2,3,4],[1,2,3,4,1,2,3,4]).
true
false

Upvotes: 1

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Here is a basic approach that doesn't use any numbers. It does use dif/2 (alternatively, use \=), which is a "term comparison", but not the kind you may have meant.

First, a predicate for expressing that an element occurs exactly 0 times in a list (in other words, it is not a member of the list):

exactly0_list(_X, []).
exactly0_list(X, [Y | Ys]) :-
    dif(X, Y),
    exactly0_list(X, Ys).

For example:

?- exactly0_list(x, [a, b, c]).
true ;
false.

But:

?- exactly0_list(b, [a, b, c]).
false.

Building on this, a predicate for expressing that an element occurs exactly 1 time in a list:

exactly1_list(X, [X | Ys]) :-
    exactly0_list(X, Ys).
exactly1_list(X, [Y | Ys]) :-
    dif(X, Y),
    exactly1_list(X, Ys).

Look how similar this looks. This behaves like this:

?- exactly1_list(b, [a, b, c]).
true ;
false.

?- exactly1_list(b, [a, b, c, b]).
false.

If you see a pattern emerging, implement a predicate exactly2_list/2 along the same lines. It should behave like this:

?- exactly2_list(b, [a, b, c, b]).
true ;
false.

?- exactly2_list(b, [a, b, c, b, b]).
false.

Then use this to check each element of your first list against your second list.

Upvotes: 2

Related Questions