Prolog - find words in matrix

Question

A friend of mine is taking a course in Programming Languages that involve Prolog. I took this course a while back and I'm pretty rusty with Prolog. My friend asked me a question in Prolog and I'm not sure how to solve it, but I guess for a seasoned Prolog programmer this would be pretty easy. If you could solve it (or at least give me the skeleton of the code) I would appreciate it:

Given an nxn letter matrix and a list of words, the program should find all the appearances of the words in the matrix and their location. They could appear up-down, right-left and diagonally (over all - 8 directions). A word can appear any number of times (including zero) and they can overlap (like the words bad, and adult) and even be a subset of one another (like the words bad and ad).

(I realize this sounds like "My friend" is me and I'm trying to trick you into giving me homework solutions, but I swear this story is genuine).

Answer 1

Here's a partial solution for horizontal and vertical straight and reverse lookup:

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.

Two weaknesses: (a) palindromic words are found twice, and one-letter words are found four times - mathematically justifiable, but probably unwanted from a common-sense perspective. (b) diagonal matches aren't found at all, for that you need more involved recursion with at least one additional counting argument.

Full disclosure: transpose_matrix/2 was adapted from the beautiful answer to this question. It's amazing, the wealth of code that stackoverflow has accumulated in just two years...

Answer 2

EDIT Here's a complete code (finds words in diagonals too). One drawback: words from the main diagonals are found twice.

% 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 3

hi bolo,

I came across this page when searching how to find words in a matrix, I dont have problems searching vertical and horizontal.

I cant seems to understand the thinking method of how you seperate the diagonals to a list,

And i mean this three lines:

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

I would be greatful for any explanation.

Thankx