Étant donné un texte rectangulaire comme puzzle de recherche de mots et une chaîne de recherche, déterminez si le texte contient la chaîne de recherche. La chaîne de recherche peut apparaître:

• horizontalement, verticalement ou en diagonale
• en avant ou en arrière

Vous pouvez écrire une fonction ou un programme et prendre deux chaînes en entrée via l'argument de fonction, ARGV ou STDIN. La sortie doit être un résultat véridique ou falsifié qui peut être renvoyé par la fonction ou écrit dans STDOUT.

Supposons que le texte contienne des caractères ASCII imprimables arbitraires (codes hexadécimaux 20 à 7E) et des caractères de saut de ligne. Les lettres sont sensibles à la casse. Vous pouvez supposer que le texte saisi est rectangulaire, c'est-à-dire que toutes les lignes ont la même longueur. Vous pouvez décider si l'entrée se termine par une nouvelle ligne de fin ou non (si cela est important pour votre soumission).

C'est le golf de code, la réponse la plus courte (en octets) l'emporte.

Exemples

En utilisant cette grille de l'article de Wikipedia sur les recherches de mots comme première entrée:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

les chaînes de recherche suivantes devraient respectivement donner des résultats vrais ou faux:

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

Alternativement, en utilisant ce texte d'entrée

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.

Nous obtenons les résultats de recherche suivants (en utilisant des guillemets maintenant, car il y a des espaces dans certaines chaînes de recherche):

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

CJam, 46 37 octets

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

Lit la grille depuis STDIN et le mot comme argument de ligne de commande. Imprime des entiers positifs pour les correspondances et 0 pour les non-correspondances.

Au prix de deux octets supplémentaires, les deux chaînes (mot, saut de ligne, grille) peuvent être lues depuis STDIN:

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

Vous pouvez essayer cette version en ligne avec l' interprète CJam .

Exemple d'exécution

$ 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

Contexte

Supposons que l'entrée était la grille suivante:

ABCD
EFGH
IJKL

En séparant les sauts de ligne, nous obtenons le tableau suivant:

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

Cela couvre les mots orientaux (mots allant de gauche à droite).

Maintenant, nous joignons les éléments de l' Autilisation d'une chaîne de len(A)sauts de ligne comme séparateur:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Ensuite, nous coupons la chaîne résultante en morceaux de longueur len(A) + len(A[0]) + 1:

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

Si on "zip" le tableau (transpose des lignes et des colonnes), on obtient:

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

Cela couvre les mots du Sud-Est.

Si nous compressons A et inversons l'ordre des lignes du résultat, nous obtenons:

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

Cela couvre le Sud et - après avoir répété le processus pour les diagonales - les mots du Sud-Ouest.

En zippant et en inversant à nouveau, on obtient:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

Cela couvre l'Ouest et - après avoir répété le processus pour les diagonales - les mots du Nord-Ouest.

En zippant et en inversant une fois de plus, nous obtenons:

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

Cela couvre le Nord et - après avoir répété le processus pour les diagonales - les mots du Nord-Est.

Comment ça marche

Le code fait comme expliqué dans la section précédente, avec deux différences mineures:

• Il zippe et s'inverse une fois au tout début.
• Il calcule len(A) + len(A[0])comme len(A + zip(A)).

Enfin, il joint toutes les lignes de tous les tableaux générés en utilisant des sauts de ligne comme séparateurs et recherche le mot dans la chaîne résultante.

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

Une force brute de base. Il n'y a pas grand-chose d'autre à dire, je suppose. L'entrée est l'aiguille en premier et la botte de foin en second. Suppose que la grille se termine par une nouvelle ligne .

Une version légèrement plus lisible avec un cas de test illustré:

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

Recherche de force brute pour chaque personnage dans toutes les directions - aussi golfé que possible

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 dans la console 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)))

Sortie

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

Python, 175

Pas très inspiré, mais voici:

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

Le premier argument est la botte de foin, le deuxième est l'aiguille.

Bash + coreutils, 214 169 octets

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"

Utilise 3 fonctions de transformation r, tet dpour inverser, transposer et décalage diagonal, dans toutes les combinaisons nécessaires.

Mise à jour - la rfonction produit désormais une sortie inversée et non inversée pour plus de golf

Saisie via des arguments de ligne de commande - chaîne de recherche, suivie d'un bloc de recherche de mots rectangulaire (séparé par une nouvelle ligne).

La sortie est un code d'état de sortie de shell idiomatiquement correct - 0 signifiant VRAI et 1 signifiant FAUX.

Sortie:

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

Pas de réarrangement de la grille, j'essaie simplement chaque lettre de départ dans toutes les directions, et je marche jusqu'à ce que je sors de la grille ou que je trouve un décalage.

Je profite du fait qu'une chaîne C se termine par un octet zéro. Comme il n'y a pas zéro octet dans la grille, il y aura TOUJOURS un décalage. Mais si la non-concordance se produit à l'octet zéro, nous savons que nous avons trouvé la fin de la chaîne à rechercher et l'enregistrons en tant que correspondance.

Non golfé dans un programme de test

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

Sortie

Notez que la fonction renverra le nombre total d'incidences de la chaîne recherchée dans la grille. Ainsi, ODil renvoie 6. Si aucune incidence n'est trouvée, il renvoie 0, ce qui est la seule valeur de fausse en C. Changer pour y|=d*!n[j]sauverait un caractère mais perdrait cette fonctionnalité.

$ ./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 octets

Fonction C # qui prend 2 chaînes, le premier mot à rechercher, plus tard la grille avec des sauts de ligne ( \n) entre les lignes. Les choses deviennent désespérées maintenant ... si désespérées en fait que ma précédente édition n'a pas fonctionné!

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

Moins joué avec le code de test:

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

Au lieu de chercher directement sur la grille, je transforme la grille de différentes manières et fais correspondre le mot avec chaque ligne de la nouvelle grille.

Par exemple,

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

Recherchez le mot dans chaque ligne de G1, G2, G4 et G5, puis nous avons terminé. Notez que G3 n'est pas utilisé, je le poste ici juste à titre d'illustration.

Une idée similaire est appliquée pour rechercher en avant et en arrière: il suffit de rechercher le mot d'origine et le mot inversé.

Alors maintenant, nous avons cherché 8 directions. Voici le code, dont l'exactitude a été vérifiée par un autre 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 fonction fest ce que nous voulons et son argument rest la chaîne rectangulaire, wc'est le mot à rechercher.

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

Merci à Will pour son aide dans le traitement de l'impression et la définition de la jointure.

Merci au chemin de fer souterrain de m'avoir rappelé correctement les espaces de golf; p

Correction des mauvaises correspondances grâce à l'utilisation de "," comme délimiteur.

Apparemment, la meilleure façon de jouer au golf est d'ajouter des tonnes de défilement horizontal.

Entrée en espaces coup de saut de ligne délimité lignes entre guillemets: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODIDEDRCD \ nHELWSLEUTH", "ALEATOIRE"

APL (Dyalog Classic) , 44 octets

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

Essayez-le en ligne!

J , 60 53 octets

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

Essayez-le en ligne!

Nécessite que la première entrée ne contienne aucune nouvelle ligne.

Explication:

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

Essayez-le en ligne!

Les crochets sont utiles.

Gelée , 16 octets

^{Résolution d'un problème connexe (éventuellement un doublon) avec 15 de ces 16 octets au cœur du code ...}

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

Un lien dyadique acceptant une liste de caractères à gauche et une liste de caractères à droite qui renvoie 1 si trouvé et 0 sinon.

Essayez-le en ligne!

Comment?

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