Spinning Word Search

Question

Introduction:

Pete likes doing word search puzzles. Despite that, he has trouble searching for words vertically, (anti-)diagonally, or reversed. Because of that, he'll always search for the words left-to-right, and rotates the entire puzzle in increments of 45 degrees clockwise.
In addition to that, he'll also always search for the words in (alphabetical) order.

Challenge:

Given a word search grid and a list of (alphabetically ordered) words, output how many rotations are necessary to find all the words.

Brief explanation of what a word search is:

In a word search you'll be given a grid of letters and a list of words. The idea is to cross off the words from the list in the grid. The words can be in eight different directions: horizontally from left-to-right or right-to-left; vertically from top-to-bottom or bottom-to-top; diagonally from the topleft-to-bottomright or bottomright-to-topleft; or anti-diagonally from the topright-to-bottomleft or bottomleft-to-topright.

For example:

Grid:
 ABCD
 EFGH
 IJKL
 MNOP

Words:
 AFK
 BCD
 FC
 PONM

Here, the first string AFK can be found diagonally from the topleft-to-bottomright; the second word BCD horizontally from the left-to-right; etc.:

AFK    BCD    FC     PONM

aBCD   Abcd   ABcD   ABCD
EfGH   EFGH   EfGH   EFGH
IJkL   IJKL   IJKL   IJKL
MNOP   MNOP   MNOP   mnop

Challenge example:

If we take the same example grid and list of words above, we find AFK after 7 clockwise rotations of 45 degrees; BCD after 1 more rotation; FC after 1 more rotation; and PONM after 3 more rotations. So the result for the example grid and four words will be 12 (7+1+1+3).

Here a visual representation of these steps:

            A                    M                    P                    D
           E B                  N I                  L O                  C H
ABCD      I F C      MIEA      O J E      PONM      H K N      DHLP      B G L
EFGH  →  M J G D  →  NJFB  →  P K F A  →  LKJI  →  D G J M  →  CGKO  →  A F K P  ⮌
IJKL      N K H      OKGC      L G B      HGFE      C F I      BFJN      E J O
MNOP       O L       PLHD       H C       DCBA       B E       AEIM       I N 
            P                    D                    A                    M

      1           2        3           4        5           6        7  A F K
 BCD                                                                             8
      9     F C
                  10       11          12 PONM

Challenge rules:

• Input can be in any reasonable format. The input-grid could be a character-matrix; list/stream of lines; taken from STDIN; etc. The same applies to the list of words.
• The inputs are guaranteed to only contain regular letters (in the same casing, unless you prefer otherwise).
• You're allowed to take the inputs in uppercase; lowercase; mixed case; or even as 0- or 1-based alphabet indices as integers if you'd want.
• You can assume the input-words will always be in alphabetical order.
• You can assume the words will always be present in the grid, and will only occur once.
• All words are guaranteed to have at least two letters (because single-letter words could be found in multiple directions, adding annoying edge cases).
• You can assume neither the grid nor list of words will be empty.
• No need to deal with the remaining letters or partial overlapping of word. Just look for the words one at a time and output the amount of 45 degree clockwise rotations that are necessary.
• The grid will not necessarily be a square, but it's guaranteed to be a rectangle.

General rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Inputs:
ABCD
EFGH
IJKL
MNOP

AFK
BCD
FC
PONM

Output: 12

Inputs:
ABC

AB
ABC
BC

Output: 0

Inputs:
AB

BA

Output: 4

Inputs:
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

BACKWARD
DIAGONAL
FIND
HORIZONTAL
RANDOM
SEEK
SLEUTH
VERTICAL
WIKIPEDIA
WORDSEARCH

Output: 39

Answer 1

JavaScript (ES6), 149 bytes

Expects (m)(a), where m is a matrix of characters and a is a list of lists of characters.

m=>a=>a.map(w=>t+=m.some((r,y)=>r.some((_,x)=>j=~[..."21036785"].findIndex(d=>w.every((c,i)=>(m[y+~-(d/3)*i]||0)[x+d%3*i-i]==c))))*n-(n=j)&7,t=n=0)|t

Try it online!

How?

For each word \$w\$, we look for a starting position \$(x,y)\$ and a direction \$d\$ from the string "21036785" for which the word is matched along the following vector:

