当我看到问题陈述时，我想到了“Trie”。但看到其他一些海报使用了这种方法，我寻找另一种不同的方法。可惜的是，Trie方法表现更好。我在我的机器上运行了Kent的Perl解决方案，在调整它以使用我的字典文件后，它花了0.31秒运行。我自己的perl实现需要0.54秒才能运行。
这就是我的方法:
Create a transition hash to model the legal transitions.
Iterate through all 16^3 possible three letter combinations.
In the loop, exclude illegal transitions and repeat visits to the
same square. Form all the legal 3-letter sequences and store them in a hash.
Then loop through all words in the dictionary.
Exclude words that are too long or short
Slide a 3-letter window across each word and see if it is among the 3-letter combos from step 2. Exclude words that fail. This eliminates most non-matches.
If still not eliminated, use a recursive algorithm to see if the word can be formed by making paths through the puzzle. (This part is slow, but called infrequently.)
Print out the words I found.
I tried 3-letter and 4-letter sequences, but 4-letter sequences slowed the program down.
在我的代码中，我使用/usr/share/dict/words作为我的字典。它是MAC OS X和许多Unix系统的标准配置。如果你愿意，你可以使用另一个文件。要破解不同的谜题，只需更改变量@puzzle。这将很容易适应更大的矩阵。你只需要改变%transitions哈希值和%legalTransitions哈希值。
这种解决方案的优点是代码短，数据结构简单。
下面是Perl代码(我知道它使用了太多的全局变量):
#!/usr/bin/perl
use Time::HiRes qw{ time };
sub readFile($);
sub findAllPrefixes($);
sub isWordTraceable($);
sub findWordsInPuzzle(@);
my $startTime = time;
# Puzzle to solve
my @puzzle = (
F, X, I, E,
A, M, L, O,
E, W, B, X,
A, S, T, U
);
my $minimumWordLength = 3;
my $maximumPrefixLength = 3; # I tried four and it slowed down.
# Slurp the word list.
my $wordlistFile = "/usr/share/dict/words";
my @words = split(/\n/, uc(readFile($wordlistFile)));
print "Words loaded from word list: " . scalar @words . "\n";
print "Word file load time: " . (time - $startTime) . "\n";
my $postLoad = time;
# Define the legal transitions from one letter position to another.
# Positions are numbered 0-15.
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
my %transitions = (
-1 => [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
0 => [1,4,5],
1 => [0,2,4,5,6],
2 => [1,3,5,6,7],
3 => [2,6,7],
4 => [0,1,5,8,9],
5 => [0,1,2,4,6,8,9,10],
6 => [1,2,3,5,7,9,10,11],
7 => [2,3,6,10,11],
8 => [4,5,9,12,13],
9 => [4,5,6,8,10,12,13,14],
10 => [5,6,7,9,11,13,14,15],
11 => [6,7,10,14,15],
12 => [8,9,13],
13 => [8,9,10,12,14],
14 => [9,10,11,13,15],
15 => [10,11,14]
);
# Convert the transition matrix into a hash for easy access.
my %legalTransitions = ();
foreach my $start (keys %transitions) {
my $legalRef = $transitions{$start};
foreach my $stop (@$legalRef) {
my $index = ($start + 1) * (scalar @puzzle) + ($stop + 1);
$legalTransitions{$index} = 1;
}
}
my %prefixesInPuzzle = findAllPrefixes($maximumPrefixLength);
print "Find prefixes time: " . (time - $postLoad) . "\n";
my $postPrefix = time;
my @wordsFoundInPuzzle = findWordsInPuzzle(@words);
print "Find words in puzzle time: " . (time - $postPrefix) . "\n";
print "Unique prefixes found: " . (scalar keys %prefixesInPuzzle) . "\n";
print "Words found (" . (scalar @wordsFoundInPuzzle) . ") :\n " . join("\n ", @wordsFoundInPuzzle) . "\n";
print "Total Elapsed time: " . (time - $startTime) . "\n";
###########################################
sub readFile($) {
my ($filename) = @_;
my $contents;
if (-e $filename) {
# This is magic: it opens and reads a file into a scalar in one line of code.
# See http://www.perl.com/pub/a/2003/11/21/slurp.html
$contents = do { local( @ARGV, $/ ) = $filename ; <> } ;
}
else {
$contents = '';
}
return $contents;
}
# Is it legal to move from the first position to the second? They must be adjacent.
sub isLegalTransition($$) {
my ($pos1,$pos2) = @_;
my $index = ($pos1 + 1) * (scalar @puzzle) + ($pos2 + 1);
return $legalTransitions{$index};
}
# Find all prefixes where $minimumWordLength <= length <= $maxPrefixLength
#
# $maxPrefixLength ... Maximum length of prefix we will store. Three gives best performance.
sub findAllPrefixes($) {
my ($maxPrefixLength) = @_;
my %prefixes = ();
my $puzzleSize = scalar @puzzle;
# Every possible N-letter combination of the letters in the puzzle
# can be represented as an integer, though many of those combinations
# involve illegal transitions, duplicated letters, etc.
# Iterate through all those possibilities and eliminate the illegal ones.
my $maxIndex = $puzzleSize ** $maxPrefixLength;
for (my $i = 0; $i < $maxIndex; $i++) {
my @path;
my $remainder = $i;
my $prevPosition = -1;
my $prefix = '';
my %usedPositions = ();
for (my $prefixLength = 1; $prefixLength <= $maxPrefixLength; $prefixLength++) {
my $position = $remainder % $puzzleSize;
# Is this a valid step?
# a. Is the transition legal (to an adjacent square)?
if (! isLegalTransition($prevPosition, $position)) {
last;
}
# b. Have we repeated a square?
if ($usedPositions{$position}) {
last;
}
else {
$usedPositions{$position} = 1;
}
# Record this prefix if length >= $minimumWordLength.
$prefix .= $puzzle[$position];
if ($prefixLength >= $minimumWordLength) {
$prefixes{$prefix} = 1;
}
push @path, $position;
$remainder -= $position;
$remainder /= $puzzleSize;
$prevPosition = $position;
} # end inner for
} # end outer for
return %prefixes;
}
# Loop through all words in dictionary, looking for ones that are in the puzzle.
sub findWordsInPuzzle(@) {
my @allWords = @_;
my @wordsFound = ();
my $puzzleSize = scalar @puzzle;
WORD: foreach my $word (@allWords) {
my $wordLength = length($word);
if ($wordLength > $puzzleSize || $wordLength < $minimumWordLength) {
# Reject word as too short or too long.
}
elsif ($wordLength <= $maximumPrefixLength ) {
# Word should be in the prefix hash.
if ($prefixesInPuzzle{$word}) {
push @wordsFound, $word;
}
}
else {
# Scan through the word using a window of length $maximumPrefixLength, looking for any strings not in our prefix list.
# If any are found that are not in the list, this word is not possible.
# If no non-matches are found, we have more work to do.
my $limit = $wordLength - $maximumPrefixLength + 1;
for (my $startIndex = 0; $startIndex < $limit; $startIndex ++) {
if (! $prefixesInPuzzle{substr($word, $startIndex, $maximumPrefixLength)}) {
next WORD;
}
}
if (isWordTraceable($word)) {
# Additional test necessary: see if we can form this word by following legal transitions
push @wordsFound, $word;
}
}
}
return @wordsFound;
}
# Is it possible to trace out the word using only legal transitions?
sub isWordTraceable($) {
my $word = shift;
return traverse([split(//, $word)], [-1]); # Start at special square -1, which may transition to any square in the puzzle.
}
# Recursively look for a path through the puzzle that matches the word.
sub traverse($$) {
my ($lettersRef, $pathRef) = @_;
my $index = scalar @$pathRef - 1;
my $position = $pathRef->[$index];
my $letter = $lettersRef->[$index];
my $branchesRef = $transitions{$position};
BRANCH: foreach my $branch (@$branchesRef) {
if ($puzzle[$branch] eq $letter) {
# Have we used this position yet?
foreach my $usedBranch (@$pathRef) {
if ($usedBranch == $branch) {
next BRANCH;
}
}
if (scalar @$lettersRef == $index + 1) {
return 1; # End of word and success.
}
push @$pathRef, $branch;
if (traverse($lettersRef, $pathRef)) {
return 1; # Recursive success.
}
else {
pop @$pathRef;
}
}
}
return 0; # No path found. Failed.
}
