string - Code Golf : Word Search Solver

Question

锁定。这个问题及其答案是locked因为这个问题是题外话，但具有历史意义。它目前不接受新的答案或互动。








注意:这是我的第一个 Code Golf 挑战/问题，所以我可能没有使用下面的正确格式。我不太确定如何标记这个特定问题，这应该是社区维基吗？谢谢!

这个 Code Golf 挑战是关于解决单词搜索!

维基百科定义的单词搜索是:

A word search, word find, word seek, word sleuth or mystery word puzzle is a word game that is letters of a word in a grid, that usually has a rectangular or square shape. The objective of this puzzle is to find and mark all the words hidden inside the box. The words may be horizontally, vertically or diagonally. Often a list of the hidden words is provided, but more challenging puzzles may let the player figure them out. Many word search puzzles have a theme to which all the hidden words are related.

此挑战的搜索词将全部为 带有单词列表的矩形网格 找到提供。字可以写垂直、水平或对角线 .

输入输出

用户输入他们的词搜索，然后输入要在他们的网格中找到的词。这两个输入将传递给您将要编写的函数。如何声明和处理这些对象取决于您。

使用下面描述的策略或您自己的策略，该函数在搜索中找到特定单词并输出其起始坐标(简单的行号和列号)和结束坐标。如果发现该词出现两次，则必须输出两组坐标。如果单词是回文，您可以任意选择一端作为单词的“开始”。

例子

输入:

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