Word Search Puzzle

Question

Given a rectangular text as a word search puzzle and a search string, determine if the text contains the search string. The search string may appear:

• horizontally, vertically or diagonally
• forwards or backwards

You may write a function or a program and take two strings as input via function argument, ARGV or STDIN. The output should be a truthy or falsy result which can either be returned from the function or written to STDOUT.

Assume that the text will contain arbitrary printable ASCII characters (hex codes 20 to 7E) and line break characters. Letters are case sensitive. You may assume that the input text is rectangular, i.e. all lines have the same length. You may whether the input ends with a trailing newline or not (if it matters for your submission).

This is code golf, the shortest answer (in bytes) wins.

Examples

Using this grid from Wikipedia's article on word searches as the first input:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

the following search strings should yield truthy or falsy results respectively:

Truthy: RANDOM, VERTICAL, HORIZONTAL, WORDSEARCH, WIKIPEDIA, TAIL
Falsy:  WordSearch, CODEGOLF, UNICORN

Alternatively, using this input text

Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur.

We get the following search results (using quotes now, because there are spaces in some search strings):

Truthy: "Lorem", "mine", "uma bop", "tuetdod", "snol,a", "texas", "pii.d  v", "vexta"
Falsy:  "lorem", "wordsearch", "pii.d v", "mute"

Answer 1

CJam, 46 37 bytes

qN%{_zW%__,N**2$2$+,)/z\}4*]:+N*eas#)

Reads the grid from STDIN and the word as a command-line argument. Prints positive integers for matches and 0 for non-matches.

At the cost of two extra bytes, both strings (word, linefeed, grid) can be read from STDIN:

qN%(\{_zW%__,N**2$2$+,)/z\}4*](\:+N*\#)

You can try this version online with the CJam interpreter.

Example run

$ for W in Lorem mine uma\ bop tuetdod snol,a texas pii.d\ \ v vexta WordSearch CODEGOLF UNICORN; do echo -e "$(cjam wordsearch.cjam "$W" < grid)\t$W"; done
1       Lorem
3085    mine
2055    uma bop
5142    tuetdod
3878    snol,a
1426    texas
5371    pii.d  v
2536    vexta
0       WordSearch
0       CODEGOLF
0       UNICORN

Background

Assume the input was the following grid:

ABCD
EFGH
IJKL

Splitting at linefeeds, we obtain the following array:

A := [
         "ABCD"
         "EFGH"
         "IJKL"
     ]

That covers East words (words going from left to right).

Now, we join the elements of A using a string of len(A) linefeeds as separator:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Then, we chop the resulting string in chunks of length len(A) + len(A[0]) + 1:

[
    "ABCD⏎⏎⏎E"
    "FGH⏎⏎⏎IJ"
    "KL"
]

If we "zip" the array (transpose rows and columns), we obtain:

[
    "AFK"
    "BGL"
    "CH"
    "D⏎"
    "⏎⏎"
    "⏎⏎"
    "I⏎"
    "EJ"
]

That covers South East words.

If we zip A and reverse the order of the result's rows, we obtain:

[
    "DHL"
    "CGK"
    "BFJ"
    "AEI"
]

That covers South and – after repeating the process for diagonals – South West words.

Zipping and reversing again, we obtain:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

That covers West and – after repeating the process for diagonals – North West words.

Zipping and reversing once more, we obtain:

[
    "IEA"
    "JFB"
    "KGC"
    "LHD"
]

That covers North and – after repeating the process for diagonals – North East words.

How it works

The code does as explained in the previous section, with two minor differences:

• It zips and reverses once at the very beginning.
• It computes len(A) + len(A[0]) as len(A + zip(A)).

Finally, it joins all rows of all generated arrays using linefeeds as separators and searches for the word in the resulting string.

qN%                                   " A := split(input(),'\n')                          ";
   {                    }4*           " Do 4 times:                                       ";
    _zW%                              "   B := reverse(zip(A))                            ";
        __,N**                        "   C := B.join(len(B) * '\n')                      ";
              2$2$+,)/z               "   D := zip(C.chunks(len(A + B) + 1))              ";
                       \              "   A := B                                          ";
                           ]          " Collect all values of A and D in an array R.      ";
                            :+        " R := flatten(R)                                   ";
                              N*      " R := R.join('\n')                                 ";
                                eas   " I := flatten(ARGV)                                ";
                                   #) " print R.index(I) + 1                              ";

Answer 2

Java : 183 211 321

boolean s(char[]w,char[]s){int j,z,a=s.length,i=a*9,f=1,q=0;for(;s[q++]>10;);for(;i-->0;)for(j=w.length,z=i/9;i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];z+=q*(i/3%3)+i%3-q-1)f*=j;return f==0;}

A basic brute force. There's not much else to say, I guess. Input is needle first and haystack second. Assumes grid is newline-terminated.

A slightly more readable version with test case shown:

public class WordSearch {
    static String grid = "WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH";
    static String search = "RANDOM";
    
