reglas - unificacion prolog

Prolog-encuentra palabras en la matriz

Question

Dada una matriz de letras nxn y una lista de palabras, el programa debería encontrar todas las apariencias de las palabras en la matriz y su ubicación.

Podrían aparecer arriba-abajo, derecha-izquierda y diagonalmente (en las 8 direcciones). Una palabra puede aparecer varias veces (incluso cero) y se pueden superponer (como las palabras bad y adult ) e incluso ser un subconjunto de la otra (como las palabras bad y ad ).

Answer 1

EDITAR Aquí hay un código completo (también encuentra palabras en las diagonales). Un inconveniente: las palabras de las diagonales principales se encuentran dos veces.

% word(X) iff X is a word
word("foo").
word("bar").
word("baz").

% prefix(?A, +B) iff A is a prefix of B
prefix([], _).
prefix([A|B], [A|C]) :- prefix(B, C).

% sublist(?A, +B) iff A is a sublist of B
sublist(A, B) :- prefix(A, B).
sublist(A, [_|B]) :- sublist(A, B).

% reversed(?A, +B) iff A is reversed B
reversed(A, B) :- reversed(B, [], A).
reversed([A|B], C, D) :- reversed(B, [A|C], D).
reversed([], A, A).

% rowsreversed(?A, +B) iff matrix A is matrix B with reversed rows
rowsreversed([A|B], [C|D]) :- reversed(A, C), rowsreversed(B, D).
rowsreversed([], []).

% transposed(+A, ?B) iff matrix B is transposed matrix A
transposed(A, B) :- transposed(A, [], B).
transposed(M, X, X) :- empty(M), !.
transposed(M, A, X) :- columns(M, Hs, Ts), transposed(Ts, [Hs|A], X).

% empty(+A) iff A is empty list or a list of empty lists
empty([[]|A]) :- empty(A).
empty([]).

% columns(+M, ?Hs, ?Ts) iff Hs is the first column
%   of matrix M and Ts is the rest of matrix M
columns([[Rh|Rt]|Rs], [Rh|Hs], [Rt|Ts]) :- columns(Rs, Hs, Ts).
columns([[]], [], []).
columns([], [], []).

% inmatrix(+M, ?W) iff word W is in the matrix M
inmatrix(M, W) :- inrows(M, W).
inmatrix(M, W) :- incolumns(M, W).
inmatrix(M, W) :- inleftdiagonals(M, W).
inmatrix(M, W) :- inrightdiagonals(M, W).

% inrows(+M, ?W) iff W or reversed W is in a row of M
inrows([R|_], W) :- word(W), sublist(W, R).
inrows([R|_], W) :- word(W), reversed(V, W), sublist(V, R).
inrows([_|Rs], W) :- inrows(Rs, W).

% incolumns(+M, ?W) iff W or reversed W is in a column of M
incolumns(M, W) :- transposed(M, N), inrows(N, W).

% inleftdiagonals(+M, ?W) iff W or reversed W is in a left diagonal of M
inleftdiagonals(M, W) :- inupperleftdiagonals(M, W).
inleftdiagonals(M, W) :- transposed(M, N), inupperleftdiagonals(N, W).

% inupperleftdiagonals(+M, ?W) iff W or reversed W is in an upper left diagonal of M
inupperleftdiagonals(M, W) :- upperdiags(M, N), inrows(N, W).

% upperdiags(+M, ?X) iff X is a list of upper diagonals of matrix M
upperdiags(M, X) :- upperdiags(M, [], Y), reversed(Z, Y), transposed(Z, X).
upperdiags([R|Rs], A, X) :- columns(Rs, _, T), upperdiags(T, [R|A], X).
upperdiags([], X, X).

% inrightdiagonals(+M, ?W) iff W or reversed W is in a right diagonal of M
inrightdiagonals(M, W) :- rowsreversed(N, M), inleftdiagonals(N, W).

Answer 2

Aquí hay una solución parcial para la búsqueda recta e inversa horizontal y vertical:

count_hits(Word, Matrix, Result):-
        atom_chars(Word, Chars),
        reverse(Chars, C2),
        transpose_matrix(Matrix, M2),
        findall(1, find_chars_in_matrix(Chars,Matrix), A),
        findall(1, find_chars_in_matrix(Chars,M2), B),
        findall(1, find_chars_in_matrix(C2,Matrix), C),
        findall(1, find_chars_in_matrix(C2,M2), D),
        length(A, X1),
        length(B, X2),
        length(C, X3),
        length(D, X4),
        Result is X1 + X2 + X3 + X4.

transpose_matrix([],[]).
transpose_matrix([[ULCorner|Header]|Body], [[ULCorner|NewHeader]|NewBody]) :- 
        collect_heads_and_tails(Body, NewHeader, Kernel),
        collect_heads_and_tails(NewBody, Header, X2),
        transpose_matrix(Kernel, X2).

collect_heads_and_tails([], [], []).
collect_heads_and_tails([[H|T]|TT], [H|X], [T|Y]):-collect_heads_and_tails(TT, X, Y).

find_chars_in_matrix(Chars, [H|_]):-
        sublist(Chars, H).

find_chars_in_matrix(Chars, [_|T]):-
        find_chars_in_matrix(Chars, T).

sublist(L, [_|T]) :- sublist(L, T).
sublist(A, B) :- prefix(A, B).

prefix([H|T], [H|T2]) :- prefix(T, T2).
prefix([], _).


% test data
matrix([[e,t,r,e],
        [r,r,t,r],
        [t,r,t,t],
        [e,e,t,e]]).
go :- matrix(M), count_hits(etre, M, X), write(X).
:-go.

Dos debilidades: (a) las palabras palindrómicas se encuentran dos veces, y las palabras de una letra se encuentran cuatro veces: matemáticamente justificables, pero probablemente no deseadas desde una perspectiva de sentido común. (b) las coincidencias diagonales no se encuentran en absoluto, para eso necesita una recursión más involucrada con al menos un argumento de recuento adicional.

Descripción completa: transpose_matrix / 2 fue adaptada de la hermosa respuesta a esta pregunta. Es increíble, la riqueza de código que ha acumulado en solo dos años ...