11
\$\begingroup\$

This question already has an answer here:

The Challenge

Given a list of words and a grid of letters, your job is to determine which of the given words can be found on the grid in all 8 directions (forward, backward, up, down, and the 4 diagonal directions), much like a word search. The grid is toroidal, so the grid wraps around on the edges. Letters can be reused with this wrap-around property.

Wrapping around for diagonals behaves as you might expect. On a 4x6 grid going diagonally down and right, you would expect movement to look like this:

9 . 5 . 1 .
. . . 6 . 2
3 . . . 7 .
. 4 . . . 8

For an example of a wrap-around reuse word:

S E A H O R

Would be able to make SEAHORSE

Example Test Cases

Given this grid and the word list [ANT, COW, PIG]:

A N T
W C O
P G I

The result would be [ANT, COW, PIG]


Given this grid and the word list [CAT, DOG, DUCK, GOOSE, PUMPKIN]:

N O O D M E
O I O C U U
P G K O T C
K A U P S K

The result would be [DOG, DUCK, PUMPKIN]


Given this grid and the word list [TACO, BEEF, PORK]:

T A C B
A P O R
K E E F
B F C P

The result would be an empty list


Given this grid and the word list [ACHE, ASK, BAD, BOOK, COOK, CROW, GAS, GOOD, LESS, MARK, MASK, MEAL, SAME, SEAHORSE, SELL, SHOW, SLACK, WOOD]:

G S L A C K 
H A E S R O
C M S K O O
A K S D W B

The result would be [ASK, BOOK, COOK, CROW, GAS, GOOD, LESS, MASK, SEAHORSE, SHOW, SLACK]


Given this grid and a list of all English words that are at least 3 letters long:

A R T U P
N T U B O
E S R O H
Q E T I U
E A T D P

The result would be [AEQ, AES, ANE, ART, ARTS, ATRIP, BOID, BON, BREE, BUD, BUT, DUB, DUE, DUET, EAN, EAR, EAT, EER, EST, HES, HIT, HOP, HOR, HORS, HORSE, HUP, NAE, NOB, NOBUT, ONT, OOT, OPP, ORS, OUR, OUT, PAR, PART, PAT, PEA, PEAT, PEE, PEER, PIR, POH, PUT, QAT, QUI, QUIT, QUITE, RAP, REE, RIP, RIPA, RTI, RUT, SEA, SEAR, STD, STR, STRA, STRAE, SUU, TAA, TAE, TAP, TAPIR, TEE, TIU, TOO, TRA, TRAP, TRI, TRIP, TUB, TUP, TUR, UDI, UIT, URE, UTE]

Rules

  • No exploiting standard loopholes
  • This is , so shortest code wins
  • Input and output may be in any convenient format
  • You may assume that both the grid and the words list will use only capital letters
  • The output order of the words does not matter
  • You do not have to, but may, filter out duplicates
\$\endgroup\$

marked as duplicate by mbomb007 code-golf May 8 '18 at 21:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Related. \$\endgroup\$ – Oliver May 5 '18 at 5:20
  • \$\begingroup\$ @Lynn Even though I can think of one other approach, I agree, it too reduces to WSP. \$\endgroup\$ – Erik the Outgolfer May 5 '18 at 14:10
  • \$\begingroup\$ Where were all of you when this was in the sandbox? Just saying. It got 3 upvotes there. \$\endgroup\$ – Beefster May 8 '18 at 22:25
3
\$\begingroup\$

Jelly, 25 bytes

Lẋ@Zɗ⁺ZU$3С;ŒD$€Ẏw€⁸ẸðÐf

A dyadic link accepting a list of lists of characters (the words) on the left and a list of lists of characters (the rows of the grid) on the right which returns a list of list of characters (the found words).

Try it online!

How?

Filters the words by their existence in the grid tiled to be word-length times as wide and word-length times as high:

Lẋ@Zɗ⁺ZU$3С;ŒD$€Ẏw€⁸ẸðÐf - Link: words, grid
                       Ðf - filter (the words) keeping those for which
                      ð   - ...the dyadic link to the left ...is truthy:
     ⁺                    -   perform this twice:
    ɗ                     -     last three links as a dyad:
L                         -       length (of the current word)
 ẋ@                       -       repeat (the rows) by (that number)
   Z                      -       transpose (making the rows become the columns)
         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)
                    ⁸     -   chain's left argument (the word)
                   €      -   for €ach run:
                  w       -     sublist-index (0 if not found)
                     Ẹ    -   any truthy? (i.e. was the word found?)
\$\endgroup\$
1
\$\begingroup\$

Clojure, 203 180 bytes

#(let[C count R range h(C %)w(C(% 0))](for[Q %2[y x][[1 0][0 1][-1 0][0 -1][1 1][1 -1][-1 -1][-1 1]]r(R h)c(R w):when(=(for[i(R(C Q))]((%(mod(+(* y i)r)h))(mod(+(* x i)c)w)))Q)]Q))

The grid must be a vector of vector of characters and the word list must be a sequence of sequence of characters. Sorry, no strings ;)

\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 269 214 bytes

(l,g)=>l.filter(w=>g.some((r,y)=>r.some((c,x,r,e=w.split``,m=(a,b)=>((a%b)+b)%b)=>[[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]].some(v=>e.every((h,i)=>h==g[m(v[0]*i+y,g.length)][m(v[1]*i+x,r.length)])))))

Try it online!

Semi readable versoin:

(l, g) =>
    l.filter(w =>
        g.some((r, y) => //loop through rows
            r.some((c, x, r, e = w.split``, //loop through columns and split word in chars
                m = (a, b) => ((a % b) + b) % b) //modulo function which also works for negative
                =>
                [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]].some(v => //the different directions
                    e.every((h, i)
                        => h == g[m(v[0] * i + y, g.length)][m(v[1] * i + x, r.length)]
                    )
                )
            )
        )
    )
\$\endgroup\$

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