    public static void main(String[] args) {
        System.out.println(new WordSearch().s(search.toCharArray(),grid.toCharArray()));
    }

    boolean s(char[]w,char[]s){
        int j,z,a=s.length,i=a*9,f=1,q=0;
        for(;s[q++]>10;);
        for(;i-->0;)
            for(j=w.length,z=i/9;
                i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];
                z+=q*(i/3%3)+i%3-q-1)
                f*=j;
        return f==0;
    }
}

Answer 3

JavaScript (E6) 111 116

Brute force search for every character in every direction - as golfed as I can

F=(b,w)=>
  [1,-1,r=b.search('\n'),-r,++r,-r,++r,-r].some(d=>
    [...b].some((_,p)=>
      [...w].every(c=>c==b[p+=d],p-=d)
    )
  )

Test In FireFox/Firebug console

;["RANDOM", "VERTICAL", "HORIZONTAL", "WORDSEARCH", "WIKIPEDIA", "TAIL",
"WordSearch", "CODEGOLF", "UNICORN"]
.forEach(w=>console.log('\n'+ w +' -> '+
  F("WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH",w)))

Output

RANDOM -> true
VERTICAL -> true
HORIZONTAL -> true
WORDSEARCH -> true
WIKIPEDIA -> true
TAIL -> true
WordSearch -> false
CODEGOLF -> false
UNICORN -> false

Answer 4

Python, 175

Not very inspired, but here goes:

def s(h,n):
 l=h.find('\n')+2;h+='\n'*l;L=i=len(h)
 while i>0:
  i-=1
  for d in[-l,1-l,2-l,-1,1,l-2,l-1,l]:
    j=i;m=len(n)
    for c in n:m-=c==h[j%L];j+=d
    if m<1:i=-1
 return-i

First argument is haystack, second is needle.

Answer 5

Bash+coreutils, 214 169 bytes

r()(tee >(rev) $@)
t()(eval paste -d'"\0"' `sed 's/.*/<(fold -1<<<"&")/'`)
d()(while IFS= read l;do echo "$a$l";a+=_;done|t)
r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep -q "$1"

Uses 3 transform functions r, t and d to reverse, transpose and diagonal shift, in all the necessary combinations.

Update - the r function now produces reversed and non-reversed output for extra golfiness

Input via commandline arguments - search string, followed by (newline separated) rectangular wordsearch block.

Output is an idiomatically correct shell exit status code - 0 meaning TRUE and 1 meaning FALSE.

Output:

$ for w in "Lorem" "mine" "uma bop" "tuetdod" "snol,a" "texas" "pii.d  v" "vexta" ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
0
0
0
0
0
0
0
0
$ for w in WordSearch CODEGOLF UNICORN ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam, 
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
1
1
1
$ 

Answer 6

C,163

f(char*h,char*n){int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;for(i=l*9;i--;y+=d&&!n[j]){p=i/9;d=i%9/3*w-w+i%3-1;for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;}return y;}

No rearrangement of the grid, I simply try every starting letter in every direction, and walk along until I run off the grid or find a mismatch.

I take advantage of the fact that a C string terminates in a zero byte. As there are no zero bytes in the grid, there will ALWAYS be a mismatch. But if the mismatch occurs at the zero byte we know we have found the end of the string to be searched for, and record it as a match.

Ungolfed in a test program

char h[]="WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH\n";

f(char*h,char*n){                                   //haystack,needle
  int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;   //l=length of whole grid. w=width of row, including terminal newline ASCII 10
  for(i=l*9;i--;){                                  //for each start letter and direction
    p=i/9;                                          //pointer to start letter
    d=i%9/3*w-w+i%3-1;                              //9 possible values of direction vector {-w,0,w}+{-1,0,1}
    for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;           //walk p in the direction defined by d until we walk off the top or bottom of the grid or a mismatch is fount
    y+=d&&!n[j];                                    //if we got all the way to the terminal 0, record it as a hit. If d=0, don't record as this is an invalid direction.
  }
  return y;   
}

main(int c, char**v){
  printf("%d",f(h,v[1]));  
}

Output

Note that the function will return the total number of incidences of the string searched for in the grid. Thus for OD it returns 6. If no incidences are found it returns 0 which is the only falsy value in C. Changing to y|=d*!n[j] would save one character but lose this functionality.

$ ./a UNICORN
0

$ ./a CODEGOLF
0

$ ./a WordSearch
0

$ ./a RANDOM
1

$ ./a WORDSEARCH
1

$ ./a VERTICAL
1

$ ./a HORIZONTAL
1

$ ./a WIKIPEDIA
1

$ ./a TAIL
1

$ ./a OD
6

Answer 7

C# - 218 197 186 bytes

C# function that takes 2 strings, the first the word to search for, the later the grid with line feeds (\n) between lines. Things are getting desperate now... so desperate in-fact that my previous edit didn't work!

Golfed code:

