Word Search Puzzle

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"

• – edc65 Sep 18 '14 at 16:23

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                              ";


Java : 183 211321

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;
}
}

• if(e<1)return 1>0; could be return e<1; couldn't it? – FryAmTheEggman Sep 18 '14 at 16:39
• @FryAmTheEggman No, that would return after finding the first failure, so it wouldn't search the whole grid. – Geobits Sep 18 '14 at 16:40
• Ah sorry, got kinda lost in there ;_; – FryAmTheEggman Sep 18 '14 at 16:43
• The out two for loops could be collapsed into one instead so you'd do i=a*9, and for(;i-->0;) and then z=i/9; and i%a!=4& and so on? – Will Sep 19 '14 at 8:19
• Wow, this is so similar to mine. And I only glanced at it after I'd already started. I didn't take time to see how it works. +1. – Level River St Sep 19 '14 at 15:17

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


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.

• I think you can save 6 characters by using h,n=input() and print. Also, does this work with non-square inputs? (m=len(n)? I admit to not fully understanding what you are doing, so I might be completely wrong!) – FryAmTheEggman Sep 18 '14 at 16:29
• @FryAmTheEggman: Yes, it works with nonsquare inputs. – Ell Sep 18 '14 at 16:52
• Some standard Python optimizations: while i>0 to while i: (since i can never become negative), if m<1:i=-1 to i-=m<1. – xnor Sep 18 '14 at 19:46
• @xnor I think you may have misread if m<1:i=-1 as if m<1:i-=1 as neither of those will work because he is setting i to be negative. – FryAmTheEggman Sep 18 '14 at 20:28
• @FryAmTheEggman Oh, yes, I totally did misread that. – xnor Sep 18 '14 at 20:36

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$

• 1. I was about to suggest T()(tee >(r) $@), but that's even better. 2. I don't think I've ever seen that function syntax before. 3. Considering non-empty strings truthy and empty strings falsy, I think you can omit -q. – Dennis Sep 18 '14 at 19:08 • If you define r()(tee >(rev)$@), r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep "$1" should work as well. – Dennis Sep 18 '14 at 19:39
• I haven't tested anything else, but the two test cases in the question checked out when I tried. – Dennis Sep 18 '14 at 19:54
• @Dennis Nice - yep it works now. I checked with Martin - he wants the -q to remain. – Digital Trauma Sep 18 '14 at 22:19

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


C# - 218197 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;
}
}


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. Python 2 - 246 259275308298297294313322 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" • L=len;J=''.join etc and print any(s in(v,d,w,r...)) ? I was going along the same lines when I saw you posted :) – Will Sep 18 '14 at 15:48 • @Will Thanks for the help! Defining len costs just as many characters as it saves, and I'm not sure about how to define join optimally (some have commas), so I'll do it in a bit. – FryAmTheEggman Sep 18 '14 at 16:12 • Anywhere you have ) or ] followed by a space, you can take out the space. – undergroundmonorail Sep 20 '14 at 1:22 APL (Dyalog Classic), 44 bytes 1∊⍞⍷↑{⍉0,⍵,↑(0,⊢)\↓0,⍵}¨{⍉⌽⍵}\4⍴⊂↑a⊆⍨a≠⊃⌽a←⎕  Try it online! • Um, I'm sorry, but it seems that you can't get input like that here, it needs to be \n-separated (that is, having ⎕TC[2] as the separator). – Erik the Outgolfer May 6 '18 at 12:07 • @EriktheOutgolfer oh crap... I'll fix it later. Thanks. – ngn May 6 '18 at 13:07 • fixed now, unfortunately much longer – ngn May 6 '18 at 14:25 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. • It seems that this works too. (51 bytes) – user202729 Apr 21 '18 at 11:07 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?)