Prolog - trouver des mots dans la matrice

Question

Étant donné une matrice de lettres nxn et une liste de mots, le programme devrait trouver toutes les apparences des mots dans la matrice et leur emplacement.

Ils peuvent apparaître de haut en bas, de droite à gauche et de diagonale (dans les 8 directions). Un mot peut apparaître n'importe quel nombre de fois (y compris zéro) et ils peuvent se chevaucher (comme les mots bad et adult) et même être un sous-ensemble de l'autre (comme les mots bad et ad).

Answer 1

EDIT Voici un code complet (trouve aussi des mots en diagonale). Un inconvénient: les mots des diagonales principales sont trouvés deux fois.

% 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

est ici une solution partielle pour droite horizontale et verticale et recherche inversée:

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. 

Deux faiblesses: (a) les mots palindromes sont trouvés deux fois, et les mots d'une lettre se trouvent quatre fois - mathématiquement justifiable, mais probablement indésirable d'une perspective de bon sens. (b) les correspondances diagonales ne sont pas trouvées du tout, pour cela vous avez besoin d'une récursion plus impliquée avec au moins un argument de comptage supplémentaire.

La divulgation complète: transpose_matrix/2 a été adapté de la belle réponse à this question. C'est incroyable, la richesse du code accumulé par stackoverflow en seulement deux ans ...