Code Golf:单词搜索解算器

Question

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

---

策略

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

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

Answer 1

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

Answer 2

Perl,226 char

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
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 R A C E 
C A R 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 R A C E C A R R O W G N D 
B C D E J Y E L W X J D F X M 
EOF
row 12, column 8 --> row 5, column 1
row 14, column 3 --> row 14, column 9
row 3, column 12 --> row 9, column 6

Answer 3

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读取板子(嘿,pop比两个字符短shift!)

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

然后我们反转搜索词("CAR" - >"RAC")并再次执行,这使我们可以匹配左,上,西北和东北的单词.当然,我们希望确保交换开始/结束位置.为了保存代码,我将匹配位置交换两次 ; 前向单词的匹配被交换两次(因此它们是未交换的),而后向单词的匹配只交换一次,因此它们将被交换掉.

最后,只需将匹配偏移量放入电路板字符串并将其转换为行/列对,并将输出格式化为问题所需.