Code Golf: поиск слов

Примечание. Это мой первый вопрос / вопрос по Code Golf, поэтому я могу использовать неправильный формат, указанный ниже. Я не совсем уверен, как пометить этот конкретный вопрос, и это должно быть вики сообщества? Спасибо!

Задача Code Golf заключается в поиске слов!

Поиск слова, как определено в Википедии, это:

Поиск слова, поиск слова, поиск слова, словосочетание или загадочное слово-загадка - это игра в слова, представляющая собой буквы слова в сетке, которые обычно имеют прямоугольную или квадратную форму. Цель этой головоломки - найти и отметить все слова, спрятанные внутри коробки. Слова могут быть по горизонтали, вертикали или диагонали. Часто предоставляется список скрытых слов, но более сложные головоломки могут позволить игроку разобраться в них. У многих загадок поиска слов есть тема, с которой связаны все скрытые слова.

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

Ввод, вывод

Пользователь вводит свой поиск слова, а затем вводит слово, которое будет найдено в его сетке. Эти два входа передаются в функцию, которую вы будете писать. Вам решать, как вы хотите объявить и обработать эти объекты.

Используя стратегию, описанную ниже, или вашу собственную, функция находит определенное слово в поиске и выводит его начальные координаты (просто номер строки и номер столбца) и конечные координаты. Если вы найдете два вхождения слова, вы должны вывести оба набора координат. Если слово является палиндромом, вы можете произвольно выбрать один конец в качестве "начала" слова.

пример

Входные данные:

A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M

Слово для поиска: codegolf

Выход:

row 12, column 8 --> row 5, column 1

Стратегии

Вот несколько стратегий, которые вы можете использовать. Вам решать, какую стратегию вы хотите использовать; это не должно быть в этом списке.

  • Ищем первую букву слова; в каждом случае просматривайте восемь окружающих букв, чтобы увидеть, есть ли следующая буква слова.
  • То же, что и выше, за исключением того, что ищите часть слова, которая имеет две одинаковые буквы рядом.
  • Подсчитайте, как часто каждая буква алфавита присутствует во всей сетке, затем выберите одну из наименее встречающихся букв из слова, которое вы должны найти, и найдите букву. При каждом появлении буквы вы смотрите на ее восемь окружающих букв, чтобы увидеть, есть ли следующая и предыдущая буквы слова.
Источник

7 ответов

Решение

Питон - 186 символов

def f(g,W):w=g.find("\n")+1;L=len(W);print" --> ".join("row %s, column %s"%(x/w+1
,x%w+1)for i in range(len(g))for j in(-w-1,-w,-w+1,-1,1,w-1,w,w+1)for x in(i,i+(L
-1)*j)if g[i::j][:L]==W)

код тестирования:

grid="""A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M """.lower().replace(" ","")
f(grid,"codegolf")
f(grid,"serverfault")
f(grid,"superuser")

Эта версия 196 символов и принимает сетку без каких-либо дополнительных настроек

def f(g,W):w=g.find("\n")+1;L=len(W);print" --> ".join("row %s, column %s"%(x/w+1,x%w/2+1)for i in range(len(g))for j in(-w-2,-w,-w+2,-2,2,w-2,w,w+2)for x in(i,i+(L-1)*j)if g[i::j][:L].lower()==W)

код тестирования:

grid="""A I Y R J J Y T A S V Q T Z E 
X B X G R Z P W V T B K U F O 
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M """
f(grid,"codegolf")
f(grid,"serverfault")
f(grid,"superuser")
Источник

Perl, 226 символов

sub h($){"row ",$%=1+($x=pop)/$W,", column ",1+$x%$W}
@S=map/[^ ]/g,<STDIN>;
B:for(@ARGV){
 for$d(map{$_,-$_}1,$W=@S/$.,$W-1,$W+1){
  A:for$s(0..$#S){
   $t=$s-$d;for(/./g){next A if$S[$t+=$d]ne$_||$t<0}
   print h$s,' --> ',h$t,$/;
   next B
}}}

Количество символов исключает переводы строки и отступы, которые включены для удобства чтения. Я предполагаю, что матрица букв определяется стандартным вводом, а целевые слова являются аргументами командной строки.

Первая строка (после sub h определение) отображает все непробельные символы в один массив @S, Затем переберите все целевые слова, возможные направления, в которых слова могут появляться ($W ширина головоломки), и по всем буквам в текущем целевом слове, пока не будет найдено совпадение.