$$(dx,\:dy)=((d\bmod3)-1,\:\lfloor d/3\rfloor-1)$$

Hence the following directions for each \$d\$:

$$\begin{matrix}0&1&2\\3&&5\\6&7&8\end{matrix}$$

We define \$j\$ as the ones' complement of the index of \$d\$ in the string, which gives:

$$\begin{matrix}-3&-2&-1\\-4&&-8\\-5&-6&-7\end{matrix}$$

(NB: We use the ones' complement so that the inner some() is not triggered when findIndex() returns \$-1\$.)

Given the previous orientation \$n\$ (starting with \$n=0\$), the number of 45° clockwise turns that are needed to reach the new orientation is:

$$(n-j)\operatorname{AND}7$$

We add the result of the above expression to the accumulator \$t\$ and update \$n\$ to \$j\$.

Answer 2

Jelly,  26 22  21 bytes

-1 thanks to ovs! (Use the outer-product quick, þ rather thank €Ɱ.)

ŒdU$ŒḌƭƬw€þ§T€F’ŻI%8S

A dyadic Link accepting the Wordsearch on the left and the sorted word-list on the right that yields an integer.

Try it online!

How?

This would need tweaking to handle multiple instances of a word in the Wordsearch (would need to account for multiple results in the result of T€) but luckily, we don't need to handle that.

ŒdU$ŒḌƭƬw€þ§T€F’ŻI%8S - Link: Wordsearch grid, G; word-list W
       Ƭ              - collect input (initially G) while distinct applying:
      ƭ               -   alternating calls to:
   $                  -   ...1: last two links as a monad:
Œd                    -           anti-diagonals
  U                   -           reverse each
    ŒḌ                -   ...2: reconstruct from forward-diagonals
          þ           - table - i.e. [[f(o,w) for o in orientations] for w in W]:
        w€            -   first index of w in each row of o
           §          - sums (sum each of the orientation results)
            T€        - truthy (1-indexed) indices of each
              F       - flatten
               ’      - decrement
                Ż     - prepend a zero
                 I    - forward differences
                  %8  - modulo eight
                    S - sum

Answer 3

Python 3, 265 260 bytes

-5 thanks to KevinCruijssen

Golfed code

def f(G,W):
 r=0;f=range;g=len
 for w in W:
  while any(w in l for l in G)<1:r+=1;m=g(G[0]);H,G=G[:],["".join(G[j][i-j]for j in f(max(i-m+1,0),min(i+1,g(G))))[::-1]for i in f(g(G)+m-1)]if r%2 else["".join(H[~j][i]for j in f(g(H)))for i in f(g(H[0]))]
 return r

Try it online!

Formatted and commented code

def find_rotations(grid, words):
    rotations = 0
    for word in words:
        while not any(word in line for line in grid):
            rotations += 1
            if rotations % 2 == 1:  # If rotations is odd, rotate rectangular grid by 45deg
                old_grid = grid[:]  # Keep a copy of the old grid
                new_grid = []                                  #
                for i in range(len(grid) + len(grid[0]) - 1):  #
                    new_line = ""                              #
                    for j in range(                            #
                        max(i - len(grid[0]) + 1, 0),          # Equivalent to first list comprehension
                        min(i + 1, len(grid))                  # Rotates rectangular grid by 45deg
                        ):                                     #
                        new_line += grid[j][i-j]               #
                    new_grid.append(new_line[::-1])            #
                grid = new_grid[:]                             #
            else:                   # If rotations is even, rotate copy of old rectangular grid by 90deg
                                    # (Much easier than rotating diamond-shaped grid by 45deg)
                new_grid = []                                  #
                for i in range(len(old_grid[0])):              #
                    new_line = ""                              # Equivalent to second list comprehension
                    for j in range(len(old_grid)):             # Rotates rectangular grid by 90deg
                        new_line += old_grid[~j][i]            # (Rotates old_grid because that is the last rectangluar grid)
                    new_grid.append(new_line)                  #
                grid = new_grid[:]                             #
    return rotations

Answer 4

Python 3, 406 bytes

R=range
L=len
e=lambda b:'\n'.join(map(''.join,b))
r=lambda b,x,y:[b[x][y]]+(r(b,x-1,y+1)if x and y<L(b[0])-1 else[])
def s(b,c=1):
 t=[[i[::-1]for i in zip(*b)],[[i]for i in b[0]]][L(b)==1]
 yield[r(b,i,0)for i in R(L(b))]+[r(b,L(b)-1,i)for i in R(1,L(b[0]))]if c%2 else t
 yield from s([t,b][c%2],c+1)
o=lambda b,w:w!=[]and w[0]in b and 1+o(b,w[1:])
g=lambda b,w,u:1+g(next(u),w[o(e(b),w):],u)if w else-1

Try it online!

Answer 5

Charcoal, 59 bytes

ＷＳ⊞υι≔⟦⟧ηＷＳ⊞ηιυＦ⁸ＦＬυＦＬθ«ＪλκＵＭη⎇⁼μ⪫ＫＤＬμ✳ιωιμ»⎚ＩΣＥη﹪⁻ι∧κ§η⊖κ⁸

Try it online! Link is to verbose version of code. Explanation:

ＷＳ⊞υι

Read in the grid.

≔⟦⟧ηＷＳ⊞ηι

Read in the words.

υ

Output the grid.

Ｆ⁸

Loop over each direction.

ＦＬυＦＬθ«Ｊλκ

Loop over each cell.

ＵＭη

Looping over each word...

⎇⁼μ⪫ＫＤＬμ✳ιωιμ

... if it matches the word in the current direction starting from the current cell, replace it with the current direction.

»⎚ＩΣＥη﹪⁻ι∧κ§η⊖κ⁸

Pairwise subtract the directions, reduce them all modulo 8, and output the sum.

Answer 6

Python 3.8 (pre-release), 206 bytes

f=lambda n,k,N=0,E=enumerate:k and f(n,k[(A:=any(any(all(-1<(Y:=r+(R:=[0,*[-K]*3,0,K,K,K])[N%8])<len(n)>-1<(Z:=c+R[N%8-2])<len(_)!=C==n[Y][Z]for K,C in E(k[0]))for c,H in E(_))for r,_ in E(n))):],N+1-A)or N

Try it online!

Recursive solution.

Explanation

Initialize N, the number of rotations. Set it to 0.

At each iteration, we attempt to identify the first word in k, the list of words to find, by going through every cell in the grid and pointing in the direction that N corresponds to. For instance, if N is 0, meaning the grid is not rotated at all, we go 0 rows down and 1 column to the right, len(k[0]) times at each cell.

If such a word is identified, then we delete the first element and recall f with n, the now smaller k, and the same N. N does not change, because there might still be words in the same orientation.

If no such word is identified, then no deletion is done and instead we recall f with n, the same k, and an incremented N.

Eventually, k will be empty, and in such a case, we return N.

Answer 7

Python 3.8 (pre-release), 158 bytes

f=lambda G,L,*H:L>[]and 1-(d:=L[0]in" ".join(map("".join,G)))+f(d*G or[*zip(*((x:=H)or[(x:=x+s)+g+s*len(G)for g in G])[::-1])],L[d:],*[G*(H==()),H][d])
s=" ",

Try it online!

Takes a sequence of tuples of characters for the grid and a sequence of strings for the search list.

Test harness nicked from @ophact.

How?

More or less does actually rotate the grid and then searches in normal row major order.

90° rotations are implemented as up down flip followed by transpose (aka zip).

If we first shear by prepending a linearly (w.r.t. line number) increasing amount of white space and then do the same 90° rotation we get essentially the same lines as we would have doing a 45° rotation.

The main "loop" is recursion. G is the current grid L the leftover word list and H alternates between being empty and a backup of G because every 90° rotation must be based not on the current G but its predecessor.

Answer 8

JavaScript, 144 bytes

f=(a,b,d=0,[w,...r]=b)=>w?a.some((r,y)=>r.some((c,x)=>w.every((p,i)=>p==a[d%4?d<4?y-i:y+i:y]?.[x+i-'00122210'[d]*i])))?f(a,r,d):f(a,b,-~d%8)+1:0

Try it online!

TIO is 147 bytes as ?. syntax is not available on it.

Input grid as 2d character array. Input words as an array of array of characters. Output a number. f(grid: string[][], words: string[][]) -> number