Biorąc pod uwagę prostokątny tekst jako łamigłówkę wyszukiwania słów i ciąg wyszukiwania, określ, czy tekst zawiera szukany ciąg. Wyszukiwany ciąg może się pojawić:

• poziomo, pionowo lub po przekątnej
• do przodu lub do tyłu

Możesz napisać funkcję lub program i wziąć dwa ciągi wejściowe za pomocą argumentu funkcji, ARGV lub STDIN. Wynik powinien być wynikiem zgodnym z prawdą lub fałszem, który może zostać zwrócony z funkcji lub zapisany w STDOUT.

Załóżmy, że tekst będzie zawierał dowolne drukowalne znaki ASCII (kody szesnastkowe od 20 do 7E) i znaki podziału linii. W literach rozróżniana jest wielkość liter. Możesz założyć, że tekst wejściowy jest prostokątny, tzn. Wszystkie linie mają tę samą długość. Możesz określić, czy dane wejściowe kończą się znakiem nowej linii, czy nie (jeśli ma to znaczenie dla przesłania).

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Przykłady

Używając tej siatki z artykułu Wikipedii na temat wyszukiwania słów jako pierwszego wejścia:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

następujące ciągi wyszukiwania powinny dawać odpowiednio wyniki zgodne z prawdą lub fałszem:

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

Alternatywnie, używając tego tekstu wejściowego

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.

Otrzymujemy następujące wyniki wyszukiwania (teraz używamy cudzysłowów, ponieważ w niektórych ciągach wyszukiwania są spacje):

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

CJam, 46 37 bajtów

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

Czyta tabelę ze STDIN i słowa jako argument wiersza poleceń. Wyświetla dodatnie liczby całkowite dla dopasowań i 0 dla niezgodności.

Kosztem dwóch dodatkowych bajtów oba ciągi (słowo, wysuw wiersza, siatka) można odczytać ze STDIN:

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

Możesz wypróbować tę wersję online za pomocą interpretera CJam .

Przykładowy przebieg

$ 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

tło

Załóżmy, że dane wejściowe były następujące:

ABCD
EFGH
IJKL

Dzieląc przy liniach, otrzymujemy następującą tablicę:

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

Dotyczy to słów wschodnich (słowa od lewej do prawej).

Teraz łączymy elementy Aza pomocą ciągu len(A)kanałów liniowych jako separatora:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Następnie tniemy powstały ciąg na kawałki o długości len(A) + len(A[0]) + 1:

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

Jeśli „skompresujemy” tablicę (transponujemy wiersze i kolumny), otrzymamy:

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

Dotyczy to słów z południowego wschodu.

Jeśli skompresujemy A i odwrócimy kolejność wierszy wyniku, otrzymamy:

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

Obejmuje to południe i - po powtórzeniu procesu dla przekątnych - słowa z południowego zachodu.

Ponownie kompresując i cofając, otrzymujemy:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

Dotyczy to Zachodu i - po powtórzeniu procesu dla przekątnych - słów Północno-Zachodnich.

Ponownie kompresując i cofając, otrzymujemy:

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

Dotyczy to północy i - po powtórzeniu procesu dla przekątnych - słów północno-wschodnich.

Jak to działa

Kod działa jak wyjaśniono w poprzedniej sekcji, z dwiema drobnymi różnicami:

• Na początku zamyka się i cofa.
• Oblicza się len(A) + len(A[0])jako len(A + zip(A)).

Wreszcie, łączy wszystkie wiersze wszystkich wygenerowanych tablic, używając linii jako separatorów i szuka słowa w wynikowym ciągu.

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

Podstawowa brutalna siła. Chyba nie ma nic więcej do powiedzenia. Dane wejściowe to igła pierwsza, a stóg siana druga. Zakłada, że ​​siatka jest zakończona znakiem nowej linii .

Nieco bardziej czytelna wersja z pokazanym przypadkiem testowym:

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

Poszukiwania brutalnej siły dla każdej postaci w każdym kierunku - tak golfa, jak tylko potrafię

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

Przetestuj w konsoli 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)))

Wydajność

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

Python, 175

Niezbyt inspirowane, ale oto:

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