bool F(string D,string S){int l=S.Length,i=l*13,r,p;for(S+="\n";i-->l*5;i=r<0?r:i)for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1);return i<0;}

Less golfed with test code:

class P
{
    static void Main()
    {
        System.Console.WriteLine(new P().F(System.Console.ReadLine(),System.Console.In.ReadToEnd())?"Truthy":"Falsy"); // because why not
    }

    bool F(string D,string S)
    {
        int l=S.Length,i=l*13,r,p;

        for(S+="\n";i-->l*5;i=r<0?r:i) // for each cell/direction
            for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1); // test against string (backwards)

        return i<0;
    }
}

Answer 8

Haskell - 173

Instead of searching directly on the grid, I transform the grid in different ways and match the word with each row of the new grid.

For example,

G1    G2    G3       G4   G5

abcd  aA1   abcd     a..  ..1
ABCD  bB2   .ABCD    bA.  .A2
1234  cC3   ..1234   cB1  aB3
      dD4            dC2  bC4
                      D3  cD
                       4  d

Search the word in each row of G1, G2, G4 and G5, then we're done. Note that G3 is not used, I post it here just for illustration.

A similar idea is applied to search forward and backward: just search the original word and reversed word.

So now we have searched 8 directions. Here's the code, whose correctness was verified by another script.

import Data.List
v=reverse
t=transpose
y=any
d r=zipWith(++)(scanr(\_->('\n':))[]r)r
g r w=y(y$y((==w).take(length w)).tails)[r,t r,t.d$r,t.d.v$r]
f r w=y(g(lines r))[w,v w]

The function f is what we want and its argument r is the rectangle string, w is the word to search.

Answer 9

Python 2 - 246 259 275 308 298 297 294 313 322

w,s=input()
r=range
d='\n'
I=''.join
w=w.split(d)
t,u=len(w),len(w[0])
v=d.join([I(x)for x in zip(*w)]+[d]+[I([w[i+j][i]for i in r(min(u,t-j))])+d+I([w[i][i+j]for i in r(min(t,u-j))])for j in r(max(t,u))]+[d]+w)
print s in v or s[::-1]in v

Thanks to Will for some help with dealing with the print and defining join.

Thanks to underground railroad for reminding me to golf spaces properly ;p

Fixed for bad matches thanks to using ',' as delimiter.

Apparently the best way to golf is to add tons of horizontal scrolling.

Input as whitespace bang newline delimited lines in quotes: "WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH","RANDOM"

Answer 10

R, 240 bytes

\(S,s,`!`=length,r=rep,`?`=strsplit,`^`=Reduce,p=paste0){d=e=Map(r,r("",!(b=(a=el(S?"\n")?""))),(x=-1+2*!el(b)))
for(j in 1:!b)d[[j]][j:(j-1+!el(b))]=e[[j]][(x-j):(x-j-1+!el(b))]=b[[j]]
any(grepl(p^c(s,"|",rev(el(s?""))),c(a,p^b,p^e,p^d)))}

Attempt This Online!

This is a function that creates all 4 possible combinations - rows, columns and 2 diagonals and searches the substring or the reverse of it in the vector.

Answer 11

APL (Dyalog Classic), 44 bytes

1∊⍞⍷↑{⍉0,⍵,↑(0,⊢)\↓0,⍵}¨{⍉⌽⍵}\4⍴⊂↑a⊆⍨a≠⊃⌽a←⎕

Try it online!

Answer 12

J, 60 53 bytes

<@[e.[:,[:(;|.)@>[:<\\.@>[:(<"1,</.)@>@(;|.@|:)[;.2@]

Try it online!

Requires the first input to contain no newlines.

Explanation:

linkrotate=: ;|.@|:     NB. link with itself rotated 90° ccw
infixes   =: <\\.       NB. list of boxes containing the infixes
lines     =: <"1 , </.  NB. horizontal and diagonal lines, boxed
linkrev   =: ;|.        NB. link with itself reversed
appearin  =: <@[ e. [: , [: linkrev@> [: infixes@> [: lines@>@linkrotate [;.2@]

Try it online!

Hooks are useful.

Answer 13

Jelly, 16 bytes

^{Solved a related (possibly a duplicate) challenge with 15 of these 16 bytes as the core of the code...}

ỴZU$3С;ŒD$€Ẏw€Ẹ

A dyadic link accepting a list of characters on the left and a list of characters on the right which returns 1 if found and 0 if not.

Try it online!

How?

ZU$3С;ŒD$€Ẏw€Ẹ - Link: words, grid
   3С          - repeat three times and collect the results (inc input):
  $             -   last two links as a monad:
Z               -     transpose
 U              -     upend     (together these rotate by a quarter)
          €     - for €ach:
         $      -   last two links as a monad:
       ŒD       -     get forward-diagonals
      ;         -     concatenate
           Ẏ    - tighten (to get all the runs across the grid) 
             €  - for €ach run:
            w   -   sublist-index (0 if not found)
              Ẹ - any truthy? (i.e. was the word found?)