29
\$\begingroup\$

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"
\$\endgroup\$
1

12 Answers 12

8
\$\begingroup\$

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                              ";
\$\endgroup\$
0
7
\$\begingroup\$

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;
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ if(e<1)return 1>0; could be return e<1; couldn't it? \$\endgroup\$ Sep 18, 2014 at 16:39
  • \$\begingroup\$ @FryAmTheEggman No, that would return after finding the first failure, so it wouldn't search the whole grid. \$\endgroup\$
    – Geobits
    Sep 18, 2014 at 16:40
  • 1
    \$\begingroup\$ Ah sorry, got kinda lost in there ;_; \$\endgroup\$ Sep 18, 2014 at 16:43
  • 4
    \$\begingroup\$ 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? \$\endgroup\$
    – Will
    Sep 19, 2014 at 8:19
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Sep 19, 2014 at 15:17
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ 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!) \$\endgroup\$ Sep 18, 2014 at 16:29
  • \$\begingroup\$ @FryAmTheEggman: Yes, it works with nonsquare inputs. \$\endgroup\$
    – Ell
    Sep 18, 2014 at 16:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Sep 18, 2014 at 19:46
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Sep 18, 2014 at 20:28
  • \$\begingroup\$ @FryAmTheEggman Oh, yes, I totally did misread that. \$\endgroup\$
    – xnor
    Sep 18, 2014 at 20:36
5
\$\begingroup\$

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
$ 
\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – Dennis
    Sep 18, 2014 at 19:08
  • \$\begingroup\$ If you define r()(tee >(rev) $@), r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep "$1" should work as well. \$\endgroup\$
    – Dennis
    Sep 18, 2014 at 19:39
  • \$\begingroup\$ I haven't tested anything else, but the two test cases in the question checked out when I tried. \$\endgroup\$
    – Dennis
    Sep 18, 2014 at 19:54
  • \$\begingroup\$ @Dennis Nice - yep it works now. I checked with Martin - he wants the -q to remain. \$\endgroup\$ Sep 18, 2014 at 22:19
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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"

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$
    – Will
    Sep 18, 2014 at 15:48
  • \$\begingroup\$ @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. \$\endgroup\$ Sep 18, 2014 at 16:12
  • \$\begingroup\$ Anywhere you have ) or ] followed by a space, you can take out the space. \$\endgroup\$ Sep 20, 2014 at 1:22
2
\$\begingroup\$

APL (Dyalog Classic), 44 bytes

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

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 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). \$\endgroup\$ May 6, 2018 at 12:07
  • \$\begingroup\$ @EriktheOutgolfer oh crap... I'll fix it later. Thanks. \$\endgroup\$
    – ngn
    May 6, 2018 at 13:07
  • \$\begingroup\$ fixed now, unfortunately much longer \$\endgroup\$
    – ngn
    May 6, 2018 at 14:25
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ It seems that this works too. (51 bytes) \$\endgroup\$
    – DELETE_ME
    Apr 21, 2018 at 11:07
0
\$\begingroup\$

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?)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.