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

• Kevin Cruijssen: Related challenges: Diamondize a matrix (single 45 degree rotation); Word Search Helper (output the left-to-right lines of all eight rotations); Wordsearch Solver (speaks for itself).

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\$.

• tsh: Maybe this failed on AB/BA, AB?
• Arnauld: @tsh This doesn't look like a valid input grid, as the words are guaranteed to only occur once (5th rule).

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

• ovs: I think €Ɱ can be þ
• Jonathan Allan: Yep, thank you @ovs

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

• Kevin Cruijssen: Welcome to CGCC! Nice first answer, +1. :) If you haven't seen it yet, tips for golfing in Python and tips for golfing in all languages might be interesting to read through. Three minor things to golf: >0 can be removed after r%2; the space at [i] for can be removed; -j-1 can be ~j. You can also move the test code to the footer in your TIO-link, so it's clearer what the actual code-block is
• Lecdi: @KevinCruijssen Thanks!

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!

• Kevin Cruijssen: y<L(b[0])-1 else can be y<~-L(b[0])else for -1

Answer 5

Charcoal, 59 bytes

WS⊞υι≔⟦⟧ηWS⊞ηιυF8FLυFLθ«JλκUMη⎇=μ⪫KDLμ✳ιωιμ»⎚IΣEη%−ι∧κ§η⊖κ8

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

WS⊞υι

Read in the grid.

≔⟦⟧ηWS⊞ηι

Read in the words.

υ

Output the grid.

F8

Loop over each direction.

FLυFLθ«Jλκ

Loop over each cell.

UMη

Looping over each word...

⎇=μ⪫KDLμ✳ιωιμ

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

»⎚IΣEη%−ι∧κ§η⊖κ8

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