$ perl wordsearch.pl CODEGOLF RACECAR BYKLHQU << EOF
AIYRJJYTASVQTZEXBXGRZ PWVTBKUFOEAFLVFJJIAGB AJKRESUREPUSCYRSYKFBB QYTKOIKHEWGNGLWZFRFHL ORWAREJAOSFUEHQVLOAZB 
JFBGIFQXEEALWACFWKZEU URZRTRACECARPHDFWHFEC GWZBJSVOAOYDLMSTCRBES JUVTCSOOXPFFRJTLCVWRN WLQUFIBLRACECARROWGND 
BCDEJYELWXJDFXM 
EOF
строка 12, столбец 8 -> строка 5, столбец 1
строка 14, столбец 3 -> строка 14, столбец 9
строка 3, столбец 12 -> строка 9, столбец 6
Источник

Perl - 243

(Не включая разрывы строк, все из которых являются необязательными)

В основном код de-golfed можно найти здесь.

$/="";@w=split//,pop;($b=<>)=~y/ //d;$W=1+index$b,"\n";
for(1,2){for(0,$W-2..$W){$p=join"."x$_,@w;
push@m,[$-[0],$+[0]-1]while$b=~/$p/sg}
@w=reverse@w;@m=map[reverse@$_],@m}
$t="row %d, column %d";
printf"$t --> $t\n",map{1+$_/$W,1+$_%$W}@$_ for@m;

Использование: запустить как скрипт. Или wordsearch.pl boardfile searchword читать из файла, или wordsearch.pl searchword читать доску из STDIN (эй, pop на два символа короче shift!)

Идея состоит в том, что мы читаем доску в строку (отбрасывая лишние пробелы между буквами), а также отмечаем ее ширину (считая символы до первой новой строки). Затем мы делаем серию регулярных выражений, чтобы найти слово, используя s Модификатор regex, позволяющий совпадать со строками. Учитывая доску шириной в 4 буквы (каждая строка состоит из 5 символов, включая перевод строки) и поисковое слово "CAR", мы можем сделать шаблоны /CAR/ соответствовать нападающим, /C...A...R/ чтобы идти на юго-запад, /C....A....R/ соответствовать спускаясь вниз, и /C.....A.....R/ соответствовать идущему на юго-восток. Для каждого матча мы записываем начальную и конечную позиции матча.

Затем мы обращаем поисковое слово ("CAR" -> "RAC") и делаем это снова, что позволяет сопоставить слово, идущее влево, вверх, на северо-запад и на северо-восток. Конечно, мы хотим убедиться, что начальная / конечная позиции также поменялись местами. Чтобы сохранить код, я меняю местами совпадения дважды; совпадения для переднего слова меняются местами оба раза (поэтому они выходят без замены), в то время как совпадения для обратного слова меняются местами только один раз, поэтому они получаются замененными.

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

Источник

AWK - 252 255

NF<2{l=split($1,w,"")}NF>1{for(i=1;i<=NF;)t[x=i++,y=NR]=$i}END{
for(i=1;i<=x;++i)for(j=0;++j<=y;)for(a=0;a<9;++a)if(t[I=i,J=j]==w[1])
for(k=1;k<l;){if(!(T=t[I+=int(a/3)-1,J+=a%3-1])||T!=w[++k])break;if(k==l)
print"row "j (B=", column ")i" --> row "J B I}}

Ввод должен быть в форме

....
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M 
CODEGOLF
Источник

Питон, 318 ударов.

from itertools import*
f=lambda x,y,i,j,n:(x-i+1,y-j+1)*(not n)or all((2*i+j,x+1,y+1,x<c,y<d))and a[x][y*2]==n[0]and f(x+i,y+j,i,j,n[1:])
w=raw_input
a=list(iter(w,''))
c=len(a)
d=len(a[0])/2
r=range
z=r(-1,2)
s='row %d, column %d'
for x in product(r(c),r(d),z,z,[w()]):
 if f(*x):print s%(x[0]+1,x[1]+1),'-->',s%f(*x)

Пример ввода:

A I Y R J J Y T A S V Q T Z E 
X C O D E G O L F B K U F O Z
E A F L V F J J I A G B A J K 
R E S U R E P U S C Y R S Y K 
F B B Q Y T K O I K H E W G N 
G L W Z F R F H L O R W A R E 
J A O S F U E H Q V L O A Z B 
J F B G I F Q X E E A L W A C 
F W K Z E U U R Z R T N P L D 
F L M P H D F W H F E C G W Z 
B J S V O A O Y D L M S T C R 
B E S J U V T C S O O X P F F 
R J T L C V W R N W L Q U F I 
B L T O O S Q V K R O W G N D 
B C D E J Y E L W X J D F X M 

CODEGOLF

Выход:

$ python wordsearch < wordsearchinput.txt
row 2, column 2 --> row 2, column 9
row 12, column 8 --> row 5, column 1

