Dado un texto rectangular como un rompecabezas de búsqueda de palabras y una cadena de búsqueda, determine si el texto contiene la cadena de búsqueda. La cadena de búsqueda puede aparecer:

• horizontal, vertical o diagonal
• hacia adelante o hacia atrás

Puede escribir una función o un programa y tomar dos cadenas como entrada a través del argumento de la función, ARGV o STDIN. La salida debe ser un resultado verdadero o falso que puede ser devuelto desde la función o escrito en STDOUT.

Suponga que el texto contendrá caracteres ASCII imprimibles arbitrarios (códigos hexadecimales 20 a 7E) y caracteres de salto de línea. Las letras distinguen entre mayúsculas y minúsculas. Puede suponer que el texto de entrada es rectangular, es decir, todas las líneas tienen la misma longitud. Puede saber si la entrada termina con una nueva línea final o no (si es importante para su envío).

Este es el código de golf, gana la respuesta más corta (en bytes).

Ejemplos

Usando esta cuadrícula del artículo de Wikipedia sobre búsquedas de palabras como la primera entrada:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

las siguientes cadenas de búsqueda deberían arrojar resultados verdaderos o falsos, respectivamente:

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

Alternativamente, usando este texto de entrada

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.

Obtenemos los siguientes resultados de búsqueda (usando comillas ahora, porque hay espacios en algunas cadenas de búsqueda):

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

CJam, 46 37 bytes

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

Lee la cuadrícula de STDIN y la palabra como argumento de línea de comandos. Imprime enteros positivos para coincidencias y 0 para no coincidencias.

A costa de dos bytes adicionales, ambas cadenas (palabra, salto de línea, cuadrícula) se pueden leer desde STDIN:

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

Puede probar esta versión en línea con el intérprete de CJam .

Ejecución de ejemplo

$ 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

Fondo

Suponga que la entrada fue la siguiente cuadrícula:

ABCD
EFGH
IJKL

Partiendo en saltos de línea, obtenemos la siguiente matriz:

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

Eso cubre las palabras del este (palabras que van de izquierda a derecha).

Ahora, unimos los elementos del Auso de una cadena de len(A)avances de línea como separador:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Luego, cortamos la cadena resultante en trozos de longitud len(A) + len(A[0]) + 1:

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

Si "comprimimos" la matriz (transponemos filas y columnas), obtenemos:

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

Eso cubre las palabras del sudeste.

Si comprimimos A e invertimos el orden de las filas del resultado, obtenemos:

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

Eso cubre el Sur y, después de repetir el proceso para las diagonales, las palabras del Sudoeste.

Comprimiendo e invirtiendo de nuevo, obtenemos:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

Eso cubre el oeste y, después de repetir el proceso para las diagonales, las palabras del noroeste.

Comprimiendo y retrocediendo una vez más, obtenemos:

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

Eso cubre el norte y, después de repetir el proceso para las diagonales, las palabras del noreste.

Cómo funciona

El código hace lo explicado en la sección anterior, con dos diferencias menores:

• Se cierra e invierte una vez al principio.
• Se calcula len(A) + len(A[0])como len(A + zip(A)).

Finalmente, une todas las filas de todas las matrices generadas utilizando avances de línea como separadores y busca la palabra en la cadena resultante.

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

Una fuerza bruta básica. No hay mucho más que decir, supongo. La entrada es la aguja primero y el pajar segundo. Asume que la grilla está terminada en nueva línea .

Una versión ligeramente más legible con el caso de prueba que se muestra:

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

JavaScript (E6) 111116

Búsqueda de fuerza bruta para cada personaje en todas las direcciones, tan golfizado como pueda

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)
    )
  )

Prueba en la consola FireFox / Firebug

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

Salida

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

Python, 175

No muy inspirado, pero aquí va:

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

El primer argumento es el pajar, el segundo es la aguja.

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"

Utiliza 3 funciones de transformación r, ty dpara invertir, transponer y desplazamiento diagonal, en todas las combinaciones necesarias.

Actualización: la rfunción ahora produce resultados invertidos y no invertidos para una mayor capacidad de golf

Entrada a través de argumentos de línea de comandos: cadena de búsqueda, seguida de un bloque de búsqueda de palabras rectangular (separado por línea nueva).

La salida es un código de estado de salida de shell idiomáticamente correcto: 0 significa VERDADERO y 1 significa FALSO.

Salida:

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

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

Sin reorganización de la cuadrícula, simplemente intento cada letra de inicio en todas las direcciones, y camino hasta que salgo de la cuadrícula o encuentro una falta de coincidencia.

Aprovecho el hecho de que una cadena C termina en un byte cero. Como no hay cero bytes en la cuadrícula, SIEMPRE habrá una falta de coincidencia. Pero si la falta de coincidencia se produce en el byte cero, sabemos que hemos encontrado el final de la cadena a buscar y lo registramos como una coincidencia.

Sin golf en un programa de prueba

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

Salida

Tenga en cuenta que la función devolverá el número total de incidencias de la cadena buscada en la cuadrícula. Por ODlo tanto , devuelve 6. Si no se encuentran incidencias, devuelve 0, que es el único valor falso en C. Cambiar a y|=d*!n[j]guardaría un carácter pero perdería esta funcionalidad.

$ ./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 # - 218 197 186 bytes

Función C # que toma 2 cadenas, la primera es la palabra a buscar, más tarde la cuadrícula con saltos de línea ( \n) entre líneas. Las cosas se están poniendo desesperadas ahora ... de hecho, tan desesperado que mi edición anterior no funcionó.

Código de golf:

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

Menos golf con código de prueba:

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

En lugar de buscar directamente en la cuadrícula, transformo la cuadrícula de diferentes maneras y relaciono la palabra con cada fila de la nueva cuadrícula.

Por ejemplo,

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

Busque la palabra en cada fila de G1, G2, G4 y G5, y listo. Tenga en cuenta que G3 no se usa, lo publico aquí solo para ilustración.

Se aplica una idea similar para buscar hacia adelante y hacia atrás: solo busca la palabra original y la palabra invertida.

Así que ahora hemos buscado 8 direcciones. Aquí está el código, cuya corrección fue verificada por otro 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]

La función fes lo que queremos y su argumento res la cadena rectangular, wes la palabra a buscar.

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

Gracias a Will por su ayuda con la impresión y la definición de la unión.

Gracias al ferrocarril subterráneo por recordarme a los espacios de golf correctamente; p

Se corrigió por malas coincidencias gracias al uso de ',' como delimitador.

Aparentemente, la mejor manera de jugar al golf es agregar toneladas de desplazamiento horizontal.

Ingrese como espacio en blanco bang líneas delimitadas de nueva línea entre comillas: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODIDEDRCD \ nHELWSLE", "RHANDWAND" n "."

APL (Dyalog Classic) , 44 bytes

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

Pruébalo en línea!

J , 60 53 bytes

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

Pruébalo en línea!

Requiere que la primera entrada no contenga nuevas líneas.

Explicación:

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@]

Pruébalo en línea!

Los ganchos son útiles.

Jalea , 16 bytes

^{Resuelto un desafío relacionado (posiblemente un duplicado) con 15 de estos 16 bytes como núcleo del código ...}

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

Un enlace diádico que acepta una lista de caracteres a la izquierda y una lista de caracteres a la derecha que devuelve 1 si se encuentra y 0 si no.

Pruébalo en línea!

¿Cómo?

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?)