Code Golf:单词搜索求解器 [英] Code Golf: Word Search Solver

问题描述

注意:这是我第一次参加Code Golf挑战赛/问题，所以我可能使用的格式不正确.我不太确定如何标记这个特定问题，这应该是社区Wiki吗?谢谢！

此Code Golf挑战是关于解决单词搜索的问题！

This Code Golf challenge is about solving word searches!

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

A word search, as defined by Wikipedia, is:

单词搜索，单词搜索，单词搜索， 单词侦探或神秘单词拼图是 一个单词游戏的单词游戏 在网格中，通常有一个 矩形或正方形.这 这个难题的目的是要找到 并标记隐藏在里面的所有单词 盒子.这句话可能是 水平，垂直或 对角地.通常是隐藏的清单 提供了文字，但更多 具有挑战性的难题可能会让玩家 弄清楚他们.多词搜索 拼图有一个主题，所有 隐藏的单词是相关的.

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.

用于搜索该挑战的单词将全部为带有单词列表的矩形网格，以查找提供的单词.这些单词可以垂直，水平或对角线书写.

The word searches for this challenge will all be rectangular grids with a list of words to find provided. The words can be written vertically, horizontally, or diagonally.

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

The user inputs their word search and then inputs a word to be found in their grid. These two inputs are passed to the function that you will be writing. It is up to you how you want to declare and handle these objects.

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

Using a strategy described below or one of your own, the function finds the specific word in the search and outputs its starting coordinates (simply row number and column number) and ending coordinates. If you find two occurrences of the word, you must output both sets of coordinates. If the word is a palindrome, you may arbitrarily choose one end to be the "start" of the word.

输入:

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

---

策略

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

---

Strategies

Here are a few strategies you might consider using. It is completely up to you to decide what strategy you want to use; it doesn't have to be in this list.

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

推荐答案

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个字符，无需做任何额外的调整即可接受网格

This version is 196 chars and accepts the grid without doing any extra tweaking

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

这篇关于Code Golf:单词搜索求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！