Prolog: busque palabras en la matriz

Question

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

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

Answer 1

EDIT 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

He aquí una solución parcial para la recta horizontal y vertical y de búsqueda inversa:

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 justificable, pero probablemente no deseado 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 la pregunta this. Es increíble, la gran cantidad de código que stackoverflow ha acumulado en solo dos años ...