Prolog - Wörter in Matrix finden

Question

Angesichts einer nxn Buchstabenmatrix und eine Liste von Wörtern, sollte das Programm alle Vorkommen der Wörter in der Matrix und deren Position finden.

Sie können von oben nach unten, von rechts nach links und diagonal erscheinen (in allen 8 Richtungen). Ein Wort kann beliebig oft vorkommen (einschließlich Null) und sie können sich überschneiden (wie die Wörter bad y adult ) und sogar eine Untermenge voneinander sein (wie die Wörter bad y ad ).

Answer 1

Hier ist eine Teillösung für die horizontale und vertikale gerade und umgekehrte Suche:

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.

Zwei Schwächen: (a) palindromische Wörter werden zweimal gefunden, und Wörter mit einem Buchstaben werden viermal gefunden - mathematisch vertretbar, aber aus Sicht des gesunden Menschenverstands wahrscheinlich unerwünscht. (b) Diagonale Übereinstimmungen werden überhaupt nicht gefunden, dafür braucht man eine aufwendigere Rekursion mit mindestens einem zusätzlichen Zählargument.

Vollständige Offenlegung: transpose_matrix/2 wurde von der schönen Antwort auf este Frage. Es ist erstaunlich, welche Fülle an Code sich in nur zwei Jahren auf Stackoverflow angesammelt hat...

Answer 2

EDIT Hier ist ein vollständiger Code (findet auch Wörter in Diagonalen). Ein Nachteil: Wörter aus den Hauptdiagonalen werden zweimal gefunden.

% 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).