Выпущено по лицензии "отредактируйте ответ вместо того, чтобы комментировать, как я должен исправить это".

Источник

C++ C, 411 400 388 367 символов

Моя первая попытка в коде гольф.

#include<stdio.h>
main(){char m[999],w[99];int r,c,l=-1,x=-1,y=-1,i=0,j,k;scanf("%s %d %d"
,w,&r,&c);for(;w[l+1];++l);for(;i<r*c;scanf("%s",&m[i++]));for(;y<2;++y)
for(;x<2;++x)if(x|y)for(i=(y<0)*l;i<r-(y>0)*l;++i)for(j=(x<0)*l;j<c-(x>0
)*l;++j)for(k=0;k<=l&&w[k++]==m[(i+k*y)*c+j+k*x];)k>l?printf(
"row %i, column %i --> row %i, column %i\n",i+1,j+1,i+y*l+1,j+x*l+1):0;}

Он компилируется без предупреждения на gcc без дополнительных флагов.

Вот версия с пробелами:

#include<stdio.h>
main() {
    char m[999], w[99];
    int r, c, l = -1, x = -1, y = -1, i = 0, j, k;

    scanf("%s %d %d", w, &r, &c);
    for (; w[l+1]; ++l);
    for (; i < r*c; scanf("%s", &m[i++]));
    for (; y < 2; ++y)
        for (; x < 2; ++x)
            if (x | y)
                for (i = (y<0) * l; i < r - (y>0) * l; ++i)
                    for (j = (x<0) * l; j < c - (x>0) * l; ++j)
                        for (k = 0; k <= l && w[k++] == m[(i+k*y) * c + j+k*x];)
                            k > l ? printf("row %i, column %i --> row %i, column %i\n",
                                    i + 1, j + 1, i + y*l + 1, j + x*l + 1)
                                  : 0;
}

Ожидаемый ввод на stdin выглядит так:

CODEGOLF 15 15
A I Y R J J Y T A S V Q T Z E
X B X G R Z P W V T B K U F O
...

где 15 15 являются номерами строк и столбцов, соответственно.

Так как это мой первый раунд игры в гольф, и я мог найти в интернете ценные маленькие хитрости, я перечислю некоторые из них, которые нашел:

  • Старайтесь держать тела цикла в одном выражении, чтобы сэкономить на усах (2 символа).
    Пример: все, что использует оператор запятой.

  • Используйте условное выражение (?:) вместо if когда вы можете (1 символ).
    Пример: вместо if(x)printf("");, записывать x?printf(""):0;, Это работает, потому что printf возвращается int,

  • Используйте тот факт, что логические 0 или же 1 когда используется как int (? символы).
    Пример: вместо (y>0?r-l:r), записывать r-(y>0)*l, Экономия здесь в скобках, которые были необходимы в этой ситуации.

  • while петли никогда не короче for циклы и дольше в большинстве случаев (>= 0 символов).
    Пример: while(x)y; так же долго, как for(;x;y); но с for Вы также можете использовать тело цикла, не платя за ;,

  • Поместите ваши приращения цикла в последнее выражение, которое использует счетчик цикла (1 символ).
    Пример: вместо for(;x<b;++x)printf("%i",x);, записывать for(;x<b;)printf("%i",x++);,

  • Оставить mainТип возврата (4 символа).

  • Оставить main"s return заявление (9 символов).

  • использование & а также | вместо && а также || по возможности (1 символ).
    Пример: вместо if(x||y), записывать if(x|y), Это работает, только если вы не зависите от поведения короткого замыкания && а также ||,

  • Инлайн strlen функционировать и удалять #include<string.h> (11 символов).

Если вас не волнуют предупреждения компилятора:

  • Не включайте заголовки (много символов).
Источник

Python: 491 - 353 символа

Полагаю, что еще есть что улучшить, все комментарии приветствуются.

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

import sys;r=range(-1,2);k=''.join;q="row %s, column %s"
a=[l[:-1:2]for l in sys.stdin]
b=sys.argv[1];c=len(a[0])
for x,y in[(x/c,x%c)for x,h in enumerate(k(map(k,a)))]:
 for i,j in[(i,j)for i in r for j in r if i or j<>0]:
  if k([a[x+z*i][y+z*j]for z in range(len(b))if 0<=x+z*i<c and 0<=y+z*j<len(a)])==b:print q%(x+1,y+1)+" --> "+q%(x+z*i+1,y+z*j+1)

Пример использования:

cat input.txt | python test.py CODEGOLF

Пример вывода:

строка 12, столбец 8 -> строка 5, столбец 1

Источник
Другие вопросы по тегам