Pierwszy argument to stóg siana, drugi to igła.

Bash + coreutils, 214 169 bajtów

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"

Zastosowania transformaty 3 funkcje r, ta ddo tyłu, transpozycji i przekątnej przesunięcie we wszystkich niezbędnych połączeń.

Aktualizacja - rfunkcja generuje teraz odwrócone i nieodwrócone wyjście dla dodatkowej gry w golfa

Wprowadzanie za pomocą argumentów wiersza poleceń - ciąg wyszukiwania, a następnie (oddzielony nowym wierszem) prostokątny blok wyszukiwania słów.

Dane wyjściowe to idiomatycznie poprawny kod statusu wyjścia powłoki - 0 oznacza PRAWDA, a 1 oznacza FAŁSZ.

Wydajność:

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

Bez zmiany układu siatki, po prostu wypróbowuję każdą literę początkową w każdym kierunku i idę, aż zbiegnę z siatki lub znajdę niedopasowanie.

Korzystam z faktu, że ciąg C kończy się na bajcie zerowym. Ponieważ w siatce nie ma zerowych bajtów, ZAWSZE wystąpi niedopasowanie. Ale jeśli niezgodność wystąpi w bajcie zerowym, wiemy, że znaleźliśmy koniec szukanego łańcucha i zapisujemy go jako dopasowanie.

Ungolfed w programie testowym

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

Wydajność

Zauważ, że funkcja zwróci całkowitą liczbę przypadków szukanego ciągu w siatce. Tak więc dla ODzwraca 6. Jeśli nie znaleziono żadnych zdarzeń, zwraca 0, co jest jedyną wartością fałszowania w C. Zmiana na zapisałaby y|=d*!n[j]jeden znak, ale utraciłaby tę funkcjonalność.

$ ./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 bajtów

Funkcja C #, która pobiera 2 ciągi, pierwsze szukane słowo, później siatka z liniami ( \n) między wierszami. Rzeczy stają się teraz desperackie ... tak desperackie , że moja poprzednia edycja nie zadziałała!

Kod do gry w golfa:

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

Mniej golfa dzięki kodowi testowemu:

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

Zamiast szukać bezpośrednio na siatce, przekształcam siatkę na różne sposoby i dopasowuję słowo do każdego wiersza nowej siatki.

Na przykład,

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

Wyszukaj słowo w każdym wierszu G1, G2, G4 i G5, i gotowe. Zauważ, że G3 nie jest używany, zamieszczam go tutaj tylko dla ilustracji.

Podobny pomysł dotyczy wyszukiwania do przodu i do tyłu: wystarczy wyszukać oryginalne słowo i słowo odwrócone.

Więc teraz szukaliśmy 8 kierunków. Oto kod, którego poprawność została zweryfikowana przez inny skrypt .

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]

Funkcja fjest tym, czego chcemy, a jej argumentem rjest ciąg prostokąta, wsłowo do wyszukania.

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

Podziękowania dla Willa za pomoc w radzeniu sobie z drukowaniem i definiowaniem złączenia.

Dzięki podziemnej linii kolejowej za właściwe przypomnienie mi o polach golfowych; str

Naprawiono błędne dopasowania dzięki użyciu „,” jako separatora.

Najwyraźniej najlepszym sposobem na golfa jest dodanie ton przewijania w poziomie.

Wejście jako spacją wybuchu nowej linii wyznaczone linie w cudzysłowie: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODIDEDRCD \ nHELWSLEUTH", "RANDOM"

APL (Dyalog Classic) , 44 bajty

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

Wypróbuj online!

J , 60 53 bajtów

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

Wypróbuj online!

Wymaga, aby pierwsze wejście nie zawierało znaków nowej linii.

Wyjaśnienie:

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

Wypróbuj online!

Haki są przydatne.

Galaretka , 16 bajtów

^{Rozwiązano powiązane (być może duplikat) wyzwanie z 15 z tych 16 bajtów jako rdzeniem kodu ...}

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

Dyadyczny link akceptujący listę znaków po lewej stronie i listę znaków po prawej stronie, która zwraca 1, jeśli znaleziono, i 0, jeśli nie.

Wypróbuj online!

W jaki sposób?

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