最近我一直在我的iPhone上玩一款名为Scramble的游戏.有些人可能认为这个游戏是Boggle.基本上,当游戏开始时你得到一个像这样的字母矩阵:
F X I E
A M L O
E W B X
A S T U
游戏的目标是尽可能多地找到可以通过将字母链接在一起形成的单词.你可以从任何字母开始,并且它周围的所有字母都是公平的游戏,然后一旦你继续下一个字母,围绕那个字母的所有字母都是合理的游戏,除了以前使用的任何字母.因此在上面的网格,例如,我能想出的话LOB,TUX,SEA,FAME,等词必须至少有3个字符,并且不超过N×N个字符以上,这将是本场比赛16,但可以在一些实现改变.虽然这个游戏很有趣且令人上瘾,但我显然不是很擅长它而且我想通过制作一个可以给我最好的单词的程序来作弊(单词越长,得分就越多).
样本博格http://www.boggled.org/sample.gif
遗憾的是,我不熟悉算法或效率等等.我第一次尝试使用字典,如这一个(〜2.3MB),并确实试图以配合字典条目组合线性搜索.这需要很长时间才能找到可能的单词,而且由于每轮只有2分钟,所以根本就不够.
我很想知道Stackoverflowers是否可以提供更有效的解决方案.我主要是在寻找使用Big 3 Ps的解决方案:Python,PHP和Perl,尽管Java或C++也很酷,因为速度至关重要.
当前的解决方案:
BOUNTY:
我正在为这个问题增加一笔赏金,作为我向所有投入他们计划的人表示感谢的方式.不幸的是,我只能向你们中的一个人提供接受的答案,所以我将测量7天后谁拥有最快的晃动解算器,并奖励获胜者赏金.
赏金奖励.感谢所有参与的人.
我正在编写一个类似于Boggle的游戏,游戏玩家应该在随机字母组成的大字符串中找到单词.
例如,有五个数组,其中包含像这样的字符串.五行,每行六个字母:
AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO
因此,游戏的用户应该使用可用的字母制作单词,并考虑以下限制和规则:
我想知道如何通过所有字符串来制作单词.要知道我将使用带有单词的txt文件的单词.
我不知道如何设计能够执行搜索的算法,特别是考虑找到单词和尊重限制所需的不稳定运动.
我已经实现了UX,掷骰子和填充棋盘游戏的逻辑,以及六个字母骰子的所有逻辑.
但这部分并不容易,我想看看你对这个有趣挑战的建议.
我在这个游戏中使用Python,因为我使用的语言代码和我最喜欢的语言.但是算法本身的解释或建议也应该很好,与语言无关.
我有兴趣识别Boggle板上的字母,可能使用openCV.字母都是相同的字体但可以旋转,因此使用标准文本识别库有点问题.另外,M和W有下划线来区分它们,Q实际上是Qu.我相当自信我可以隔离图像中的单独字母,我只是想知道如何做识别部分.
解决boggle的函数的最佳时间复杂度O(n)是多少,其中boggle board是n？
我觉得n^2因为每个角色都要看2(n-1)其他角色.采访者认为,这不是n^2一个O(1)字典查找.
我正在尝试解决反向Boggle问题.简单地说,给定一个单词列表,得出一个4x4字母的字母,其中列表中的多个单词可以在相邻字母的序列中找到(字母正交和对角相邻).
我不想拿一块已知的板子来解决它.这是一个简单的TRIE问题,并且已经在人们的CS项目中进行了讨论/解决.
单词列表示例:
margays, jaguars, cougars, tomcats, margay, jaguar, cougar, pumas, puma, toms
解:
ATJY
CTSA
OMGS
PUAR
这个问题很难(对我来说).我到目前为止的算法:
显然,有实现细节.首先从最长的单词开始.忽略作为其他单词的子串的单词.
我可以在大约0.4秒内为7个字符的单词生成所有68k可能的板.然后,当我添加一个额外的7个字符板时,我需要比较68k x 68k板x 7比较.解决时间变得冰冷.
必须有一个更好的方法来做到这一点!!!!
一些代码:
BOARD_SIDE_LENGTH = 4
class Board:
def __init__(self):
pass
def setup(self, word, start_position):
self.word = word
self.indexSequence = [start_position,]
self.letters_left_over = word[1:]
self.overlay = []
# set up template for overlay. When we compare boards, we will add to this if the board fits
for i in range(BOARD_SIDE_LENGTH*BOARD_SIDE_LENGTH): …我参加了Coursera上的算法第二部分课程，其中一项作业是解决Boggle游戏的方法：http : //coursera.cs.princeton.edu/algs4/assignments/boggle.html
荣誉代码要求我不要公开发布解决方案，因此这里是基本算法的伪代码。
visit:
word <- board[i][j]
start <- dictionary.match(word, start)
if start is not null
visited[i][j] <- true
word <- prefix + word
if word is longer than min required length
words <- words + word
for (x, y) ? adj(i, j)
if not visited(x, y)
visit (x, y)
visited[i][j] <- false
该字典是使用Trie实现的。
上面的代码有效，我通过了分配，但是随后我遇到了这篇博客文章，该文章声称使用动态编程可以实现更快的解决方案：
事实证明，我们可以使用一种巧妙的动态编程技术来快速检查一个单词（在这种情况下是从词典中）是否可以从黑板上构造出来！
这是动态编程思想的核心：
要在板的第[i，j]个位置找到长度为k的单词（结束位置），该单词的第k-1个字母必须位于[i， j]。
基本情况是k = 1。
在板的第[i，j]个单元格的第[i，j]个单元格中会找到一个长度为1的字母（结束位置），该单词中唯一的字母与板的第[i，j]个位置的字母匹配。
一旦用基本情况填充了动态编程表，就可以在长度为k，k> 1的任何单词的基础上进行构建。
不幸的是，作者在解释方面做得很差，我无法遵循他的解决方案。我想不过，希望这里有人可以向我解释。
PS：
这个问题不是重复的，因为那个人不使用DP。请检查那些重复快乐的手指。
我已表现出足够的努力，没有要求任何人做我的作业。我已经有了自己的解决方案。我感兴趣的是学习一种更好的解决问题的方法（如果存在）。
谢谢！
我正在为我在python中编写的boggle-clone创建一个联网服务器,它接受用户,解决板,并对玩家输入进行评分.我正在使用的字典文件是1.8MB(ENABLE2K字典),我需要它可以用于几个游戏求解器类.现在,我有它,以便每个类逐行遍历文件并生成一个哈希表(关联数组),但我实例化的解算器类越多,它占用的内存就越多.
我想要做的是导入一次字典文件,并在需要时将其传递给每个求解器实例.但是最好的方法是什么？我应该在全局空间中导入字典,然后在解算器类中以globals()['字典']的形式访问它吗？或者我应该导入字典然后将其作为参数传递给类构造函数？其中一个比另一个好吗？有第三种选择吗？