如何查找可能的单词列表从信矩阵[惊奇求解] [英] How to find list of possible words from a letter matrix [Boggle Solver]

问题描述

最近我一直在玩游戏，我的iPhone称为争夺。你们有些人可能知道这​​场比赛为惊奇。从本质上讲，游戏开始时你会得到一个字母矩阵像这样：

Lately I have been playing a game on my iPhone called Scramble. Some of you may know this game as Boggle. Essentially, when the game starts you get a matrix of letters like so:

F X I E
A M L O
E W B X
A S T U

本场比赛的目标是找到尽可能多的话，你可以，可以由字母链接在一起而形成的。你可以使用任何字母开头，所有围绕着它的字母都是公平的游戏，然后，一旦你移动到下一个字母，都围绕着这封信的字母都是公平的游戏，除了任何previously的字母。因此在上面的网格，例如，我可以用的话拿出 LOB ， TUX ， SEA ， FAME 等词必须至少为3个字符，并在这场比赛中不超过N×N个字符以上，这将是16但是可以在一些实施方式有所不同。虽然本场比赛是有趣和令人上瘾，我显然不是很擅长，我想通过一个程序，会给我最好的词（时间越长，字越点你）骗一点点。

The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, except for any previously used letters. So in the grid above, for example, I could come up with the words LOB, TUX, SEA, FAME, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations. While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).

我，不幸的是，不是很好的算法或它们的效率等等。我第一次尝试使用字典<一个href="http://www.freebsd.org/cgi/cvsweb.cgi/src/share/dict/web2?rev=1.12;content-type=text%2Fplain">such这一个（〜2.3MB），并做了线性搜索试图匹配组合，带字典条目。这需要的非常的很长一段时间，找到可能的话，因为你只能得到每回合2分钟，那简直是不足够的。

I am, unfortunately, not very good with algorithms or their efficiencies and so forth. My first attempt uses a dictionary such as this one (~2.3MB) and does a linear search trying to match combinations with dictionary entries. This takes a very long time to find the possible words, and since you only get 2 minutes per round, it is simply not adequate.

我很感兴趣，看看是否有Stackoverflowers能拿出更有效的解决方案。我主要是想找使用三巨头诗的解决方案：Python和PHP和Perl，但使用Java或C ++什么也很酷，因为速度是关键

I am interested to see if any Stackoverflowers can come up with more efficient solutions. I am mostly looking for solutions using the Big 3 Ps: Python, PHP, and Perl, although anything with Java or C++ is cool too, since speed is essential.

目前的解决方案

• 亚当罗森菲尔德，Python中，20岁〜
• 约翰Fouhy ，Python和〜3秒
• 肯特弗雷德里克，Perl中，〜1秒
• 大流士培根，Python和〜1秒
• rvarcher ，VB.NET （活动链接）〜1秒
• 保罗Bergantino ，PHP （活动链接） ，〜5秒（约2秒本地）

• Adam Rosenfield, Python, ~20s
• John Fouhy, Python, ~3s
• Kent Fredric, Perl, ~1s
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET (live link), ~1s
• Paolo Bergantino, PHP (live link), ~5s (~2s locally)

BOUNTY

我加入悬赏这个问题，因为我的话说感谢所有谁投在其方案中的人的方式。遗憾的是我只能给接受的答案给你，所以我会衡量谁拥有最快的惊奇求解7天现在奖获得者的奖金。

I am adding a bounty to this question as my way of saying thanks to all the people who pitched in with their programs. Unfortunately I can only give the accepted answer to one of you, so I'll measure who has the fastest boggle solver 7 days from now and award the winner the bounty.

赏金奖励。谢谢大家的参与。

Bounty awarded. Thanks to everyone that participated.

推荐答案

我的回答就像其他人在这里，但我会发布它，因为它看起来有点比其他的Python的解决方案更快，更快的建立字典。 （我检查过这对约翰Fouhy的解决方案。）安装后，解决的时间是下跌中的噪声。

My answer works like the others here, but I'll post it because it looks a bit faster than the other Python solutions, from setting up the dictionary faster. (I checked this against John Fouhy's solution.) After setup, the time to solve is down in the noise.

grid = "fxie amlo ewbx astu".split()
nrows, ncols = len(grid), len(grid[0])

# A dictionary word that could be a solution must use only the grid's
# letters and have length >= 3. (With a case-insensitive match.)
import re
alphabet = ''.join(set(''.join(grid)))
bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match

words = set(word.rstrip('\n') for word in open('words') if bogglable(word))
prefixes = set(word[:i] for word in words
               for i in range(2, len(word)+1))

def solve():
    for y, row in enumerate(grid):
        for x, letter in enumerate(row):
            for result in extending(letter, ((x, y),)):
                yield result

def extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield result

def neighbors((x, y)):
    for nx in range(max(0, x-1), min(x+2, ncols)):
        for ny in range(max(0, y-1), min(y+2, nrows)):
            yield (nx, ny)

使用范例：

# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))

编辑：筛选出的3个字母少言

Filter out words less than 3 letters long.

编辑2：我很好奇，为什么肯特弗雷德里克的Perl的解决方案更快;原来使用的字符集的常规-EX pression匹配代替。做同样在Python约一倍的速度。

Edit 2: I was curious why Kent Fredric's Perl solution was faster; it turns out to use regular-expression matching instead of a set of characters. Doing the same in Python about doubles the speed.

这篇关于如何查找可能的单词列表从信矩阵[惊奇求解]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！