24

注意:这是我的第一个 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

策略

以下是您可能会考虑使用的一些策略。完全由您决定要使用哪种策略;它不必在此列表中。

  • 寻找单词的第一个字母;每次出现时,查看周围的八个字母,看看单词的下一个字母是否存在。
  • 与上面相同,除了寻找一个单词的一部分,它有两个并排的相同字母。
  • 计算字母表中每个字母在整个网格中出现的频率,然后从您必须找到的单词中选择一个出现次数最少的字母并搜索该字母。每次出现该字母时,您都会查看其周围的八个字母,以查看该单词的下一个和前一个字母是否存在。
4

7 回答 7

12

Python - 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")
于 2010-04-06T21:06:21.883 回答
8

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
AIYRJJYTASVQTZE
XBXGRZPWVTBKUFO
EAFLVFJJIAGBAJK
RESUREPUSCYRSYK
FBBQYTKOIKHEWGN
GLWZFRFHLORWARE
JAOSFUHQVLOAZB
JFBGIFQXEEALWAC
FWKZEUURZRTRACE
CARPHDFWHFECGWZ
BJSVOAOYDLMSTCR
BESJUVTCSOOXPFF
RJTLCVWRNWLQUFI
BLRACECARROWGND
BCDEJYELWXJDFXM
EOF
第 12 行,第 8 列 --> 第 5 行,第 1 列
第 14 行第 3 列 --> 第 14 行第 9 列
第 3 行,第 12 列 --> 第 9 行,第 6 列
于 2010-04-03T06:12:47.213 回答
6

Perl - 243

(不包括换行符,都是可选的)

大部分去高尔夫球的代码可以在这里找到。

$/="";@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 中读取板子(嘿,popshift! 短两个字符)

这个想法是我们将板读成一个字符串(丢弃字母之间的额外空格),并记下它的宽度(通过计算字符直到第一个换行符)。然后我们进行一系列正则表达式匹配来查找单词,使用s正则表达式修饰符允许匹配跨越行。给定一个 4 个字母宽的板子(所以每行是 5 个字符,包括换行符)和搜索词“CAR”,我们可以使模式/CAR/匹配向前、/C...A...R/匹配向西南、/C....A....R/向下/C.....A.....R/匹配和向东南匹配. 对于每场比赛,我们记录比赛的开始和结束位置。

然后我们反转搜索词(“CAR”->“RAC”)并再次执行此操作,这让我们可以匹配向左、上、西北和东北方向的词。当然,我们要确保开始/结束位置也交换。为了节省代码,我交换了两次匹配位置;前向词的匹配被交换了两次(所以它们没有交换),而后向词的匹配只交换一次,所以它们会被交换。

最后,只需将匹配偏移量放入板字符串并将它们转换为行/列对,然后按照问题的需要格式化输出。

于 2010-04-03T02:16:01.503 回答
4

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
于 2010-04-02T21:30:12.017 回答
3

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 个字符)。
    示例:使用逗号运算符的任何内容。

  • 使用条件表达式 ( ?:) 而不是ifwhen you can (1 char)。
    示例:而不是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++);

  • 保留 offmain的返回类型(4 个字符)。

  • 留下 offmainreturn声明(9 个字符)。

  • 尽可能使用&and|代替&&and (1 个字符)。示例:而不是,写。这仅在您不依赖和的短路行为时才有效。||
    if(x||y)if(x|y)&&||

  • 内联strlen函数并删除#include<string.h>(11 个字符)。

如果您不关心编译器警告:

  • 不要包含任何标题(许多字符)。
于 2010-04-02T19:05:41.807 回答
3

蟒蛇,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

根据“edit-the-answer-instead-of-commenting-on-how-I-should-fix-this”许可发布。

于 2010-04-02T20:53:08.637 回答
0

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)

示例用法:

猫输入.txt | python test.py CODEGOLF

示例输出:

第 12 行,第 8 列 --> 第 5 行,第 1 列

于 2010-04-02T21:18:18.093 回答