Учитывая прямоугольный текст как загадку поиска слова и строку поиска, определите, содержит ли текст строку поиска. Поисковая строка может появиться:

• горизонтально, вертикально или по диагонали
• вперед или назад

Вы можете написать функцию или программу и взять две строки в качестве входных данных через аргумент функции, ARGV или STDIN. Вывод должен быть верным или ложным результатом, который можно либо вернуть из функции, либо записать в STDOUT.

Предположим, что текст будет содержать произвольные печатаемые символы ASCII (шестнадцатеричные коды от 20 до 7E) и символы разрыва строки. Буквы чувствительны к регистру. Вы можете предположить, что входной текст является прямоугольным, то есть все строки имеют одинаковую длину. Вы можете указать, заканчивается ли ввод завершающим переводом строки (если это важно для вашего представления).

Это код гольф, самый короткий ответ (в байтах) выигрывает.

Примеры

Используя эту сетку из статьи Википедии о поиске слов в качестве первого ввода:

WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

Следующие строки поиска должны давать правдивые или ложные результаты соответственно:

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

В качестве альтернативы, используя этот входной текст

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.

Мы получаем следующие результаты поиска (используя кавычки, потому что в некоторых строках поиска есть пробелы):

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

CJam, 46 37 байт

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

Читает сетку из STDIN и слово в качестве аргумента командной строки. Печатает положительные целые числа для совпадений и 0 для несоответствий.

За счет двух дополнительных байтов обе строки (слово, перевод строки, сетка) могут быть прочитаны из STDIN:

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

Вы можете попробовать эту версию онлайн с переводчиком CJam .

Пример запуска

$ 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

Задний план

Предположим, что вход был следующей сеткой:

ABCD
EFGH
IJKL

Разбивая строки, мы получаем следующий массив:

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

Это охватывает восточные слова (слова, идущие слева направо).

Теперь мы объединяем элементы Aиспользования строки len(A)перевода строки в качестве разделителя:

"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

Затем мы нарезаем полученную строку на куски длины len(A) + len(A[0]) + 1:

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

Если мы «заархивируем» массив (транспонируем строки и столбцы), получим:

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

Это охватывает юго-восточные слова.

Если мы застегнем A и изменим порядок строк результата, мы получим:

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

Это охватывает юг и - после повторения процесса для диагоналей - юго-западные слова.

Застегнув молнию и задний ход, мы получаем:

[
    "LKJI"
    "HGFE"
    "DCBA"
]

Это охватывает Запад и - после повторения процесса для диагоналей - северо-западные слова.

Застегивая и переворачивая еще раз, мы получаем:

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

Это охватывает Север и - после повторения процесса для диагоналей - северо-восточные слова.

Как это работает

Код выполняет действия, описанные в предыдущем разделе, с двумя небольшими отличиями:

• Он застегивается и переворачивается один раз в самом начале.
• Это вычисляется len(A) + len(A[0])как len(A + zip(A)).

Наконец, он объединяет все строки всех сгенерированных массивов, используя перевод строки в качестве разделителей, и ищет слово в результирующей строке.

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

Ява: 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;}

Основная грубая сила. Думаю, больше нечего сказать. Ввод - игла первая и стог сена вторая. Предполагается, что сетка завершена новой строкой .

Немного более читаемая версия с показанным тестовым примером:

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

Грубая сила ищет каждого персонажа во всех направлениях - как можно лучше в гольфе

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

Тест In 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)))

Выход

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

Питон, 175

Не очень вдохновляет, но здесь идет:

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

Первый аргумент - стог сена, второй - иголка.

Bash + coreutils, 214 169 байт

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"

Использует 3 функции преобразования r, tи dдля реверса, транспонирования и диагонального сдвига во всех необходимых комбинациях.

Обновление - rтеперь функция производит обратный и не обратный вывод для дополнительной игры в гольф

Ввод с помощью аргументов командной строки - строка поиска, за которой следует (разделенный новой строкой) прямоугольный блок поиска слов.

Выход - идиоматически правильный код состояния выхода оболочки - 0 означает ИСТИНА и 1 означает ЛОЖЬ.

Выход:

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

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

Никакой перестановки сетки, я просто пробую каждую начальную букву в каждом направлении и иду вперед, пока не убегу из сетки или не найду несоответствие.

Я использую тот факт, что строка C заканчивается нулевым байтом. Поскольку в сетке нет нулевых байтов, ВСЕГДА будет несоответствие. Но если несоответствие происходит в нулевом байте, мы знаем, что нашли конец строки для поиска, и запишите это как совпадение.

Разгружен в тестовой программе

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

Выход

Обратите внимание, что функция вернет общее количество совпадений искомой строки в сетке. Таким образом, для ODнего возвращается 6. Если никакие инциденты не найдены, он возвращает 0, что является единственным ложным значением в C. Изменение y|=d*!n[j]приведет к сохранению одного символа, но утратит эту функциональность.

$ ./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 байтов

Функция C #, которая принимает 2 строки: первое слово для поиска, затем сетка с переводами строк ( \n) между строками. Теперь все становится отчаянным ... настолько отчаянным , что мое предыдущее редактирование не сработало!

Гольф-код:

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

Меньше гольфа с тестовым кодом:

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

Хаскелл - 173

Вместо того, чтобы искать прямо в сетке, я трансформирую сетку по-разному и сопоставляю слово с каждой строкой новой сетки.

Например,

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

Найдите слово в каждом ряду G1, G2, G4 и G5, и все готово. Обратите внимание, что G3 не используется, я выкладываю его здесь только для иллюстрации.

Аналогичная идея применяется для поиска вперед и назад: просто искать оригинальное слово и обратное слово.

Итак, теперь мы искали 8 направлений. Вот код, правильность которого проверена другим скриптом .

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]

Функция f- это то, что мы хотим, и ее аргумент r- это прямоугольная строка, wэто слово для поиска.

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

Спасибо Уиллу за помощь в работе с печатью и определение соединения.

Спасибо подземной железной дороге за то, что напомнил мне о местах для гольфа должным образом; p

Исправлено для плохих совпадений благодаря использованию «,» в качестве разделителя.

Видимо, лучший способ игры в гольф - добавить тонны горизонтальной прокрутки.

Вводите в виде пробелов, разделяя строки, разделенные новой строкой, в кавычках: "WVERTICALL \ nROOAFFLSAB \ nACRILIATOA \ nNDODKONWDC \ nDRKESOODDK \ nOEEPZEGLIW \ nMSIIHOAERA \ nALRKRRIRER \ nKODIDEDRLE \ nHEL"

APL (Дьялог Классик) , 44 байта

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

Попробуйте онлайн!

J , 60 53 байта

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

Попробуйте онлайн!

Требует, чтобы первый ввод не содержал новых строк.

Объяснение:

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

Попробуйте онлайн!

Крючки полезны.

Желе , 16 байт

^{Решил связанную (возможно, дублирующуюся) задачу с 15 из этих 16 байтов в качестве ядра кода ...}

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

Диадическая ссылка, принимающая список символов слева и список символов справа, который возвращает 1, если найден, и 0, если нет.

Попробуйте онлайн!

Как?

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