Word Search Solver

Question

I got to wondering yesterday if I could write a program to comb through a given word search and output the answers. It was actually surprisingly easy. Now I wonder just how small we can get.

Rules

• Your first input is a string or collection of n lines, each of which is n characters long
• Your second input is a list of words in any format to find in the puzzle
• All words in the search list are guaranteed to be in the puzzle
• Words can be oriented in any of the four cardinal directions, as well as diagonally both forwards and backwards
• Only uppercase A-Z characters will be present in the puzzle
• Your code must find every word in the the search string, and output the coordinate position of the starting letter, where 0,0 is the top left character.
• In the event that you locate more than one instance of the same word, you may handle it however you like. Output it multiple times, or only once, it's up to you

Examples/Test Cases

Given the following board:

ABCD
EFGH
IJKL
MNOP

And the following search string:

ABCD,CGKO,POMN,NJF,AFKP,CFI,LGB,MJGD

Your program should output the following, in any order:

ABCD at 0,0
CGKO at 0,2
PONM at 3,3
NJF at 3,1
AFKP at 0,0
CFI at 0,2
LGB at 2,3
MJGD at 3,0

As always, shortest answer wins

Answer 1

JavaScript (Node.js), 154 152 150 141 bytes

• thanks to Arnauld for reducing by 2 bytes

returns array of locations (it was a string with new lines before)

(b,w)=>w.map(s=>[...b].map((_,p)=>[1,-1,r=b.search`
`,-r,~r,++r,-~r,~r].map(d=>[...s].every((c,i)=>c==b[p+d*i])?s+=" at "+[p/r|0,p%r]:0))&&s)

Try it online!

Answer 2

Python 2, 213 bytes

lambda a,W:[(w,i,j)for w in W for i in R(L(a))for j in R(L(a[0]))for U in R(9)if U-4and g(i,j,U/3-1,U%3-1,a).find(w)==0]
g=lambda i,j,u,v,a,s='':L(a)>i>=0<=j<L(a[0])and g(i+u,j+v,u,v,a,s+a[i][j])or s
L=len;R=range

Try it online!

g takes a starting location i,j and a direction u,v and via recursion extracts the string starting at that location in that direction.

f then visits each starting location i,j and direction U/3-1,U%3-1 and checks each word w to see if the resulting string starts with w.

Answer 3

Python 3, 149 147 bytes

def g(b,w):h=b.find('\n')+1;return[f'{y} at {i//h},{i%h}'for y in w for i in range(len(b))for d in(1,h+1,h,h-1,-1,~h,-h,1-h)if y==b[i::d][:len(y)]]

Try it online!

Ungolfed version

def g(b,w):
    h = b.find('\n') + 1                              # width of a row plus the '\n'
    a = []
    for y in w:                                       # iterate over the words
        for i in range(len(b)):                       #   iterate over the game board
            for d in(1,h+1,h,h-1,-1,~h,-h,1-h):       #     for each possible direction
                if y==b[i::d][:len(y)]:               #       see if the word matches
                    a.append(f'{y} at {i//h},{i%h}')
    return a

The main idea is that b[i::d] selects a slice from the game board. The slice starts as position i and extends in the direction d. For example, d = h+1 corresponds to the southeast diagonal, whereas d = ~h, which is the same as -h-1, corresponds to the northwest diagonal. [:len(y)] chops the slice off at the same length as the word being searched.