如何从字母矩阵中找到可能的单词列表 [Boggle Solver] [英] How to find list of possible words from a letter matrix [Boggle Solver]

问题描述

最近我一直在我的 iPhone 上玩一款名为 Scramble 的游戏.你们中的一些人可能知道这个游戏是 Boggle.基本上，当游戏开始时，你会得到一个像这样的字母矩阵:

F X I E一个 M L OE W B XA S T U

游戏的目标是找到尽可能多的单词，这些单词可以通过将字母链接在一起形成.你可以从任何一个字母开始，它周围的所有字母都是公平游戏，然后一旦你移动到下一个字母，那个字母周围的所有字母都是公平游戏，除了任何以前使用过的字母.例如，在上面的网格中，我可以想出词LOB、TUX、SEA、FAME 等.单词必须至少为 3 个字符，且不超过 NxN 个字符，在此游戏中为 16 个字符，但在某些实现中可能会有所不同.虽然这个游戏既有趣又容易上瘾，但我显然不太擅长它，我想通过制作一个程序来给我最好的单词(单词越长，得分越多)来作弊.

_{(来源:boggled.org)}

不幸的是，我不太擅长算法或它们的效率等等.我的第一次尝试使用字典 例如这个 (~2.3MB) 并进行线性搜索，尝试将组合与字典条目相匹配.这需要很长时间才能找到可能的单词，而且由于每轮只有 2 分钟，这根本不够.

我有兴趣看看是否有任何 Stackoverflowers 可以提出更有效的解决方案.我主要是在寻找使用三大 Ps 的解决方案:Python、PHP 和 Perl，尽管使用 Java 或 C++ 的任何东西也很酷，因为速度至关重要.

当前解决方案:

• Adam Rosenfield，Python，20 多岁
• John Fouhy，Python，~3s
• Kent Fredric，Perl，~1s
• Darius Bacon，Python，~1s
• rvarcher，VB.NET，~1s
• Paolo Bergantino，PHP (实时链接)，~5 秒(本地~2 秒))

解决方案

我的答案和这里的其他答案一样，但我会发布它，因为它看起来比其他 Python 解决方案快一点，从更快地设置字典.(我根据 John Fouhy 的解决方案检查了这一点.)设置后，解决的时间减少了.

grid = "fxie amlo ewbx astu".split()nrows, ncols = len(grid), len(grid[0])# 可以作为解决方案的字典单词必须仅使用网格的# 字母并且长度大于等于 3.(不区分大小写匹配.)进口重新字母 = ''.join(set(''.join(grid)))bogglable = re.compile('[' + 字母 + ']{3,}$', re.I).matchwords = set(word.rstrip('
') for word in open('words') if bogglable(word))prefixes = set(word[:i] for word in words对于范围内的 i(2, len(word)+1))定义解决():对于 y，枚举(网格)中的行:对于 x，枚举中的字母(行):对于扩展(字母，((x，y)，))的结果:产出结果定义扩展(前缀，路径):如果单词前缀:产量(前缀，路径)对于(nx，ny)在邻居(路径[-1])中:如果 (nx, ny) 不在路径中:前缀 1 = 前缀 + 网格 [ny][nx]如果前缀为 prefix1:对于扩展(前缀1，路径+((nx，ny)，))的结果:产出结果定义邻居((x，y)):对于范围内的 nx(max(0, x-1), min(x+2, ncols)):对于范围内的 ny(max(0, y-1), min(y+2, nrows)):产量 (nx, ny)

示例用法:

# 打印最大长度的单词及其路径:打印 max(solve(), key=lambda (word, path): len(word))

过滤掉少于 3 个字母的单词.

编辑 2: 我很好奇为什么 Kent Fredric 的 Perl 解决方案更快；结果证明使用正则表达式匹配而不是一组字符.在 Python 中做同样的事情，速度会提高一倍.

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

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

_{(source: boggled.org)}

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.

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.

CURRENT SOLUTIONS:

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

解决方案

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('
') 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)

Sample usage:

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

Edit: Filter out words less than 3 letters long.

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.

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