Als ich die Problemstellung sah, dachte ich sofort an "Trie". Aber da mehrere andere Poster diesen Ansatz verwendet haben, habe ich nach einem anderen Ansatz gesucht, nur um anders zu sein. Leider schneidet der Trie-Ansatz besser ab. Ich habe Kents Perl-Lösung auf meinem Rechner ausgeführt und es dauerte 0.31 Sekunden laufen, nachdem ich es an die Verwendung meiner Wörterbuchdatei angepasst habe. Meine eigene Perl-Implementierung erforderte 0.54 Sekunden zu laufen.
Das war mein Ansatz:
-
Erstellen Sie einen Übergangs-Hash, um die gesetzlichen Übergänge zu modellieren.
-
Iterieren Sie durch alle 16^3 möglichen Kombinationen von drei Buchstaben.
- Schließen Sie in der Schleife illegale Übergänge und wiederholte Besuche der gleichen Platz. Bilde alle zulässigen 3-Buchstaben-Sequenzen und speichere sie in einem Hash.
-
Gehen Sie dann in einer Schleife durch alle Wörter im Wörterbuch.
- Zu lange oder zu kurze Wörter ausschließen
- Schieben Sie ein 3-Buchstaben-Fenster über jedes Wort und prüfen Sie, ob es zu den 3-Buchstaben-Kombinationen aus Schritt 2 gehört. Schließen Sie Wörter aus, die dies nicht tun. Dadurch werden die meisten Nichtübereinstimmungen eliminiert.
- Falls immer noch nicht eliminiert, verwenden Sie einen rekursiven Algorithmus, um zu sehen, ob das Wort durch Wege durch das Rätsel gebildet werden kann. (Dieser Teil ist langsam, wird aber nur selten aufgerufen).
-
Drucken Sie die gefundenen Wörter aus.
Ich habe 3-Buchstaben- und 4-Buchstaben-Sequenzen ausprobiert, aber 4-Buchstaben-Sequenzen verlangsamten das Programm.
In meinem Code verwende ich /usr/share/dict/words für mein Wörterbuch. Diese Datei ist standardmäßig auf MAC OS X und vielen Unix-Systemen vorhanden. Sie können auch eine andere Datei verwenden, wenn Sie wollen. Um ein anderes Rätsel zu knacken, ändern Sie einfach die Variable @puzzle. Dies lässt sich leicht für größere Matrizen anpassen. Sie müssten nur den %transitions-Hash und den %legalTransitions-Hash ändern.
Die Stärke dieser Lösung ist, dass der Code kurz und die Datenstrukturen einfach sind.
Hier ist der Perl-Code (der zu viele globale Variablen verwendet, ich weiß):
#!/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.
}
1 Stimmen
Eine einfache Lösung ist die Klasse BoggleFinder aima.cs.berkeley.edu/python/search.html
0 Stimmen
Das macht doch keinen Spaß, oder? :)
18 Stimmen
Bitte übersetzen Sie dies beibehalten die gleichen HTML-Tags, wenn diese vorhanden sind von en nach de: Featureanfrage MEHR RÄTSEL
6 Stimmen
In Bezug auf die Zeitpunkte: In meiner Lösung wird praktisch die gesamte Zeit damit verbracht, den Trie aufzubauen. Sobald der Trie erstellt ist, kann er viele Male wiederverwendet werden. Wenn nur ein Rätsel gelöst wird, wäre es effizienter, eine einfachere Datenstruktur zu verwenden (wie eine Menge aller Wörter und aller Präfixe).
3 Stimmen
Auch Adam hat ein größeres Wörterbuch, wie durch die Anzahl der längeren Wörter in seiner Lösung belegt wird. Sie sollten alle basierend auf einem gemeinsamen Wörterbuch getestet werden.
0 Stimmen
@Reich: Ich führe sie alle auf meinem Computer mit meinem eigenen Wörterbuch aus.
2 Stimmen
Ich nehme an, dass niemand viel Boggle spielt? "Qu" ist ein "Buchstabe" und ich bin mir nicht sicher, wie viele der Lösungen dieses kleine Detail beachtet haben. Es sieht so aus, als ob einige von ihnen es ermöglichen würden, das "u" unabhängig zu verwenden, unter anderem Probleme.
2 Stimmen
Ich hatte kürzlich diese Frage bei einem Vorstellungsgespräch und bin nett in den Details steckengeblieben. Ich behandelte es als ein Graphenproblem, was in Ordnung ist, aber die Lösungen hier verwenden viel weniger Speicher. Ich code jetzt meine eigene Lösung. Gut gemacht an alle, die beigetragen haben!
0 Stimmen
Diese Frage scheint nicht zum Thema zu gehören, da es um Rätsellösungen geht. Es wäre passender auf codegolf.stackexchange.com
0 Stimmen
@Blazemonger Die Frage ist nach dem effizientesten Algorithmus zur Lösung eines Boggle gestellt, nicht nach dem kürzesten, und es handelt sich nicht um ein Rätsel im Codegolf-Stil. Soweit ich weiß, waren algorithmusbezogene Fragen fair für StackOverflow. Dies ist nicht off-topic, und ich denke, die Community hat ziemlich laut darüber gesprochen.
2 Stimmen
Sie sagen, dass Sie einen allgemeinen Algorithmus möchten, aber "Sie suchen hauptsächlich" nach konkretem Code in Python, PHP oder Perl. Sie haben keine eigene Arbeit geleistet, was heutzutage als wesentlich für SO-Fragen angesehen wird. Kommentare kennzeichnen dies eindeutig als "Rätsel" und nicht als eng definiertes Problem mit einer einzigen Lösung. Alles zusammen genommen könnte es als Codegolf geeignet sein, wie es geschrieben ist, aber wenn Sie diese Frage heute eingereicht hätten, würde sie sicherlich nicht als angemessen für SO angesehen. Meiner Meinung nach setzt es ein schlechtes Beispiel für Neulinge, was hier als "gute Frage" angesehen wird, wenn Sie sie offen lassen.
1 Stimmen
@Blazemonger 1. Die Bitte um bestimmte Sprachen ist für die Frage nach einem Algorithmus irrelevant. 2. Ich habe meine versuchte Lösung beschrieben und meine eigene gepostet. 3. Es ist definitiv eng und ausreichend definiert. 4. Es würde sicherlich offen bleiben, wenn es heute gepostet würde. 5. Wenn Neuankömmlinge Fragen stellen würden, die nur halb so gut sind wie diese, wären wir in guter Verfassung. Kurz gesagt, ich widerspreche respektvoll praktisch allem, was du gesagt hast.
0 Stimmen
@PaoloBergantino Tatsächlich sind offene Fragen, die zum analytischen Denken anregen, viel besser als die "Mach meinen Job, während ich Mittagessen gehe" Art von sogenannten Anfängerfragen, die heutzutage auf SO so verbreitet sind.
0 Stimmen
Ich erwarte, dass diese Frage gesperrt wird, da der Wert der Antworten darin liegt, aber ich stimme zu, dass sie nicht zum Thema gehört. Ich werde es erneut versuchen zu schließen. cc @Blazemonger.