最近我一直在iPhone上玩一款名为《Scramble》的游戏。有些人可能知道这个游戏叫拼字游戏。从本质上讲，当游戏开始时，你会得到一个字母矩阵:
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).
(来源:boggled.org)
不幸的是，我不太擅长算法或它们的效率等等。我的第一次尝试使用一个像这样的字典(约2.3MB)，并进行线性搜索，试图匹配字典条目的组合。这需要花费很长时间来找到可能的单词，因为你每轮只有2分钟的时间，这是不够的。
我很有兴趣看看是否有任何Stackoverflowers可以提出更有效的解决方案。我主要是在寻找使用三大p的解决方案:Python、PHP和Perl，尽管任何使用Java或c++的东西也很酷，因为速度是至关重要的。
目前的解决方案:
Adam Rosenfield, Python， ~20岁
John Fouhy, Python， ~3秒
Kent Fredric, Perl， ~1s
Darius Bacon, Python， ~1s
rvarcher, VB。净,~ 1 s
Paolo Bergantino, PHP(实时链接)，~5s(本地~2s)
package ProblemSolving;
import java.util.HashSet;
import java.util.Set;
/**
* Given a 2-dimensional array of characters and a
* dictionary in which a word can be searched in O(1) time.
* Need to print all the words from array which are present
* in dictionary. Word can be formed in any direction but
* has to end at any edge of array.
* (Need not worry much about the dictionary)
*/
public class DictionaryWord {
private static char[][] matrix = new char[][]{
{'a', 'f', 'h', 'u', 'n'},
{'e', 't', 'a', 'i', 'r'},
{'a', 'e', 'g', 'g', 'o'},
{'t', 'r', 'm', 'l', 'p'}
};
private static int dim_x = matrix.length;
private static int dim_y = matrix[matrix.length -1].length;
private static Set<String> wordSet = new HashSet<String>();
public static void main(String[] args) {
//dictionary
wordSet.add("after");
wordSet.add("hate");
wordSet.add("hair");
wordSet.add("air");
wordSet.add("eat");
wordSet.add("tea");
for (int x = 0; x < dim_x; x++) {
for (int y = 0; y < dim_y; y++) {
checkAndPrint(matrix[x][y] + "");
int[][] visitedMap = new int[dim_x][dim_y];
visitedMap[x][y] = 1;
recursion(matrix[x][y] + "", visitedMap, x, y);
}
}
}
private static void checkAndPrint(String word) {
if (wordSet.contains(word)) {
System.out.println(word);
}
}
private static void recursion(String word, int[][] visitedMap, int x, int y) {
for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
if (visitedMap[i][j] == 1) {
continue;
} else {
int[][] newVisitedMap = new int[dim_x][dim_y];
for (int p = 0; p < dim_x; p++) {
for (int q = 0; q < dim_y; q++) {
newVisitedMap[p][q] = visitedMap[p][q];
}
}
newVisitedMap[i][j] = 1;
checkAndPrint(word + matrix[i][j]);
recursion(word + matrix[i][j], newVisitedMap, i, j);
}
}
}
}
}
我花了3个月的时间致力于解决10个最佳点密集的5x5 Boggle板问题。
这个问题现在已经解决了，并在5个网页上进行了全面披露。有问题请联系我。
该棋盘分析算法使用显式堆栈，通过具有直接子信息的有向无环词图伪递归遍历棋盘方格，并使用时间戳跟踪机制。这很可能是世界上最先进的词汇数据结构。
该方案在四核上每秒评估大约10,000块非常好的电路板。(9500 +分)
父网页:
DeepSearch.c - http://www.pathcom.com/~vadco/deep.html
组件网页:
最佳记分牌- http://www.pathcom.com/~vadco/binary.html
高级词汇结构- http://www.pathcom.com/~vadco/adtdawg.html
板分析算法- http://www.pathcom.com/~vadco/guns.html
并行批处理- http://www.pathcom.com/~vadco/parallel.html
-
只有追求最好的人才会对这本全面的著作感兴趣。
给定一个有N行M列的Boggle板，让我们假设如下:
N*M基本上大于可能单词的数量
N*M基本上大于可能的最长单词
在这些假设下，该解的复杂度为O(N*M)。
我认为比较这个示例板的运行时间在很多方面都没有重点，但是为了完整性，在我的现代MacBook Pro上，这个解决方案在0.2秒内完成。
这个解决方案将为语料库中的每个单词找到所有可能的路径。
#!/usr/bin/env ruby
# Example usage: ./boggle-solver --board "fxie amlo ewbx astu"
autoload :Matrix, 'matrix'
autoload :OptionParser, 'optparse'
DEFAULT_CORPUS_PATH = '/usr/share/dict/words'.freeze
# Functions
def filter_corpus(matrix, corpus, min_word_length)
board_char_counts = Hash.new(0)
matrix.each { |c| board_char_counts[c] += 1 }
max_word_length = matrix.row_count * matrix.column_count
boggleable_regex = /^[#{board_char_counts.keys.reduce(:+)}]{#{min_word_length},#{max_word_length}}$/
corpus.select{ |w| w.match boggleable_regex }.select do |w|
word_char_counts = Hash.new(0)
w.each_char { |c| word_char_counts[c] += 1 }
word_char_counts.all? { |c, count| board_char_counts[c] >= count }
end
end
def neighbors(point, matrix)
i, j = point
([i-1, 0].max .. [i+1, matrix.row_count-1].min).inject([]) do |r, new_i|
([j-1, 0].max .. [j+1, matrix.column_count-1].min).inject(r) do |r, new_j|
neighbor = [new_i, new_j]
neighbor.eql?(point) ? r : r << neighbor
end
end
end
def expand_path(path, word, matrix)
return [path] if path.length == word.length
next_char = word[path.length]
viable_neighbors = neighbors(path[-1], matrix).select do |point|
!path.include?(point) && matrix.element(*point).eql?(next_char)
end
viable_neighbors.inject([]) do |result, point|
result + expand_path(path.dup << point, word, matrix)
end
end
def find_paths(word, matrix)
result = []
matrix.each_with_index do |c, i, j|
result += expand_path([[i, j]], word, matrix) if c.eql?(word[0])
end
result
end
def solve(matrix, corpus, min_word_length: 3)
boggleable_corpus = filter_corpus(matrix, corpus, min_word_length)
boggleable_corpus.inject({}) do |result, w|
paths = find_paths(w, matrix)
result[w] = paths unless paths.empty?
result
end
end
# Script
options = { corpus_path: DEFAULT_CORPUS_PATH }
option_parser = OptionParser.new do |opts|
opts.banner = 'Usage: boggle-solver --board <value> [--corpus <value>]'
opts.on('--board BOARD', String, 'The board (e.g. "fxi aml ewb ast")') do |b|
options[:board] = b
end
opts.on('--corpus CORPUS_PATH', String, 'Corpus file path') do |c|
options[:corpus_path] = c
end
opts.on_tail('-h', '--help', 'Shows usage') do
STDOUT.puts opts
exit
end
end
option_parser.parse!
unless options[:board]
STDERR.puts option_parser
exit false
end
unless File.file? options[:corpus_path]
STDERR.puts "No corpus exists - #{options[:corpus_path]}"
exit false
end
rows = options[:board].downcase.scan(/\S+/).map{ |row| row.scan(/./) }
raw_corpus = File.readlines(options[:corpus_path])
corpus = raw_corpus.map{ |w| w.downcase.rstrip }.uniq.sort
solution = solve(Matrix.rows(rows), corpus)
solution.each_pair do |w, paths|
STDOUT.puts w
paths.each do |path|
STDOUT.puts "\t" + path.map{ |point| point.inspect }.join(', ')
end
end
STDOUT.puts "TOTAL: #{solution.count}"
如何简单的排序和使用字典中的二进制搜索?
在0.35秒内返回整个列表，并可以进一步优化(例如删除含有未使用字母的单词等)。
from bisect import bisect_left
f = open("dict.txt")
D.extend([line.strip() for line in f.readlines()])
D = sorted(D)
def neibs(M,x,y):
n = len(M)
for i in xrange(-1,2):
for j in xrange(-1,2):
if (i == 0 and j == 0) or (x + i < 0 or x + i >= n or y + j < 0 or y + j >= n):
continue
yield (x + i, y + j)
def findWords(M,D,x,y,prefix):
prefix = prefix + M[x][y]
# find word in dict by binary search
found = bisect_left(D,prefix)
# if found then yield
if D[found] == prefix:
yield prefix
# if what we found is not even a prefix then return
# (there is no point in going further)
if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
return
# recourse
for neib in neibs(M,x,y):
for word in findWords(M,D,neib[0], neib[1], prefix):
yield word
def solve(M,D):
# check each starting point
for x in xrange(0,len(M)):
for y in xrange(0,len(M)):
for word in findWords(M,D,x,y,""):
yield word
grid = "fxie amlo ewbx astu".split()
print [x for x in solve(grid,D)]
令人惊讶的是，没有人尝试使用PHP版本。
这是John Fouhy的Python解决方案的PHP版本。
虽然我从其他人的答案中得到了一些建议，但这主要是抄袭约翰的。
$boggle = "fxie
amlo
ewbx
astu";
$alphabet = str_split(str_replace(array("\n", " ", "\r"), "", strtolower($boggle)));
$rows = array_map('trim', explode("\n", $boggle));
$dictionary = file("C:/dict.txt");
$prefixes = array(''=>'');
$words = array();
$regex = '/[' . implode('', $alphabet) . ']{3,}$/S';
foreach($dictionary as $k=>$value) {
$value = trim(strtolower($value));
$length = strlen($value);
if(preg_match($regex, $value)) {
for($x = 0; $x < $length; $x++) {
$letter = substr($value, 0, $x+1);
if($letter == $value) {
$words[$value] = 1;
} else {
$prefixes[$letter] = 1;
}
}
}
}
$graph = array();
$chardict = array();
$positions = array();
$c = count($rows);
for($i = 0; $i < $c; $i++) {
$l = strlen($rows[$i]);
for($j = 0; $j < $l; $j++) {
$chardict[$i.','.$j] = $rows[$i][$j];
$children = array();
$pos = array(-1,0,1);
foreach($pos as $z) {
$xCoord = $z + $i;
if($xCoord < 0 || $xCoord >= count($rows)) {
continue;
}
$len = strlen($rows[0]);
foreach($pos as $w) {
$yCoord = $j + $w;
if(($yCoord < 0 || $yCoord >= $len) || ($z == 0 && $w == 0)) {
continue;
}
$children[] = array($xCoord, $yCoord);
}
}
$graph['None'][] = array($i, $j);
$graph[$i.','.$j] = $children;
}
}
function to_word($chardict, $prefix) {
$word = array();
foreach($prefix as $v) {
$word[] = $chardict[$v[0].','.$v[1]];
}
return implode("", $word);
}
function find_words($graph, $chardict, $position, $prefix, $prefixes, &$results, $words) {
$word = to_word($chardict, $prefix);
if(!isset($prefixes[$word])) return false;
if(isset($words[$word])) {
$results[] = $word;
}
foreach($graph[$position] as $child) {
if(!in_array($child, $prefix)) {
$newprefix = $prefix;
$newprefix[] = $child;
find_words($graph, $chardict, $child[0].','.$child[1], $newprefix, $prefixes, $results, $words);
}
}
}
$solution = array();
find_words($graph, $chardict, 'None', array(), $prefixes, $solution);
print_r($solution);
如果你想尝试的话，这里有一个实时链接。虽然在我的本地机器上需要大约2秒，但在我的web服务器上需要大约5秒。无论哪种情况，它都不是很快。尽管如此，它还是很可怕，所以我可以想象时间可以大大缩短。任何关于如何实现这一目标的建议都将不胜感激。PHP缺少元组，这使得坐标处理起来很奇怪，而且我无法理解到底发生了什么，这对我一点帮助都没有。
编辑:一些修复使它在本地少于1秒。
