CODEWITHSUNDEEP
prolog
Skinper
Skinper

Reputation: 93

How to check if all elements in the list of lists are the same except one [Prolog]

I would like to check if the elements of an array are less than 0, except for 1 element that is parameterized by (X, Y). I tried to use maplist, but could not maintain equality. Another alternative I tried is this:

verifyMatrix(X,Y,M) :-
   verifyMatrix(X,Y,0,M).

verifyMatrix(,,_,[]) :-
   !. 
verifyMatrix(X,Y,I,[M|Ms]):-
   rowVerify(0,M),
   Ni is I,
   verifyMatrix(X,Y,Ni,Ms). 
verifyMatrix(X,Y,X,[M|Ms]):-
   rowVerify(Y,M),
   I is X,
   verifyMatrix(-1,-1,I,Ms).

rowVerify(,,[]) :- !. 
rowVerify(Ec,I,[R|Rs]):-
   ((R < 0) ; (Ec is I)),
   Ni is I,
   rowVerify(Ec,Ni,Rs).

rowVerify(Ec,R):-
   rowVerify(Ec,0,R).

Upvotes: 2

Views: 450

Answers (2)

slago
slago

Reputation: 5509

Use nth1/3 (or nth0/3, if you prefer to index from 0) to enumerate elements of the matrix that are greater than ou equal to zero:

?- Matrix =[[-1,-2,-3],[-4,-5,+6],[-7,-8,-9]], nth1(R,Matrix,Row), nth1(C,Row,Element), Element>=0.
Matrix = [[-1, -2, -3], [-4, -5, 6], [-7, -8, -9]],
R = 2,
Row = [-4, -5, 6],
C = 3,
Element = 6 ;
false.

Then, use findall/3 to verify if such element is unique and is in the given position:

?- Matrix =[[-1,-2,-3],[-4,-5,+6],[-7,-8,-9]], 
findall(R-C, (nth1(R,Matrix,Row), 
nth1(C,Row,Element), Element>=0),[I-J]).
Matrix = [[-1, -2, -3], [-4, -5, 6], [-7, -8, -9]],
I = 2,
J = 3.

Thus, we can define the predicate less_than_zero_except/3 as:

less_than_zero_except(I, J, Matrix) :-
    findall(R-C, (nth1(R,Matrix,Row), nth1(C,Row,Element), Element>=0), [I-J]).

This predicate can be used to verify a specific position or to find such position:

?- less_than_zero_except(2,3,[[-1,-2,-3],[-4,-5,+6],[-7,-8,-9]]).
true.

?- less_than_zero_except(I,J,[[-1,-2,-3],[-4,-5,+6],[-7,-8,-9]]).
I = 2,
J = 3.

?- less_than_zero_except(I,J,[[-1,-2,-3],[-4,-5,+6],[-7,-8,+9]]).
false.

?- less_than_zero_except(I,J,[[-1,-2,-3],[-4,-5,-6],[-7,-8,-9]]).
false.

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476557

You are making things too hard here, by trying to solve everything concurrently. Let us first write a predicate that verifies that all elements in a list ("row"), are less than zero, we will worry about that special element later. We can verify that with:

less_zero(L) :-
    maplist(>(0), L).

We can also check if a condition holds for all elements, except for a given index, by using forall/2 [swi-doc]:

less_zero_except(L, J) :-
    forall((nth0(I, L, V), dif(I, J)), V < 0).

For example:

?- less_zero_except([-1, -2, 3, -5], 2).
true.

?- less_zero_except([-1, -2, 3, -5], 1).
false.

We can generate a predicate that checks if the row index is the same as a given one, and routes it accordingly to less_zero/1 or less_zero_except/2, like:

verify_row(Row, I, I, ColJ) :-
    less_zero_except(Row, ColJ).
verify_row(Row, I, J, _) :-
    dif(I, J),
    less_zero(Row).

Now we can use forall/2 on the matrix level as well:

verifyMatrix(RowI, ColJ, Matrix) :-
    forall(nth0(I, Matrix, Row), verify_row(Row, I, RowI, ColJ)).

A multi-directional predicate

The above is not bi-directional: we can not pass a matrix here, and then let Prolog determine the coordinates of the non-negative value (given that value exists). We can however implement that, for example by using the clpfd library [swi-doc]:

:- use_module(library(clpfd)).

validate_cell(V, I, J, I, J) :-
    V #>= 0.
validate_cell(V, _, _, _, _) :-
    V #< 0.

Now we can iterate over these values like:

validate_row([], _, _, _, _).
validate_row([C|T], RowI, ColJ, I, J) :-
    validate_cell(C, RowI, ColJ, I, J),
    J1 is J+1,
    validate_row(T, RowI, ColJ, I, J1).

and then we can validate the matrix:

validate_matrix([], _, _, _).
validate_matrix([Row|T], RowI, ColJ, I) :-
    validate_row(Row, RowI, ColJ, I, 0),
    I1 is I+1,
    validate_matrix(T, RowI, ColJ, I1).

and then we can define the validate_matrix/3 in terms of validate_matrix/4:

validate_matrix(ColI, RowJ, Matrix) :-
    validate_matrix(Matrix, ColI, RowJ, 0).

We can now generate matrices that satisfy the given constraint, as well as finding out the coordinates of the non-negative element, and validate the matrix for a given coordinate pair:

?- validate_matrix(I, J, M).
M = [] ;
M = [[]] ;
M = [[], []] ;
M = [[], [], []] ;
M = [[], [], [], []] ;
M = [[], [], [], [], []] ;
M = [[], [], [], [], [], []] ;
M = [[], [], [], [], [], [], []] ;
M = [[], [], [], [], [], [], [], []] .

?- validate_matrix(I, J, [R1, R2, R3]).
R1 = R2, R2 = R3, R3 = [] ;
I = 2,
J = 0,
R1 = R2, R2 = [],
R3 = [_5416],
_5416 in 0..sup ;
I = 2,
J = 0,
R1 = R2, R2 = [],
R3 = [_5672, _5678],
_5672 in 0..sup,
_5678 in inf.. -1 ;
I = 2,
J = 0,
R1 = R2, R2 = [],
R3 = [_5916, _5922, _5928],
_5916 in 0..sup,
_5922 in inf.. -1,
_5928 in inf.. -1.

?- validate_matrix(I, J, [[1, -1], [-2, -3]]).
I = J, J = 0 ;
false.

?- validate_matrix(I, J, [[-1, -1], [-2, 3]]).
I = J, J = 1 ;
false.

?- validate_matrix(I, J, [[-1, 1], [-2, 3]]).
false.

?- validate_matrix(0, 1, [[-1, -1], [-2, 3]]).
false.

?- validate_matrix(1, 1, [[-1, -1], [-2, 3]]).
true ;
false.

Upvotes: 1

Related Questions