Wie Liste der möglichen Wörter aus einem Brief Matrix finden [Boggle Solver]
https://stackoverflow.com/questions/746082
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
In letzter Zeit ein Spiel auf meinem iPhone zu spielen genannt Scramble Ich habe. Einige von Ihnen mögen dieses Spiel als Boggle wissen. Im Wesentlichen, wenn das Spiel beginnt man eine Matrix aus Buchstaben erhält wie folgt:
F X I E
A M L O
E W B X
A S T U
Das Ziel des Spiels ist es, so viele Worte zu finden, wie Sie, dass durch die Verkettung zusammen Buchstaben gebildet werden können. Sie können mit jedem Buchstaben beginnen, und alle Buchstaben, die es fair Spiel umgeben, und dann, wenn Sie auf den nächsten Buchstaben weitergehen, werden alle Buchstaben, die diesen Brief sind fair Spiel umgeben, Ausnahme für alle bisher verwendeten Buchstaben . So in dem Gitter oben, zum Beispiel könnte ich kommen mit den Worten LOB, TUX, SEA, FAME usw. Die Worte müssen mindestens 3 Zeichen lang, und nicht mehr als NxN Zeichen sein, die 16 in diesem Spiel sein würde, aber kann unterscheiden sich in einigen Implementierungen. Während dieses Spiel Spaß und süchtig ist, bin ich es anscheinend nicht sehr gut, und ich wollte ein wenig betrügen, indem ein Programm machen, das mir die bestmöglichen Worte geben würde (je länger das Wort, desto mehr Punkte erhalten Sie.)
(Quelle: boggled.org )
Ich bin leider nicht sehr gut mit Algorithmen oder ihrer Effizienz und so weiter. Mein erster Versuch verwendet ein Wörterbuch wie dieser (~ 2,3MB) und stellt eine lineare Suche versucht, Kombinationen mit Wörterbucheinträgen entsprechen. Dies nimmt eine sehr lange Zeit, um die möglichen Worte zu finden, und da Sie nur 2 Minuten pro Runde bekommen, es ist einfach nicht ausreichend.
Ich bin interessiert, um zu sehen, ob irgendwelche Stackoverflowers mit effizienteren Lösungen kommen können. Ich bin vor allem für Lösungen suchen, um den Big 3 Ps: ein. Python, PHP und Perl, obwohl alles mit Java oder C ++ zu kühl ist, da Geschwindigkeit wesentlich ist,
AKTUELLE SOLUTIONS :
- Adam Rosenfield, Python, ~ 20s
- John Fouhy, Python, ~ 3s
- Kent Fredric, Perl, ~ 1 s
- Darius Bacon, Python, ~ 1 s
- rvarcher, VB.NET (live link) , ~ 1 s
- Paolo Bergantino, PHP (live link) , ~ 5 s (~ 2s lokal )
Lösung
Meine Antwort funktioniert wie die anderen hier, aber ich werde es schreiben, weil es ein bisschen schneller als die anderen Python-Lösungen sieht, von der Einstellung der Wörterbuch schneller auf. (Ich habe dies gegen John Fouhy Lösung.) Nach der Einrichtung zu lösen ist die Zeit, in dem Lärm nach unten.
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)
Verwendungsbeispiel:
# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))
Edit:. filtern Wörter mit weniger als 3 Buchstaben lang
Edit 2: Ich war neugierig, warum war Kent Fredric Perl-Lösung schneller; es stellt sich heraus, statt einer Reihe von Zeichen passenden regulären Ausdruck zu verwenden. Dadurch könnte die gleiche in Python über die Geschwindigkeit verdoppelt.
Andere Tipps
Die schnellste Lösung Sie gehen wahrscheinlich zu bekommen beinhalten Ihr Wörterbuch in einem trie . Dann erstellen eine Warteschlange von Tripletts ( x , y , s ), wobei jedes Element in der Warteschlange entspricht einem Präfix s ein Wort, das in dem Gitter geschrieben werden kann, an der Stelle endet ( x , y ). Initialisieren der Warteschlange mit N x N Elemente (wobei N die Größe des Gitters ist), ein Element für jedes Quadrat in dem Gitter. Dann geht der Algorithmus wie folgt:
While the queue is not empty:
Dequeue a triple (x, y, s)
For each square (x', y') with letter c adjacent to (x, y):
If s+c is a word, output s+c
If s+c is a prefix of a word, insert (x', y', s+c) into the queue
Wenn Sie Ihre Wörterbuch in einem Trie, wenn die Prüfung s + c ist ein Wort oder ein Präfix eines Wortes in konstanter Zeit durchgeführt werden (vorausgesetzt, Sie auch hält einige zusätzliche Metadaten in jeder Warteschlange Datum, wie beispielsweise einen Zeiger auf den aktuellen Knoten in der Trie), so dass die Laufzeit dieses Algorithmus O (Anzahl der Worte ist, die geschrieben werden können).
[Bearbeiten] Hier ist eine Implementierung in Python, dass ich codiert oben nur:
#!/usr/bin/python
class TrieNode:
def __init__(self, parent, value):
self.parent = parent
self.children = [None] * 26
self.isWord = False
if parent is not None:
parent.children[ord(value) - 97] = self
def MakeTrie(dictfile):
dict = open(dictfile)
root = TrieNode(None, '')
for word in dict:
curNode = root
for letter in word.lower():
if 97 <= ord(letter) < 123:
nextNode = curNode.children[ord(letter) - 97]
if nextNode is None:
nextNode = TrieNode(curNode, letter)
curNode = nextNode
curNode.isWord = True
return root
def BoggleWords(grid, dict):
rows = len(grid)
cols = len(grid[0])
queue = []
words = []
for y in range(cols):
for x in range(rows):
c = grid[y][x]
node = dict.children[ord(c) - 97]
if node is not None:
queue.append((x, y, c, node))
while queue:
x, y, s, node = queue[0]
del queue[0]
for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)):
x2, y2 = x + dx, y + dy
if 0 <= x2 < cols and 0 <= y2 < rows:
s2 = s + grid[y2][x2]
node2 = node.children[ord(grid[y2][x2]) - 97]
if node2 is not None:
if node2.isWord:
words.append(s2)
queue.append((x2, y2, s2, node2))
return words
Beispiel Nutzung:
d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))
Ausgabe:
[ 'fa', 'xi', 'also', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', ‚mich ‘, 'lo', 'li', 'oe', 'Ochse', 'em', 'ea', 'ea', 'es', 'wa', 'wir', 'wa', 'bo', 'bu', 'wie', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'FAE', 'imi', ‚eli ‘, 'Ulme', 'ELB', 'ami', 'AMA', 'ame', 'aes', 'Ahle', 'AWA', 'awe', 'AWA', 'Mix', 'mim', 'mil', 'MAM', 'max', 'Mae', 'Schlund', 'mew', 'mem', 'MES', 'LOB', 'LOX', 'Leu', 'LEO', ‚lie ‘, 'lim', 'Öl', 'OLM', 'Mutterschaf', 'eme', 'Wachs', 'waf', 'WAE', 'WAW', 'WEM', 'wea', 'wea', 'war', 'waw', 'wae', 'bob', 'blo', 'bub', 'aber', 'ast', 'ase', 'asa', 'Ahle', 'awa', ‚Ehrfurcht ‘, 'awa', 'aes', 'swa', 'swa', 'nähen', 'Meer', 'Meer', 'sah', 'Smoking', 'Wanne', 'tut', 'twa', 'TWA', 'TST', 'utu', 'fama', 'Ruhm', 'IXIL', 'imam', 'amli', 'amil', 'Ambo', 'axil', 'Achse', ‚mimi ‘, 'mima', 'MIME', 'Milo', 'Meile', 'mewl', 'mese', 'mesa', 'lolo', 'lobo', 'lima', 'lime', 'Glied', 'lile', 'oime', 'oleo', 'olio', 'Oboe', 'Obolus', 'emim', 'emil', 'Osten', 'Leichtigkeit', 'wame', 'Wawa', ‚wawa ' 'WEAM', 'Westen', 'Wese', 'wast',' wa se‘, 'wawa', 'wawa', 'Kochen', 'bolo', 'bole', 'bobo', 'blob', 'Bleo', 'Beule', 'asem', 'Stub', 'Stut' , 'schwimmt', 'halb', 's'eme', 'Naht', 'Sax', 'Sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', ' ilima‘, 'amble', 'axile', 'awest', 'mamie', 'mambo', 'Maxime', 'MEASE', 'mesem', 'Limax', 'Kalk', 'Schwebezustand', 'limbu' , 'obole', 'Emesa', 'eMBox', 'awest', 'swami', 'famble', 'mimble', 'maxima', 'Embolo', 'embole', 'Wamble', 'Semese', ' semble‘, 'Sawbwa', 'Sawbwa']
Weitere Informationen: Dieses Programm funktioniert nicht ausgegeben 1-Buchstaben-Wörter oder Filter für Wort überhaupt Länge. Das ist einfach hinzuzufügen, aber nicht wirklich relevant für das Problem. Es gibt auch ein paar Worte mehrmals, wenn sie können auf vielfältige Weise geschrieben werden. Wenn ein gegebenes Wort kann auf vielen verschiedenen Arten geschrieben werden (ungünstigster Fall: jeder Buchstabe im Netz gleich ist (zB ‚A‘) und ein Wort wie ‚aaaaaaaaaa‘ ist in Ihrem Wörterbuch), dann wird die Laufzeit bekommt schrecklich exponentielle . Ausfiltern Duplikate und Sortierung ist trivial zurückzuführen, nachdem der Algorithmus beendet ist.
Für ein Wörterbuch Speedup, gibt es eine allgemeine Transformation / Prozess Sie stark tun können, um die Wörterbuch-Vergleiche vor der Zeit zu reduzieren.
Da die oben Gitter nur 16 Zeichen enthalten, vervielfältigen einige von ihnen, können Sie erheblich die Gesamtzahl der Schlüssel in Ihrem Wörterbuch reduzieren, indem sie einfach Einträge Ausfiltern der unerreichbar Zeichen lang sein.
Ich dachte, dies war die offensichtliche Optimierung aber da niemand tat es ich bin es zu erwähnen.
Es reduzierte mich aus einem Wörterbuch von 200.000 Tasten nur 2.000 Tasten einfach während der Eingabe weiter. Dies zumindest reduziert Speicher-Overhead, und das ist sicher irgendwo auf eine Geschwindigkeitserhöhung zur Karte als Speicher nicht unendlich schnell ist.
Perl Implementierung
Meine Implementierung ist ein bisschen kopflastig, weil ich wichtig den genauen Pfad jeder extrahierten String, nicht nur die Gültigkeit darin wissen, darauf gelegt.
Ich habe auch ein paar Adaptionen dort das wäre theoretisch ein Gitter mit Löchern darin erlauben, zu funktionieren, und Gitter mit unterschiedlich großen Linien (vorausgesetzt, Sie die Eingabe richtig machen und es reiht sich irgendwie).
Der frühe Filter ist bei weitem die meisten signifikante Engpass in meiner Anwendung, wie bereits vermutet, kommentieren, dass Zeile, um 7.5s von 1,5s bläht.
Bei der Ausführung erscheint es alle die einzelnen Ziffern denken auf ihre eigenen gültigen Worte sind, aber ich bin mir ziemlich sicher, das ist darauf zurückzuführen, wie die Wörterbuch-Datei funktioniert.
Es ist ein bisschen aufgebläht, aber zumindest ich wieder verwenden Baum :: Trie von cpan
Ein Teil davon wurde von den bestehenden Implementierungen teilweise inspiriert, es einige ich schon im Sinn hatte.
Konstruktive Kritik und Möglichkeiten, es willkommen verbessert werden könnte (/ me bemerkt er nie gesucht CPAN für einen boggle Solver , aber das war mehr Spaß zu trainieren)
nach neuen Kriterien aktualisiert
#!/usr/bin/perl
use strict;
use warnings;
{
# this package manages a given path through the grid.
# Its an array of matrix-nodes in-order with
# Convenience functions for pretty-printing the paths
# and for extending paths as new paths.
# Usage:
# my $p = Prefix->new(path=>[ $startnode ]);
# my $c = $p->child( $extensionNode );
# print $c->current_word ;
package Prefix;
use Moose;
has path => (
isa => 'ArrayRef[MatrixNode]',
is => 'rw',
default => sub { [] },
);
has current_word => (
isa => 'Str',
is => 'rw',
lazy_build => 1,
);
# Create a clone of this object
# with a longer path
# $o->child( $successive-node-on-graph );
sub child {
my $self = shift;
my $newNode = shift;
my $f = Prefix->new();
# Have to do this manually or other recorded paths get modified
push @{ $f->{path} }, @{ $self->{path} }, $newNode;
return $f;
}
# Traverses $o->path left-to-right to get the string it represents.
sub _build_current_word {
my $self = shift;
return join q{}, map { $_->{value} } @{ $self->{path} };
}
# Returns the rightmost node on this path
sub tail {
my $self = shift;
return $self->{path}->[-1];
}
# pretty-format $o->path
sub pp_path {
my $self = shift;
my @path =
map { '[' . $_->{x_position} . ',' . $_->{y_position} . ']' }
@{ $self->{path} };
return "[" . join( ",", @path ) . "]";
}
# pretty-format $o
sub pp {
my $self = shift;
return $self->current_word . ' => ' . $self->pp_path;
}
__PACKAGE__->meta->make_immutable;
}
{
# Basic package for tracking node data
# without having to look on the grid.
# I could have just used an array or a hash, but that got ugly.
# Once the matrix is up and running it doesn't really care so much about rows/columns,
# Its just a sea of points and each point has adjacent points.
# Relative positioning is only really useful to map it back to userspace
package MatrixNode;
use Moose;
has x_position => ( isa => 'Int', is => 'rw', required => 1 );
has y_position => ( isa => 'Int', is => 'rw', required => 1 );
has value => ( isa => 'Str', is => 'rw', required => 1 );
has siblings => (
isa => 'ArrayRef[MatrixNode]',
is => 'rw',
default => sub { [] }
);
# Its not implicitly uni-directional joins. It would be more effient in therory
# to make the link go both ways at the same time, but thats too hard to program around.
# and besides, this isn't slow enough to bother caring about.
sub add_sibling {
my $self = shift;
my $sibling = shift;
push @{ $self->siblings }, $sibling;
}
# Convenience method to derive a path starting at this node
sub to_path {
my $self = shift;
return Prefix->new( path => [$self] );
}
__PACKAGE__->meta->make_immutable;
}
{
package Matrix;
use Moose;
has rows => (
isa => 'ArrayRef',
is => 'rw',
default => sub { [] },
);
has regex => (
isa => 'Regexp',
is => 'rw',
lazy_build => 1,
);
has cells => (
isa => 'ArrayRef',
is => 'rw',
lazy_build => 1,
);
sub add_row {
my $self = shift;
push @{ $self->rows }, [@_];
}
# Most of these functions from here down are just builder functions,
# or utilities to help build things.
# Some just broken out to make it easier for me to process.
# All thats really useful is add_row
# The rest will generally be computed, stored, and ready to go
# from ->cells by the time either ->cells or ->regex are called.
# traverse all cells and make a regex that covers them.
sub _build_regex {
my $self = shift;
my $chars = q{};
for my $cell ( @{ $self->cells } ) {
$chars .= $cell->value();
}
$chars = "[^$chars]";
return qr/$chars/i;
}
# convert a plain cell ( ie: [x][y] = 0 )
# to an intelligent cell ie: [x][y] = object( x, y )
# we only really keep them in this format temporarily
# so we can go through and tie in neighbouring information.
# after the neigbouring is done, the grid should be considered inoperative.
sub _convert {
my $self = shift;
my $x = shift;
my $y = shift;
my $v = $self->_read( $x, $y );
my $n = MatrixNode->new(
x_position => $x,
y_position => $y,
value => $v,
);
$self->_write( $x, $y, $n );
return $n;
}
# go through the rows/collums presently available and freeze them into objects.
sub _build_cells {
my $self = shift;
my @out = ();
my @rows = @{ $self->{rows} };
for my $x ( 0 .. $#rows ) {
next unless defined $self->{rows}->[$x];
my @col = @{ $self->{rows}->[$x] };
for my $y ( 0 .. $#col ) {
next unless defined $self->{rows}->[$x]->[$y];
push @out, $self->_convert( $x, $y );
}
}
for my $c (@out) {
for my $n ( $self->_neighbours( $c->x_position, $c->y_position ) ) {
$c->add_sibling( $self->{rows}->[ $n->[0] ]->[ $n->[1] ] );
}
}
return \@out;
}
# given x,y , return array of points that refer to valid neighbours.
sub _neighbours {
my $self = shift;
my $x = shift;
my $y = shift;
my @out = ();
for my $sx ( -1, 0, 1 ) {
next if $sx + $x < 0;
next if not defined $self->{rows}->[ $sx + $x ];
for my $sy ( -1, 0, 1 ) {
next if $sx == 0 && $sy == 0;
next if $sy + $y < 0;
next if not defined $self->{rows}->[ $sx + $x ]->[ $sy + $y ];
push @out, [ $sx + $x, $sy + $y ];
}
}
return @out;
}
sub _has_row {
my $self = shift;
my $x = shift;
return defined $self->{rows}->[$x];
}
sub _has_cell {
my $self = shift;
my $x = shift;
my $y = shift;
return defined $self->{rows}->[$x]->[$y];
}
sub _read {
my $self = shift;
my $x = shift;
my $y = shift;
return $self->{rows}->[$x]->[$y];
}
sub _write {
my $self = shift;
my $x = shift;
my $y = shift;
my $v = shift;
$self->{rows}->[$x]->[$y] = $v;
return $v;
}
__PACKAGE__->meta->make_immutable;
}
use Tree::Trie;
sub readDict {
my $fn = shift;
my $re = shift;
my $d = Tree::Trie->new();
# Dictionary Loading
open my $fh, '<', $fn;
while ( my $line = <$fh> ) {
chomp($line);
# Commenting the next line makes it go from 1.5 seconds to 7.5 seconds. EPIC.
next if $line =~ $re; # Early Filter
$d->add( uc($line) );
}
return $d;
}
sub traverseGraph {
my $d = shift;
my $m = shift;
my $min = shift;
my $max = shift;
my @words = ();
# Inject all grid nodes into the processing queue.
my @queue =
grep { $d->lookup( $_->current_word ) }
map { $_->to_path } @{ $m->cells };
while (@queue) {
my $item = shift @queue;
# put the dictionary into "exact match" mode.
$d->deepsearch('exact');
my $cword = $item->current_word;
my $l = length($cword);
if ( $l >= $min && $d->lookup($cword) ) {
push @words,
$item; # push current path into "words" if it exactly matches.
}
next if $l > $max;
# put the dictionary into "is-a-prefix" mode.
$d->deepsearch('boolean');
siblingloop: foreach my $sibling ( @{ $item->tail->siblings } ) {
foreach my $visited ( @{ $item->{path} } ) {
next siblingloop if $sibling == $visited;
}
# given path y , iterate for all its end points
my $subpath = $item->child($sibling);
# create a new path for each end-point
if ( $d->lookup( $subpath->current_word ) ) {
# if the new path is a prefix, add it to the bottom of the queue.
push @queue, $subpath;
}
}
}
return \@words;
}
sub setup_predetermined {
my $m = shift;
my $gameNo = shift;
if( $gameNo == 0 ){
$m->add_row(qw( F X I E ));
$m->add_row(qw( A M L O ));
$m->add_row(qw( E W B X ));
$m->add_row(qw( A S T U ));
return $m;
}
if( $gameNo == 1 ){
$m->add_row(qw( D G H I ));
$m->add_row(qw( K L P S ));
$m->add_row(qw( Y E U T ));
$m->add_row(qw( E O R N ));
return $m;
}
}
sub setup_random {
my $m = shift;
my $seed = shift;
srand $seed;
my @letters = 'A' .. 'Z' ;
for( 1 .. 4 ){
my @r = ();
for( 1 .. 4 ){
push @r , $letters[int(rand(25))];
}
$m->add_row( @r );
}
}
# Here is where the real work starts.
my $m = Matrix->new();
setup_predetermined( $m, 0 );
#setup_random( $m, 5 );
my $d = readDict( 'dict.txt', $m->regex );
my $c = scalar @{ $m->cells }; # get the max, as per spec
print join ",\n", map { $_->pp } @{
traverseGraph( $d, $m, 3, $c ) ;
};
Bogen / Ausführung Info zum Vergleich:
model name : Intel(R) Core(TM)2 Duo CPU T9300 @ 2.50GHz
cache size : 6144 KB
Memory usage summary: heap total: 77057577, heap peak: 11446200, stack peak: 26448
total calls total memory failed calls
malloc| 947212 68763684 0
realloc| 11191 1045641 0 (nomove:9063, dec:4731, free:0)
calloc| 121001 7248252 0
free| 973159 65854762
Histogram for block sizes:
0-15 392633 36% ==================================================
16-31 43530 4% =====
32-47 50048 4% ======
48-63 70701 6% =========
64-79 18831 1% ==
80-95 19271 1% ==
96-111 238398 22% ==============================
112-127 3007 <1%
128-143 236727 21% ==============================
Mehr Gemurmel auf dieser Regex Optimierung
Die Regex Optimierung ich benutze, ist nutzlos für Wörterbücher Mehr lösen und für Multi lösen Sie ein komplettes Wörterbuch wollen, kein Pre-getrimmten ein.
Allerdings, was gesagt, für Einmal löst, es ist wirklich schnell. (Perl regex ist in C! :))
Hier einige unterschiedlichen Code Ergänzungen:
sub readDict_nofilter {
my $fn = shift;
my $re = shift;
my $d = Tree::Trie->new();
# Dictionary Loading
open my $fh, '<', $fn;
while ( my $line = <$fh> ) {
chomp($line);
$d->add( uc($line) );
}
return $d;
}
sub benchmark_io {
use Benchmark qw( cmpthese :hireswallclock );
# generate a random 16 character string
# to simulate there being an input grid.
my $regexen = sub {
my @letters = 'A' .. 'Z' ;
my @lo = ();
for( 1..16 ){
push @lo , $_ ;
}
my $c = join '', @lo;
$c = "[^$c]";
return qr/$c/i;
};
cmpthese( 200 , {
filtered => sub {
readDict('dict.txt', $regexen->() );
},
unfiltered => sub {
readDict_nofilter('dict.txt');
}
});
}
s/iter unfiltered filtered unfiltered 8.16 -- -94% filtered 0.464 1658% --
ps: 8,16 * 200 = 27 Minuten.
Sie könnten das Problem aufgeteilt in zwei Teile:
- Eine Art Suchalgorithmus, die möglich Strings im Raster aufzuzählen werden.
- Eine Art und Weise der Prüfung, ob eine Zeichenfolge ein gültiges Wort ist.
Im Idealfall (2) soll auch eine Lösung für die Prüfung, ob eine Zeichenfolge ein Präfix eines gültigen Wortes ist - dies ermöglicht es Ihnen, Ihre Suche zu beschneiden und einen ganzen Haufen von Zeit sparen
.Adam Rosenfield der Trie ist eine Lösung (2). Es ist elegant und wahrscheinlich das, was Ihre Algorithmen Spezialist würde es vorziehen, aber mit modernen Sprachen und modernen Computern können wir ein bisschen fauler sein. Auch, wie Kent schon sagt, können wir unsere Größe des Wörterbuchs durch Verwerfen Worte reduzieren, die Buchstaben nicht im Netz haben. Hier einige Python:
def make_lookups(grid, fn='dict.txt'):
# Make set of valid characters.
chars = set()
for word in grid:
chars.update(word)
words = set(x.strip() for x in open(fn) if set(x.strip()) <= chars)
prefixes = set()
for w in words:
for i in range(len(w)+1):
prefixes.add(w[:i])
return words, prefixes
Wow; Konstantzeit-Präfix-Tests. Es dauert ein paar Sekunden, um das Wörterbuch Sie verknüpft zu laden, aber nur ein paar :-) (beachten Sie, dass words <= prefixes)
Nun, für einen Teil (1), ich bin geneigt in Bezug auf den Graphen zu denken. Also werde ich ein Wörterbuch erstellen, die etwa wie folgt aussieht:
graph = { (x, y):set([(x0,y0), (x1,y1), (x2,y2)]), }
d. graph[(x, y)] ist der Satz von Koordinaten, die Sie von der Position (x, y) erreichen können. Ich werde auch eine Dummy-Knoten None beimischen, das alles verbinden wird.
Gebäude ist es ein bisschen ungeschickt, weil es 8 mögliche Positionen ist, und Sie haben die Überprüfung der Grenzen zu tun. Hier einig entsprechend-plump Python-Code:
def make_graph(grid):
root = None
graph = { root:set() }
chardict = { root:'' }
for i, row in enumerate(grid):
for j, char in enumerate(row):
chardict[(i, j)] = char
node = (i, j)
children = set()
graph[node] = children
graph[root].add(node)
add_children(node, children, grid)
return graph, chardict
def add_children(node, children, grid):
x0, y0 = node
for i in [-1,0,1]:
x = x0 + i
if not (0 <= x < len(grid)):
continue
for j in [-1,0,1]:
y = y0 + j
if not (0 <= y < len(grid[0])) or (i == j == 0):
continue
children.add((x,y))
Dieser Code baut auch ein Wörterbuch Mapping (x,y) auf das entsprechende Zeichen auf. Auf diese Weise können Sie mir eine Liste von Positionen in ein Wort drehen:
def to_word(chardict, pos_list):
return ''.join(chardict[x] for x in pos_list)
Schließlich haben wir tun, um eine Tiefensuche. Die grundsätzliche Vorgehensweise ist:
- Die Suche kommt zu einem bestimmten Knoten.
- Überprüfen Sie, ob der Weg so weit Teil eines Wortes sein könnte. Wenn nicht, erforschen nicht diesen Zweig weiter.
- Überprüfen Sie, ob der Weg so weit ist ein Wort. Wenn ja, in der Liste der Ergebnisse hinzuzufügen.
- Alle Kinder nicht Teil des Weges so weit.
Python:
def find_words(graph, chardict, position, prefix, results, words, prefixes):
""" Arguments:
graph :: mapping (x,y) to set of reachable positions
chardict :: mapping (x,y) to character
position :: current position (x,y) -- equals prefix[-1]
prefix :: list of positions in current string
results :: set of words found
words :: set of valid words in the dictionary
prefixes :: set of valid words or prefixes thereof
"""
word = to_word(chardict, prefix)
if word not in prefixes:
return
if word in words:
results.add(word)
for child in graph[position]:
if child not in prefix:
find_words(graph, chardict, child, prefix+[child], results, words, prefixes)
Führen Sie den Code wie:
grid = ['fxie', 'amlo', 'ewbx', 'astu']
g, c = make_graph(grid)
w, p = make_lookups(grid)
res = set()
find_words(g, c, None, [], res, w, p)
und inspizieren res die Antworten zu sehen. Hier ist eine Liste von Wörtern für Ihr Beispiel, sortiert nach Größe gefunden:
['a', 'b', 'e', 'f', 'i', 'l', 'm', 'o', 's', 't',
'u', 'w', 'x', 'ae', 'am', 'as', 'aw', 'ax', 'bo',
'bu', 'ea', 'el', 'em', 'es', 'fa', 'ie', 'io', 'li',
'lo', 'ma', 'me', 'mi', 'oe', 'ox', 'sa', 'se', 'st',
'tu', 'ut', 'wa', 'we', 'xi', 'aes', 'ame', 'ami',
'ase', 'ast', 'awa', 'awe', 'awl', 'blo', 'but', 'elb',
'elm', 'fae', 'fam', 'lei', 'lie', 'lim', 'lob', 'lox',
'mae', 'maw', 'mew', 'mil', 'mix', 'oil', 'olm', 'saw',
'sea', 'sew', 'swa', 'tub', 'tux', 'twa', 'wae', 'was',
'wax', 'wem', 'ambo', 'amil', 'amli', 'asem', 'axil',
'axle', 'bleo', 'boil', 'bole', 'east', 'fame', 'limb',
'lime', 'mesa', 'mewl', 'mile', 'milo', 'oime', 'sawt',
'seam', 'seax', 'semi', 'stub', 'swam', 'twae', 'twas',
'wame', 'wase', 'wast', 'weam', 'west', 'amble', 'awest',
'axile', 'embox', 'limbo', 'limes', 'swami', 'embole',
'famble', 'semble', 'wamble']
Der Code nimmt (buchstäblich) ein paar Sekunden, um das Wörterbuch zu laden, aber der Rest ist sofort auf meiner Maschine.
Mein Versuch in Java. Es dauert etwa 2 s-Datei zu lesen und Trie zu bauen, und um 50 ms um das Rätsel zu lösen. Ich benutzen das Wörterbuch in der Frage verknüpft (es hat ein paar Worte, die ich nicht in Englisch gibt es weiß, wie fae, ima)
0 [main] INFO gineer.bogglesolver.util.Util - Reading the dictionary
2234 [main] INFO gineer.bogglesolver.util.Util - Finish reading the dictionary
2234 [main] INFO gineer.bogglesolver.Solver - Found: FAM
2234 [main] INFO gineer.bogglesolver.Solver - Found: FAME
2234 [main] INFO gineer.bogglesolver.Solver - Found: FAMBLE
2234 [main] INFO gineer.bogglesolver.Solver - Found: FAE
2234 [main] INFO gineer.bogglesolver.Solver - Found: IMA
2234 [main] INFO gineer.bogglesolver.Solver - Found: ELI
2234 [main] INFO gineer.bogglesolver.Solver - Found: ELM
2234 [main] INFO gineer.bogglesolver.Solver - Found: ELB
2234 [main] INFO gineer.bogglesolver.Solver - Found: AXIL
2234 [main] INFO gineer.bogglesolver.Solver - Found: AXILE
2234 [main] INFO gineer.bogglesolver.Solver - Found: AXLE
2234 [main] INFO gineer.bogglesolver.Solver - Found: AMI
2234 [main] INFO gineer.bogglesolver.Solver - Found: AMIL
2234 [main] INFO gineer.bogglesolver.Solver - Found: AMLI
2234 [main] INFO gineer.bogglesolver.Solver - Found: AME
2234 [main] INFO gineer.bogglesolver.Solver - Found: AMBLE
2234 [main] INFO gineer.bogglesolver.Solver - Found: AMBO
2250 [main] INFO gineer.bogglesolver.Solver - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: MIX
2250 [main] INFO gineer.bogglesolver.Solver - Found: MIL
2250 [main] INFO gineer.bogglesolver.Solver - Found: MILE
2250 [main] INFO gineer.bogglesolver.Solver - Found: MILO
2250 [main] INFO gineer.bogglesolver.Solver - Found: MAX
2250 [main] INFO gineer.bogglesolver.Solver - Found: MAE
2250 [main] INFO gineer.bogglesolver.Solver - Found: MAW
2250 [main] INFO gineer.bogglesolver.Solver - Found: MEW
2250 [main] INFO gineer.bogglesolver.Solver - Found: MEWL
2250 [main] INFO gineer.bogglesolver.Solver - Found: MES
2250 [main] INFO gineer.bogglesolver.Solver - Found: MESA
2250 [main] INFO gineer.bogglesolver.Solver - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIE
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIM
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMA
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMAX
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIME
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMES
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMB
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMBO
2250 [main] INFO gineer.bogglesolver.Solver - Found: LIMBU
2250 [main] INFO gineer.bogglesolver.Solver - Found: LEI
2250 [main] INFO gineer.bogglesolver.Solver - Found: LEO
2250 [main] INFO gineer.bogglesolver.Solver - Found: LOB
2250 [main] INFO gineer.bogglesolver.Solver - Found: LOX
2250 [main] INFO gineer.bogglesolver.Solver - Found: OIME
2250 [main] INFO gineer.bogglesolver.Solver - Found: OIL
2250 [main] INFO gineer.bogglesolver.Solver - Found: OLE
2250 [main] INFO gineer.bogglesolver.Solver - Found: OLM
2250 [main] INFO gineer.bogglesolver.Solver - Found: EMIL
2250 [main] INFO gineer.bogglesolver.Solver - Found: EMBOLE
2250 [main] INFO gineer.bogglesolver.Solver - Found: EMBOX
2250 [main] INFO gineer.bogglesolver.Solver - Found: EAST
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAF
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAX
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAME
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAMBLE
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver - Found: WEAM
2250 [main] INFO gineer.bogglesolver.Solver - Found: WEM
2250 [main] INFO gineer.bogglesolver.Solver - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver - Found: WES
2250 [main] INFO gineer.bogglesolver.Solver - Found: WEST
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAS
2250 [main] INFO gineer.bogglesolver.Solver - Found: WASE
2250 [main] INFO gineer.bogglesolver.Solver - Found: WAST
2250 [main] INFO gineer.bogglesolver.Solver - Found: BLEO
2250 [main] INFO gineer.bogglesolver.Solver - Found: BLO
2250 [main] INFO gineer.bogglesolver.Solver - Found: BOIL
2250 [main] INFO gineer.bogglesolver.Solver - Found: BOLE
2250 [main] INFO gineer.bogglesolver.Solver - Found: BUT
2250 [main] INFO gineer.bogglesolver.Solver - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver - Found: ASE
2250 [main] INFO gineer.bogglesolver.Solver - Found: ASEM
2250 [main] INFO gineer.bogglesolver.Solver - Found: AST
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEAX
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEAM
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEMI
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEMBLE
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEW
2250 [main] INFO gineer.bogglesolver.Solver - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: SWAM
2250 [main] INFO gineer.bogglesolver.Solver - Found: SWAMI
2250 [main] INFO gineer.bogglesolver.Solver - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: SAW
2250 [main] INFO gineer.bogglesolver.Solver - Found: SAWT
2250 [main] INFO gineer.bogglesolver.Solver - Found: STU
2250 [main] INFO gineer.bogglesolver.Solver - Found: STUB
2250 [main] INFO gineer.bogglesolver.Solver - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver - Found: TWAS
2250 [main] INFO gineer.bogglesolver.Solver - Found: TUB
2250 [main] INFO gineer.bogglesolver.Solver - Found: TUX
Der Quellcode besteht aus 6 Klassen. Ich werde sie unten posten (wenn dies auf Stackoverflow nicht die richtige Praxis ist, erklären Sie mir bitte).
gineer.bogglesolver.Main
package gineer.bogglesolver;
import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;
public class Main
{
private final static Logger logger = Logger.getLogger(Main.class);
public static void main(String[] args)
{
BasicConfigurator.configure();
Solver solver = new Solver(4,
"FXIE" +
"AMLO" +
"EWBX" +
"ASTU");
solver.solve();
}
}
gineer.bogglesolver.Solver
package gineer.bogglesolver;
import gineer.bogglesolver.trie.Trie;
import gineer.bogglesolver.util.Constants;
import gineer.bogglesolver.util.Util;
import org.apache.log4j.Logger;
public class Solver
{
private char[] puzzle;
private int maxSize;
private boolean[] used;
private StringBuilder stringSoFar;
private boolean[][] matrix;
private Trie trie;
private final static Logger logger = Logger.getLogger(Solver.class);
public Solver(int size, String puzzle)
{
trie = Util.getTrie(size);
matrix = Util.connectivityMatrix(size);
maxSize = size * size;
stringSoFar = new StringBuilder(maxSize);
used = new boolean[maxSize];
if (puzzle.length() == maxSize)
{
this.puzzle = puzzle.toCharArray();
}
else
{
logger.error("The puzzle size does not match the size specified: " + puzzle.length());
this.puzzle = puzzle.substring(0, maxSize).toCharArray();
}
}
public void solve()
{
for (int i = 0; i < maxSize; i++)
{
traverseAt(i);
}
}
private void traverseAt(int origin)
{
stringSoFar.append(puzzle[origin]);
used[origin] = true;
//Check if we have a valid word
if ((stringSoFar.length() >= Constants.MINIMUM_WORD_LENGTH) && (trie.containKey(stringSoFar.toString())))
{
logger.info("Found: " + stringSoFar.toString());
}
//Find where to go next
for (int destination = 0; destination < maxSize; destination++)
{
if (matrix[origin][destination] && !used[destination] && trie.containPrefix(stringSoFar.toString() + puzzle[destination]))
{
traverseAt(destination);
}
}
used[origin] = false;
stringSoFar.deleteCharAt(stringSoFar.length() - 1);
}
}
gineer.bogglesolver.trie.Node
package gineer.bogglesolver.trie;
import gineer.bogglesolver.util.Constants;
class Node
{
Node[] children;
boolean isKey;
public Node()
{
isKey = false;
children = new Node[Constants.NUMBER_LETTERS_IN_ALPHABET];
}
public Node(boolean key)
{
isKey = key;
children = new Node[Constants.NUMBER_LETTERS_IN_ALPHABET];
}
/**
Method to insert a string to Node and its children
@param key the string to insert (the string is assumed to be uppercase)
@return true if the node or one of its children is changed, false otherwise
*/
public boolean insert(String key)
{
//If the key is empty, this node is a key
if (key.length() == 0)
{
if (isKey)
return false;
else
{
isKey = true;
return true;
}
}
else
{//otherwise, insert in one of its child
int childNodePosition = key.charAt(0) - Constants.LETTER_A;
if (children[childNodePosition] == null)
{
children[childNodePosition] = new Node();
children[childNodePosition].insert(key.substring(1));
return true;
}
else
{
return children[childNodePosition].insert(key.substring(1));
}
}
}
/**
Returns whether key is a valid prefix for certain key in this trie.
For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell", "hello" return true
@param prefix the prefix to check
@return true if the prefix is valid, false otherwise
*/
public boolean containPrefix(String prefix)
{
//If the prefix is empty, return true
if (prefix.length() == 0)
{
return true;
}
else
{//otherwise, check in one of its child
int childNodePosition = prefix.charAt(0) - Constants.LETTER_A;
return children[childNodePosition] != null && children[childNodePosition].containPrefix(prefix.substring(1));
}
}
/**
Returns whether key is a valid key in this trie.
For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell" return false
@param key the key to check
@return true if the key is valid, false otherwise
*/
public boolean containKey(String key)
{
//If the prefix is empty, return true
if (key.length() == 0)
{
return isKey;
}
else
{//otherwise, check in one of its child
int childNodePosition = key.charAt(0) - Constants.LETTER_A;
return children[childNodePosition] != null && children[childNodePosition].containKey(key.substring(1));
}
}
public boolean isKey()
{
return isKey;
}
public void setKey(boolean key)
{
isKey = key;
}
}
gineer.bogglesolver.trie.Trie
package gineer.bogglesolver.trie;
public class Trie
{
Node root;
public Trie()
{
this.root = new Node();
}
/**
Method to insert a string to Node and its children
@param key the string to insert (the string is assumed to be uppercase)
@return true if the node or one of its children is changed, false otherwise
*/
public boolean insert(String key)
{
return root.insert(key.toUpperCase());
}
/**
Returns whether key is a valid prefix for certain key in this trie.
For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell", "hello" return true
@param prefix the prefix to check
@return true if the prefix is valid, false otherwise
*/
public boolean containPrefix(String prefix)
{
return root.containPrefix(prefix.toUpperCase());
}
/**
Returns whether key is a valid key in this trie.
For example: if key "hello" is in this trie, tests with all prefixes "hel", "hell" return false
@param key the key to check
@return true if the key is valid, false otherwise
*/
public boolean containKey(String key)
{
return root.containKey(key.toUpperCase());
}
}
gineer.bogglesolver.util.Constants
package gineer.bogglesolver.util;
public class Constants
{
public static final int NUMBER_LETTERS_IN_ALPHABET = 26;
public static final char LETTER_A = 'A';
public static final int MINIMUM_WORD_LENGTH = 3;
public static final int DEFAULT_PUZZLE_SIZE = 4;
}
gineer.bogglesolver.util.Util
package gineer.bogglesolver.util;
import gineer.bogglesolver.trie.Trie;
import org.apache.log4j.Logger;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Util
{
private final static Logger logger = Logger.getLogger(Util.class);
private static Trie trie;
private static int size = Constants.DEFAULT_PUZZLE_SIZE;
/**
Returns the trie built from the dictionary. The size is used to eliminate words that are too long.
@param size the size of puzzle. The maximum lenght of words in the returned trie is (size * size)
@return the trie that can be used for puzzle of that size
*/
public static Trie getTrie(int size)
{
if ((trie != null) && size == Util.size)
return trie;
trie = new Trie();
Util.size = size;
logger.info("Reading the dictionary");
final File file = new File("dictionary.txt");
try
{
Scanner scanner = new Scanner(file);
final int maxSize = size * size;
while (scanner.hasNext())
{
String line = scanner.nextLine().replaceAll("[^\\p{Alpha}]", "");
if (line.length() <= maxSize)
trie.insert(line);
}
}
catch (FileNotFoundException e)
{
logger.error("Cannot open file", e);
}
logger.info("Finish reading the dictionary");
return trie;
}
static boolean[] connectivityRow(int x, int y, int size)
{
boolean[] squares = new boolean[size * size];
for (int offsetX = -1; offsetX <= 1; offsetX++)
{
for (int offsetY = -1; offsetY <= 1; offsetY++)
{
final int calX = x + offsetX;
final int calY = y + offsetY;
if ((calX >= 0) && (calX < size) && (calY >= 0) && (calY < size))
squares[calY * size + calX] = true;
}
}
squares[y * size + x] = false;//the current x, y is false
return squares;
}
/**
Returns the matrix of connectivity between two points. Point i can go to point j iff matrix[i][j] is true
Square (x, y) is equivalent to point (size * y + x). For example, square (1,1) is point 5 in a puzzle of size 4
@param size the size of the puzzle
@return the connectivity matrix
*/
public static boolean[][] connectivityMatrix(int size)
{
boolean[][] matrix = new boolean[size * size][];
for (int x = 0; x < size; x++)
{
for (int y = 0; y < size; y++)
{
matrix[y * size + x] = connectivityRow(x, y, size);
}
}
return matrix;
}
}
Ich glaube, dass Sie wahrscheinlich die meiste Zeit damit verbringen, Worte entsprechen, die möglicherweise nicht durch Ihren Brief Gitter eingebaut werden kann. Also, das erste, was ich tun würde, ist versuchen, diesen Schritt zu beschleunigen, und das sollte man die meisten des Weges dorthin zu gelangen.
Dazu würde ich das Gitter als eine Tabelle von möglichen „bewegt“, dass Sie Index durch den Buchstaben-Übergang Sie suchen auf.
erneut auszudrückenBeginnen Sie mit jedem Buchstaben eine Zahl von Ihrem gesamten Alphabet zuordnen (A = 0, B = 1, C = 2, ... und so weiter).
Lassen Sie sich dieses Beispiel nehmen:
h b c d
e e g h
l l k l
m o f p
Und jetzt, läßt das Alphabet der Buchstaben verwenden wir (in der Regel würden Sie wahrscheinlich das gleiche ganze Alphabet jedes Mal verwendet werden sollen):
b | c | d | e | f | g | h | k | l | m | o | p
---+---+---+---+---+---+---+---+---+---+----+----
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
Sie dann einen 2D-boolean-Array machen, das sagt, ob Sie einen bestimmten Buchstaben Übergang zur Verfügung haben:
| 0 1 2 3 4 5 6 7 8 9 10 11 <- from letter
| b c d e f g h k l m o p
-----+--------------------------------------
0 b | T T T T
1 c | T T T T T
2 d | T T T
3 e | T T T T T T T
4 f | T T T T
5 g | T T T T T T T
6 h | T T T T T T T
7 k | T T T T T T T
8 l | T T T T T T T T T
9 m | T T
10 o | T T T T
11 p | T T T
^
to letter
Jetzt durch Ihre Wortliste gehen und die Worte, um Übergänge konvertieren:
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
Dann überprüfen, ob diese Übergänge erlaubt sind, indem sie sich in der Tabelle suchen:
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
Wenn sie alle erlaubt sind, gibt es eine Chance, dass dieses Wort gefunden werden könnte.
Zum Beispiel das Wort „Helm“ kann auf der 4. Übergang ausgeschlossen werden (m e: Helmet)., Da dieser Eintrag in der Tabelle falsch ist
Und das Wort Hamster kann ausgeschlossen werden, da die erste (h a) Übergang ist nicht erlaubt (nicht einmal in der Tabelle vorhanden ist).
Nun, für die wahrscheinlich nur sehr wenige verbleibende Worte, die Sie nicht beseitigen, versuchen sie tatsächlich im Netz zu finden, wie Sie es jetzt oder wie vorgeschlagen hier in einigen der anderen Antworten zu tun. Dies ist auf Fehlalarme zu vermeiden, die von Sprüngen zwischen identischen Buchstaben im Raster zur Folge hat. Zum Beispiel wird das Wort „Hilfe“ von der Tabelle erlaubt, aber nicht durch das Netz.
Einige weitere Leistungsverbesserung Tipps auf dieser Idee:
-
Statt einen 2D-Array, einen 1D-Array verwenden und einfach den Index des zweiten Briefes selbst berechnen. So kann anstelle einer 12x12-Array wie oben, macht einen 1D-Array mit einer Länge von 144 Wenn Sie dann immer das gleichen Alphabet verwenden (dh ein 26x26 = 676x1-Array für das Standard-Englisch Alphabet), auch wenn nicht alle Buchstaben erscheinen im Raster können Sie die Indizes in dieser 1D-Array, das Sie brauchen, um testen Sie Ihr Wörterbuch Wörter vorab berechnen lassen. Zum Beispiel würden die Indizes für ‚Hallo‘ in dem obigen Beispiel sein
hello (6, 3, 8, 8, 10): 42 (from 6 + 3x12), 99, 104, 128 -> "hello" will be stored as 42, 99, 104, 128 in the dictionary -
Erweitern Sie die Idee zu einer 3D-Tabelle (als 1D-Array ausgedrückt), das heißt alle erlaubten 3-Buchstaben-Kombinationen. So können Sie noch mehr Worte sofort beseitigen und die Anzahl der Array-Lookups für jedes Wort um 1 reduzieren: Für ‚Hallo‘, müssen Sie nur 3-Array-Lookups: hel, ell, llo. Es wird sehr schnell, diese Tabelle zu erstellen, durch die Art und Weise, wie es nur 400 mögliche 3-Buchstaben-Züge im Raster ist.
-
Pre-Berechnung der Indizes der Bewegungen in Ihrem Raster, die Sie benötigen in der Tabelle enthalten. Für das obige Beispiel, müssen Sie die folgenden Einträge auf ‚True‘ gesetzt werden:
(0,0) (0,1) -> here: h, b : [6][0] (0,0) (1,0) -> here: h, e : [6][3] (0,0) (1,1) -> here: h, e : [6][3] (0,1) (0,0) -> here: b, h : [0][6] (0,1) (0,2) -> here: b, c : [0][1] . : - stellen auch Ihr Spiel Gitter in einem 1-D-Array mit 16 Einträgen und haben die Tabelle vorher berechnet in 3. die Indizes in dieses Array enthält.
Ich bin sicher, wenn Sie diesen Ansatz verwenden Sie Ihren Code erhalten können irrsinnig schnell laufen, wenn Sie das Wörterbuch vorberechnet und bereits in den Speicher geladen.
BTW: Ein andere nette Sache zu tun, wenn Sie ein Spiel bauen, ist diese Art von Dingen sofort im Hintergrund laufen zu lassen. Starten Erzeugen und das erste Spiel zu lösen, während der Benutzer noch auf dem Titel-Bildschirm auf Ihrem App und immer mit dem Finger in der richtigen Position suchen, um „Play“ zu drücken. Dann erzeugen und das nächste Spiel lösen, wenn der Benutzer der vorherigen spielt. Das sollte Ihnen viel Zeit zum Ausführen des Codes.
(Ich mag dieses Problem, also werde ich wohl versucht sein, meinen Vorschlag in Java zu implementieren irgendwann in den nächsten Tagen zu sehen, wie es wirklich durchführen würde ... Ich werde den Code hier posten, wenn ich es tue.)
UPDATE:
Ok, ich hatte heute einige Zeit und implementiert diese Idee in Java:
class DictionaryEntry {
public int[] letters;
public int[] triplets;
}
class BoggleSolver {
// Constants
final int ALPHABET_SIZE = 5; // up to 2^5 = 32 letters
final int BOARD_SIZE = 4; // 4x4 board
final int[] moves = {-BOARD_SIZE-1, -BOARD_SIZE, -BOARD_SIZE+1,
-1, +1,
+BOARD_SIZE-1, +BOARD_SIZE, +BOARD_SIZE+1};
// Technically constant (calculated here for flexibility, but should be fixed)
DictionaryEntry[] dictionary; // Processed word list
int maxWordLength = 0;
int[] boardTripletIndices; // List of all 3-letter moves in board coordinates
DictionaryEntry[] buildDictionary(String fileName) throws IOException {
BufferedReader fileReader = new BufferedReader(new FileReader(fileName));
String word = fileReader.readLine();
ArrayList<DictionaryEntry> result = new ArrayList<DictionaryEntry>();
while (word!=null) {
if (word.length()>=3) {
word = word.toUpperCase();
if (word.length()>maxWordLength) maxWordLength = word.length();
DictionaryEntry entry = new DictionaryEntry();
entry.letters = new int[word.length() ];
entry.triplets = new int[word.length()-2];
int i=0;
for (char letter: word.toCharArray()) {
entry.letters[i] = (byte) letter - 65; // Convert ASCII to 0..25
if (i>=2)
entry.triplets[i-2] = (((entry.letters[i-2] << ALPHABET_SIZE) +
entry.letters[i-1]) << ALPHABET_SIZE) +
entry.letters[i];
i++;
}
result.add(entry);
}
word = fileReader.readLine();
}
return result.toArray(new DictionaryEntry[result.size()]);
}
boolean isWrap(int a, int b) { // Checks if move a->b wraps board edge (like 3->4)
return Math.abs(a%BOARD_SIZE-b%BOARD_SIZE)>1;
}
int[] buildTripletIndices() {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int a=0; a<BOARD_SIZE*BOARD_SIZE; a++)
for (int bm: moves) {
int b=a+bm;
if ((b>=0) && (b<board.length) && !isWrap(a, b))
for (int cm: moves) {
int c=b+cm;
if ((c>=0) && (c<board.length) && (c!=a) && !isWrap(b, c)) {
result.add(a);
result.add(b);
result.add(c);
}
}
}
int[] result2 = new int[result.size()];
int i=0;
for (Integer r: result) result2[i++] = r;
return result2;
}
// Variables that depend on the actual game layout
int[] board = new int[BOARD_SIZE*BOARD_SIZE]; // Letters in board
boolean[] possibleTriplets = new boolean[1 << (ALPHABET_SIZE*3)];
DictionaryEntry[] candidateWords;
int candidateCount;
int[] usedBoardPositions;
DictionaryEntry[] foundWords;
int foundCount;
void initializeBoard(String[] letters) {
for (int row=0; row<BOARD_SIZE; row++)
for (int col=0; col<BOARD_SIZE; col++)
board[row*BOARD_SIZE + col] = (byte) letters[row].charAt(col) - 65;
}
void setPossibleTriplets() {
Arrays.fill(possibleTriplets, false); // Reset list
int i=0;
while (i<boardTripletIndices.length) {
int triplet = (((board[boardTripletIndices[i++]] << ALPHABET_SIZE) +
board[boardTripletIndices[i++]]) << ALPHABET_SIZE) +
board[boardTripletIndices[i++]];
possibleTriplets[triplet] = true;
}
}
void checkWordTriplets() {
candidateCount = 0;
for (DictionaryEntry entry: dictionary) {
boolean ok = true;
int len = entry.triplets.length;
for (int t=0; (t<len) && ok; t++)
ok = possibleTriplets[entry.triplets[t]];
if (ok) candidateWords[candidateCount++] = entry;
}
}
void checkWords() { // Can probably be optimized a lot
foundCount = 0;
for (int i=0; i<candidateCount; i++) {
DictionaryEntry candidate = candidateWords[i];
for (int j=0; j<board.length; j++)
if (board[j]==candidate.letters[0]) {
usedBoardPositions[0] = j;
if (checkNextLetters(candidate, 1, j)) {
foundWords[foundCount++] = candidate;
break;
}
}
}
}
boolean checkNextLetters(DictionaryEntry candidate, int letter, int pos) {
if (letter==candidate.letters.length) return true;
int match = candidate.letters[letter];
for (int move: moves) {
int next=pos+move;
if ((next>=0) && (next<board.length) && (board[next]==match) && !isWrap(pos, next)) {
boolean ok = true;
for (int i=0; (i<letter) && ok; i++)
ok = usedBoardPositions[i]!=next;
if (ok) {
usedBoardPositions[letter] = next;
if (checkNextLetters(candidate, letter+1, next)) return true;
}
}
}
return false;
}
// Just some helper functions
String formatTime(long start, long end, long repetitions) {
long time = (end-start)/repetitions;
return time/1000000 + "." + (time/100000) % 10 + "" + (time/10000) % 10 + "ms";
}
String getWord(DictionaryEntry entry) {
char[] result = new char[entry.letters.length];
int i=0;
for (int letter: entry.letters)
result[i++] = (char) (letter+97);
return new String(result);
}
void run() throws IOException {
long start = System.nanoTime();
// The following can be pre-computed and should be replaced by constants
dictionary = buildDictionary("C:/TWL06.txt");
boardTripletIndices = buildTripletIndices();
long precomputed = System.nanoTime();
// The following only needs to run once at the beginning of the program
candidateWords = new DictionaryEntry[dictionary.length]; // WAAAY too generous
foundWords = new DictionaryEntry[dictionary.length]; // WAAAY too generous
usedBoardPositions = new int[maxWordLength];
long initialized = System.nanoTime();
for (int n=1; n<=100; n++) {
// The following needs to run again for every new board
initializeBoard(new String[] {"DGHI",
"KLPS",
"YEUT",
"EORN"});
setPossibleTriplets();
checkWordTriplets();
checkWords();
}
long solved = System.nanoTime();
// Print out result and statistics
System.out.println("Precomputation finished in " + formatTime(start, precomputed, 1)+":");
System.out.println(" Words in the dictionary: "+dictionary.length);
System.out.println(" Longest word: "+maxWordLength+" letters");
System.out.println(" Number of triplet-moves: "+boardTripletIndices.length/3);
System.out.println();
System.out.println("Initialization finished in " + formatTime(precomputed, initialized, 1));
System.out.println();
System.out.println("Board solved in "+formatTime(initialized, solved, 100)+":");
System.out.println(" Number of candidates: "+candidateCount);
System.out.println(" Number of actual words: "+foundCount);
System.out.println();
System.out.println("Words found:");
int w=0;
System.out.print(" ");
for (int i=0; i<foundCount; i++) {
System.out.print(getWord(foundWords[i]));
w++;
if (w==10) {
w=0;
System.out.println(); System.out.print(" ");
} else
if (i<foundCount-1) System.out.print(", ");
}
System.out.println();
}
public static void main(String[] args) throws IOException {
new BoggleSolver().run();
}
}
Hier sind einige Ergebnisse:
Für das Gitter aus dem Bild in der ursprünglichen Frage gestellt (DGHI ...):
Precomputation finished in 239.59ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 408
Initialization finished in 0.22ms
Board solved in 3.70ms:
Number of candidates: 230
Number of actual words: 163
Words found:
eek, eel, eely, eld, elhi, elk, ern, erupt, erupts, euro
eye, eyer, ghi, ghis, glee, gley, glue, gluer, gluey, glut
gluts, hip, hiply, hips, his, hist, kelp, kelps, kep, kepi
kepis, keps, kept, kern, key, kye, lee, lek, lept, leu
ley, lunt, lunts, lure, lush, lust, lustre, lye, nus, nut
nuts, ore, ort, orts, ouph, ouphs, our, oust, out, outre
outs, oyer, pee, per, pert, phi, phis, pis, pish, plus
plush, ply, plyer, psi, pst, pul, pule, puler, pun, punt
punts, pur, pure, puree, purely, pus, push, put, puts, ree
rely, rep, reply, reps, roe, roue, roup, roups, roust, rout
routs, rue, rule, ruly, run, runt, runts, rupee, rush, rust
rut, ruts, ship, shlep, sip, sipe, spue, spun, spur, spurn
spurt, strep, stroy, stun, stupe, sue, suer, sulk, sulker, sulky
sun, sup, supe, super, sure, surely, tree, trek, trey, troupe
troy, true, truly, tule, tun, tup, tups, turn, tush, ups
urn, uts, yeld, yelk, yelp, yelps, yep, yeps, yore, you
your, yourn, yous
Für die Buchstaben wie das Beispiel in der ursprünglichen Frage gestellt (FXIE ...)
Precomputation finished in 239.68ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 408
Initialization finished in 0.21ms
Board solved in 3.69ms:
Number of candidates: 87
Number of actual words: 76
Words found:
amble, ambo, ami, amie, asea, awa, awe, awes, awl, axil
axile, axle, boil, bole, box, but, buts, east, elm, emboli
fame, fames, fax, lei, lie, lima, limb, limbo, limbs, lime
limes, lob, lobs, lox, mae, maes, maw, maws, max, maxi
mesa, mew, mewl, mews, mil, mile, milo, mix, oil, ole
sae, saw, sea, seam, semi, sew, stub, swam, swami, tub
tubs, tux, twa, twae, twaes, twas, uts, wae, waes, wamble
wame, wames, was, wast, wax, west
Für das folgende 5x5-Raster:
R P R I T
A H H L N
I E T E P
Z R Y S G
O G W E Y
es gibt so aus:
Precomputation finished in 240.39ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 768
Initialization finished in 0.23ms
Board solved in 3.85ms:
Number of candidates: 331
Number of actual words: 240
Words found:
aero, aery, ahi, air, airt, airth, airts, airy, ear, egest
elhi, elint, erg, ergo, ester, eth, ether, eye, eyen, eyer
eyes, eyre, eyrie, gel, gelt, gelts, gen, gent, gentil, gest
geste, get, gets, gey, gor, gore, gory, grey, greyest, greys
gyre, gyri, gyro, hae, haet, haets, hair, hairy, hap, harp
heap, hear, heh, heir, help, helps, hen, hent, hep, her
hero, hes, hest, het, hetero, heth, hets, hey, hie, hilt
hilts, hin, hint, hire, hit, inlet, inlets, ire, leg, leges
legs, lehr, lent, les, lest, let, lethe, lets, ley, leys
lin, line, lines, liney, lint, lit, neg, negs, nest, nester
net, nether, nets, nil, nit, ogre, ore, orgy, ort, orts
pah, pair, par, peg, pegs, peh, pelt, pelter, peltry, pelts
pen, pent, pes, pest, pester, pesty, pet, peter, pets, phi
philter, philtre, phiz, pht, print, pst, rah, rai, rap, raphe
raphes, reap, rear, rei, ret, rete, rets, rhaphe, rhaphes, rhea
ria, rile, riles, riley, rin, rye, ryes, seg, sel, sen
sent, senti, set, sew, spelt, spelter, spent, splent, spline, splint
split, stent, step, stey, stria, striae, sty, stye, tea, tear
teg, tegs, tel, ten, tent, thae, the, their, then, these
thesp, they, thin, thine, thir, thirl, til, tile, tiles, tilt
tilter, tilth, tilts, tin, tine, tines, tirl, trey, treys, trog
try, tye, tyer, tyes, tyre, tyro, west, wester, wry, wryest
wye, wyes, wyte, wytes, yea, yeah, year, yeh, yelp, yelps
yen, yep, yeps, yes, yester, yet, yew, yews, zero, zori
Dazu habe ich die TWL06 Turnier Scrabble Wortliste , da der Link in der ursprünglichen Frage nicht mehr funktioniert . Diese Datei ist 1.85MB, so ist es ein bisschen kürzer. Und die buildDictionary Funktion wirft alle Wörter mit weniger als 3 Buchstaben.
Hier sind ein paar Beobachtungen über die Leistung dieses:
-
Es ist etwa 10-mal langsamer als die gemeldete Leistung von Victor Nicollet der OCaml Umsetzung. Ob dies durch den anderen Algorithmus verursacht wird, desto kürzer Wörterbuch er verwendet wird, die Tatsache, dass sein Code kompiliert und Mine läuft in einer virtuellen Java-Maschine oder die Leistung unserer Computer (Mine ist ein Intel Q6600 @ 2,4 MHz läuft WinXP), Ich weiß es nicht. Aber es ist viel schneller als die Ergebnisse für die anderen Implementierungen am Ende der ursprünglichen Frage zitiert. Also, ob dieser Algorithmus zum Trie-Wörterbuch überlegen ist oder nicht, weiß ich nicht an dieser Stelle.
-
Die Tabelle Methode in
checkWordTriplets()verwendet ergibt sich eine sehr gute Annäherung an die tatsächlichen Antworten. Nur noch 1 in 3-5 Worten von ihm geleitet werden dencheckWords()Test nicht bestehen (Siehe Anzahl der Kandidaten vs. Anzahl der tatsächlichen Worte oben). -
Etwas, das man nicht oben sehen: Die
checkWordTriplets()Funktion dauert etwa 3.65ms und ist daher vollständig dominant in dem Suchprozess. DiecheckWords()Funktion nimmt so ziemlich den restlichen 0,05-0,20 ms. -
Die Ausführungszeit der
checkWordTriplets()Funktion linear von der Größe des Wörterbuchs abhängt und praktisch unabhängig von Plattengröße! -
Die Ausführungszeit von
checkWords()hängt von der Plattengröße und die Anzahl der Worte nicht durchcheckWordTriplets()ausgeschlossen. -
Die
checkWords()Implementierung oben ist die dümmste erste Version kam ich mit. Es ist im Grunde nicht optimiert. Aber verglich es mitcheckWordTriplets()für die Gesamtleistung der Anwendung irrelevant ist, so dass ich nicht darum kümmern. Aber , wenn die Plattengröße größer wird, wird diese Funktion erhalten langsamer und langsamer und wird schließlich auf die Materie beginnen. Dann würde es muß auch optimiert werden. -
Eine nette Sache über diesen Codes ist seine Flexibilität:
- Sie können leicht die Platinengröße ändern:. Update-Linie 10 und die String-Array übergeben
initializeBoard() - Es kann größer / verschiedene Alphabete unterstützen und kann die Dinge handhaben wie ‚Qu‘ als ein Brief ohne Performance-Overhead zu behandeln. Dazu müßte man aktualisieren Linie 9 und das Paar von Orten, an denen Zeichen in Zahlen umgewandelt werden (derzeit nur von 65 aus dem ASCII-Wert subtrahiert wird)
- Sie können leicht die Platinengröße ändern:. Update-Linie 10 und die String-Array übergeben
Ok, aber ich denke, jetzt durch diesen Beitrag waaaay lang genug ist. Ich kann auf jeden Fall beantworten alle Fragen, die Sie haben könnten, aber wir, dass auf die Ausführungen bewegen.
Überraschenderweise versucht niemand eine PHP-Version dieser.
Dies ist eine funktionierende PHP-Version von John Fouhy Python-Lösung.
Obwohl ich einige Hinweise nahm von allen anderen Antworten, dies ist vor allem von John kopiert.
$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);
Hier ist ein , wenn Sie es ausprobieren möchten. Obwohl es ~ 2s in meinem lokalen Rechner Anspruch nimmt, dauert es ~ 5s auf meinem Webserver. In jedem Fall ist es nicht sehr schnell. Noch aber ist es ziemlich scheußlich, damit ich die Zeit deutlich reduziert werden sich vorstellen können kann. Alle Hinweise auf, wie das zu bewerkstelligen wäre sehr hilfreich. PHP Mangel an Tupeln gemacht, um die Koordinaten seltsam, mit zu arbeiten und meiner Unfähigkeit, nur um zu begreifen, was zur Hölle los ist überhaupt nicht helfen.
Bearbeiten . Einige Korrekturen dauern, es weniger als 1 s lokal
Nicht interessiert in VB? :) Ich konnte nicht widerstehen. Ich habe dies anders gelöst als viele der Lösungen vorgestellt.
Meine Zeiten sind:
- Laden der Wörterbuch und Wort Präfixe in eine Hash-Tabelle. 0,5-1 Sekunden
- Das Finden der Wörter: Lungs unter 10 Millisekunden .
EDIT: Wörterbuch Ladezeiten auf dem Web-Host-Server ausgeführt werden etwa 1 bis 1,5 Sekunden länger als mein Heimcomputer
.Ich weiß nicht, wie schlecht die Zeiten mit einer Last auf dem Server verschlechtern werden.
Ich schrieb meine Lösung als Webseite in .Net. myvrad.com/boggle
Ich bin mit dem Wörterbuch in der ursprünglichen Frage verwiesen wird.
Briefe werden nicht in einem Wort wiederverwendet werden. Nur Worte 3 Zeichen oder mehr gefunden werden.
Ich bin mit einem Hash-Tabelle aller eindeutigen Wort Präfixe und Wörter anstelle eines Trie. Ich wusste nicht, über trie ist, damit ich dort etwas gelernt. Die Idee, eine Liste von Präfixen von Worten zusätzlich zu den vollständigen Worten zu schaffen ist, was endlich meine Zeiten auf eine respektable Zahl.
Lesen Sie die Codekommentare für weitere Details.
Hier ist der Code:
Imports System.Collections.Generic
Imports System.IO
Partial Class boggle_Default
'Bob Archer, 4/15/2009
'To avoid using a 2 dimensional array in VB I'm not using typical X,Y
'coordinate iteration to find paths.
'
'I have locked the code into a 4 by 4 grid laid out like so:
' abcd
' efgh
' ijkl
' mnop
'
'To find paths the code starts with a letter from a to p then
'explores the paths available around it. If a neighboring letter
'already exists in the path then we don't go there.
'
'Neighboring letters (grid points) are hard coded into
'a Generic.Dictionary below.
'Paths is a list of only valid Paths found.
'If a word prefix or word is not found the path is not
'added and extending that path is terminated.
Dim Paths As New Generic.List(Of String)
'NeighborsOf. The keys are the letters a to p.
'The value is a string of letters representing neighboring letters.
'The string of neighboring letters is split and iterated later.
Dim NeigborsOf As New Generic.Dictionary(Of String, String)
'BoggleLetters. The keys are mapped to the lettered grid of a to p.
'The values are what the user inputs on the page.
Dim BoggleLetters As New Generic.Dictionary(Of String, String)
'Used to store last postition of path. This will be a letter
'from a to p.
Dim LastPositionOfPath As String = ""
'I found a HashTable was by far faster than a Generic.Dictionary
' - about 10 times faster. This stores prefixes of words and words.
'I determined 792773 was the number of words and unique prefixes that
'will be generated from the dictionary file. This is a max number and
'the final hashtable will not have that many.
Dim HashTableOfPrefixesAndWords As New Hashtable(792773)
'Stores words that are found.
Dim FoundWords As New Generic.List(Of String)
'Just to validate what the user enters in the grid.
Dim ErrorFoundWithSubmittedLetters As Boolean = False
Public Sub BuildAndTestPathsAndFindWords(ByVal ThisPath As String)
'Word is the word correlating to the ThisPath parameter.
'This path would be a series of letters from a to p.
Dim Word As String = ""
'The path is iterated through and a word based on the actual
'letters in the Boggle grid is assembled.
For i As Integer = 0 To ThisPath.Length - 1
Word += Me.BoggleLetters(ThisPath.Substring(i, 1))
Next
'If my hashtable of word prefixes and words doesn't contain this Word
'Then this isn't a word and any further extension of ThisPath will not
'yield any words either. So exit sub to terminate exploring this path.
If Not HashTableOfPrefixesAndWords.ContainsKey(Word) Then Exit Sub
'The value of my hashtable is a boolean representing if the key if a word (true) or
'just a prefix (false). If true and at least 3 letters long then yay! word found.
If HashTableOfPrefixesAndWords(Word) AndAlso Word.Length > 2 Then Me.FoundWords.Add(Word)
'If my List of Paths doesn't contain ThisPath then add it.
'Remember only valid paths will make it this far. Paths not found
'in the HashTableOfPrefixesAndWords cause this sub to exit above.
If Not Paths.Contains(ThisPath) Then Paths.Add(ThisPath)
'Examine the last letter of ThisPath. We are looking to extend the path
'to our neighboring letters if any are still available.
LastPositionOfPath = ThisPath.Substring(ThisPath.Length - 1, 1)
'Loop through my list of neighboring letters (representing grid points).
For Each Neighbor As String In Me.NeigborsOf(LastPositionOfPath).ToCharArray()
'If I find a neighboring grid point that I haven't already used
'in ThisPath then extend ThisPath and feed the new path into
'this recursive function. (see recursive.)
If Not ThisPath.Contains(Neighbor) Then Me.BuildAndTestPathsAndFindWords(ThisPath & Neighbor)
Next
End Sub
Protected Sub ButtonBoggle_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles ButtonBoggle.Click
'User has entered the 16 letters and clicked the go button.
'Set up my Generic.Dictionary of grid points, I'm using letters a to p -
'not an x,y grid system. The values are neighboring points.
NeigborsOf.Add("a", "bfe")
NeigborsOf.Add("b", "cgfea")
NeigborsOf.Add("c", "dhgfb")
NeigborsOf.Add("d", "hgc")
NeigborsOf.Add("e", "abfji")
NeigborsOf.Add("f", "abcgkjie")
NeigborsOf.Add("g", "bcdhlkjf")
NeigborsOf.Add("h", "cdlkg")
NeigborsOf.Add("i", "efjnm")
NeigborsOf.Add("j", "efgkonmi")
NeigborsOf.Add("k", "fghlponj")
NeigborsOf.Add("l", "ghpok")
NeigborsOf.Add("m", "ijn")
NeigborsOf.Add("n", "ijkom")
NeigborsOf.Add("o", "jklpn")
NeigborsOf.Add("p", "klo")
'Retrieve letters the user entered.
BoggleLetters.Add("a", Me.TextBox1.Text.ToLower.Trim())
BoggleLetters.Add("b", Me.TextBox2.Text.ToLower.Trim())
BoggleLetters.Add("c", Me.TextBox3.Text.ToLower.Trim())
BoggleLetters.Add("d", Me.TextBox4.Text.ToLower.Trim())
BoggleLetters.Add("e", Me.TextBox5.Text.ToLower.Trim())
BoggleLetters.Add("f", Me.TextBox6.Text.ToLower.Trim())
BoggleLetters.Add("g", Me.TextBox7.Text.ToLower.Trim())
BoggleLetters.Add("h", Me.TextBox8.Text.ToLower.Trim())
BoggleLetters.Add("i", Me.TextBox9.Text.ToLower.Trim())
BoggleLetters.Add("j", Me.TextBox10.Text.ToLower.Trim())
BoggleLetters.Add("k", Me.TextBox11.Text.ToLower.Trim())
BoggleLetters.Add("l", Me.TextBox12.Text.ToLower.Trim())
BoggleLetters.Add("m", Me.TextBox13.Text.ToLower.Trim())
BoggleLetters.Add("n", Me.TextBox14.Text.ToLower.Trim())
BoggleLetters.Add("o", Me.TextBox15.Text.ToLower.Trim())
BoggleLetters.Add("p", Me.TextBox16.Text.ToLower.Trim())
'Validate user entered something with a length of 1 for all 16 textboxes.
For Each S As String In BoggleLetters.Keys
If BoggleLetters(S).Length <> 1 Then
ErrorFoundWithSubmittedLetters = True
Exit For
End If
Next
'If input is not valid then...
If ErrorFoundWithSubmittedLetters Then
'Present error message.
Else
'Else assume we have 16 letters to work with and start finding words.
Dim SB As New StringBuilder
Dim Time As String = String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString())
Dim NumOfLetters As Integer = 0
Dim Word As String = ""
Dim TempWord As String = ""
Dim Letter As String = ""
Dim fr As StreamReader = Nothing
fr = New System.IO.StreamReader(HttpContext.Current.Request.MapPath("~/boggle/dic.txt"))
'First fill my hashtable with word prefixes and words.
'HashTable(PrefixOrWordString, BooleanTrueIfWordFalseIfPrefix)
While fr.Peek <> -1
Word = fr.ReadLine.Trim()
TempWord = ""
For i As Integer = 0 To Word.Length - 1
Letter = Word.Substring(i, 1)
'This optimization helped quite a bit. Words in the dictionary that begin
'with letters that the user did not enter in the grid shouldn't go in my hashtable.
'
'I realize most of the solutions went with a Trie. I'd never heard of that before,
'which is one of the neat things about SO, seeing how others approach challenges
'and learning some best practices.
'
'However, I didn't code a Trie in my solution. I just have a hashtable with
'all words in the dicitonary file and all possible prefixes for those words.
'A Trie might be faster but I'm not coding it now. I'm getting good times with this.
If i = 0 AndAlso Not BoggleLetters.ContainsValue(Letter) Then Continue While
TempWord += Letter
If Not HashTableOfPrefixesAndWords.ContainsKey(TempWord) Then
HashTableOfPrefixesAndWords.Add(TempWord, TempWord = Word)
End If
Next
End While
SB.Append("Number of Word Prefixes and Words in Hashtable: " & HashTableOfPrefixesAndWords.Count.ToString())
SB.Append("<br />")
SB.Append("Loading Dictionary: " & Time & " - " & String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString()))
SB.Append("<br />")
Time = String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString())
'This starts a path at each point on the grid an builds a path until
'the string of letters correlating to the path is not found in the hashtable
'of word prefixes and words.
Me.BuildAndTestPathsAndFindWords("a")
Me.BuildAndTestPathsAndFindWords("b")
Me.BuildAndTestPathsAndFindWords("c")
Me.BuildAndTestPathsAndFindWords("d")
Me.BuildAndTestPathsAndFindWords("e")
Me.BuildAndTestPathsAndFindWords("f")
Me.BuildAndTestPathsAndFindWords("g")
Me.BuildAndTestPathsAndFindWords("h")
Me.BuildAndTestPathsAndFindWords("i")
Me.BuildAndTestPathsAndFindWords("j")
Me.BuildAndTestPathsAndFindWords("k")
Me.BuildAndTestPathsAndFindWords("l")
Me.BuildAndTestPathsAndFindWords("m")
Me.BuildAndTestPathsAndFindWords("n")
Me.BuildAndTestPathsAndFindWords("o")
Me.BuildAndTestPathsAndFindWords("p")
SB.Append("Finding Words: " & Time & " - " & String.Format("{0}:{1}:{2}:{3}", Date.Now.Hour.ToString(), Date.Now.Minute.ToString(), Date.Now.Second.ToString(), Date.Now.Millisecond.ToString()))
SB.Append("<br />")
SB.Append("Num of words found: " & FoundWords.Count.ToString())
SB.Append("<br />")
SB.Append("<br />")
FoundWords.Sort()
SB.Append(String.Join("<br />", FoundWords.ToArray()))
'Output results.
Me.LiteralBoggleResults.Text = SB.ToString()
Me.PanelBoggleResults.Visible = True
End If
End Sub
End Class
Sobald ich das Problem Aussage sah, dachte ich „Trie“. Aber wie einige andere Plakate gemacht Verwendung dieses Ansatzes zu sehen, suchte ich nach einem anderen Ansatz nur anders zu sein. Leider führt der Trie-Ansatz besser. Ich lief Kents Perl-Lösung auf meiner Maschine und es dauerte 0,31 Sekunden zu laufen, nachdem sie die Anpassung meine Wörterbuch-Datei zu verwenden. Meine eigene Perl-Implementierung erforderlich 0,54 Sekunden zu laufen.
Dies war mein Ansatz:
-
einen Übergang Hash Erstellen Sie die Rechtsübergänge zu modellieren.
-
Iteration durch alle 16 ^ 3 möglich, drei Buchstabenkombinationen.
- In der Schleife, illegale Übergänge ausschließen und wiederholte Besuche auf dem gleicher Platz. Bilden alle rechtlichen 3-Buchstaben-Sequenzen und speichern sie in einer Hash.
-
Dann Schleife durch alle Wörter im Wörterbuch.
- Schließen Sie Wörter, die zu lang oder kurz sind
- Schieben Sie ein 3-Buchstaben-Fenster über jedes Wort und sehen, ob es unter den 3-Buchstaben-Kombinationen aus Schritt 2. Wörter ausschließen, die fehlschlagen. Dies beseitigt die meisten Nicht-Spielen.
- Falls noch nicht beseitigt wurde, verwenden Sie einen rekursiven Algorithmus, um zu sehen, ob das Wort, indem sie Wege durch das Puzzle gebildet werden kann. (Dieser Teil ist langsam, aber selten genannt.)
-
Drucken Sie die Worte, die ich gefunden.
Ich habe versucht, mit 3 Buchstaben und 4-Buchstaben-Sequenzen, aber 4-Buchstaben-Sequenzen verlangsamten das Programm nach unten.
In meinem Code verwende ich / usr / share / dict / words für meinen Wörterbuch. Es wird standardmäßig auf MAC OS X und viele Unix-Systeme. Sie können eine andere Datei verwenden, wenn Sie möchten. Um ein anderes Rätsel zu knacken, ändern Sie einfach die Variable @puzzle. Dies wäre leicht für größere Matrizen anzupassen. Sie würden nur die% Übergänge Hash und% legalTransitions Hash ändern müssen.
Die Stärke dieser Lösung ist, dass der Code ist kurz, und die Datenstrukturen einfach.
Hier ist der Perl-Code (die 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.
}
Ich weiß, ich bin super spät, aber ich habe eine von ihnen vor einer Weile in PHP - nur zum Spaß zu ...
http://www.lostsockdesign.com.au/ Sandbox / boggle / index.php? Buchstaben = fxieamloewbxastu Gefunden 75 Wörter (133 Punkte) in 0,90108 Sekunden
F.........X..I..............E...............
A......................................M..............................L............................O...............................
E....................W............................B..........................X
A..................S..................................................T.................U....
Gibt einen Hinweis auf, was das Programm tatsächlich tun - jeder Buchstabe ist, wo es beginnt, während jeder durch die Muster suchen ‚‘ zeigt einen Weg, es zu nehmen versucht hat. Je mehr '.' dort sind es die weiteren hat gesucht.
Lassen Sie mich wissen, wenn Sie den Code wollen ... es ist eine schreckliche Mischung aus PHP und HTML, die nie gedacht war das Licht des Tages zu sehen, so wage ich es nicht hier posten: P
Ich verbrachte 3 Monate an einer Lösung arbeiten zu dem 10 besten Punkt dicht 5x5 Boggle Boards Problem.
Das Problem ist nun gelöst und angelegt mit vollständiger Offenlegung auf 5 Web-Seiten. Bitte kontaktieren Sie mich mit Fragen.
Die Platine Analysealgorithmus verwendet einen expliziten Stapel Pseudo-rekursiv der Platine Quadrate durch einen gerichteten azyklischer Wortgraph mit direktem Kind Informationen, und ein Zeitstempel Verfolgungsmechanismus durchquert. Dies kann sehr gut die fortschrittlichste Lexikon Datenstruktur der Welt sein.
Das System wertet rund 10.000 sehr gute Platten pro Sekunde auf einem Quad-Core. (9500+ Punkte)
Übergeordnetes Web-Seite:
DeepSearch.c - http://www.pathcom.com/~vadco/deep. html
Die Komponente Web-Seiten:
Optimale Anzeigetafel - http://www.pathcom.com/~vadco/binary.html
Erweiterte Lexikon Struktur - http://www.pathcom.com/~vadco/adtdawg. html
Brettanalysealgorithmus - http://www.pathcom.com/~vadco/guns. html
Parallel Stapelverarbeitung - http://www.pathcom.com/~vadco/parallel. html
- Dieses umfassende Oeuvre wird nur eine Person interessieren, die das Beste abverlangt.
Hat Ihr Suchalgorithmus ständig die Wortliste ab, wenn Sie Ihre Suche weiter?
Zum Beispiel oben bei der Suche gibt es nur 13 Buchstaben, die Ihre Worte mit (effektiv zu reduzieren, um halb so vielen Anfangsbuchstabe) beginnen können.
Wenn Sie mehr Buchstaben Permutationen hinzufügen würde es weiter verringern die verfügbaren Wortsätze verringert die Suche notwendig.
Ich würde dort beginnen.
Ich muß mehr Gedanken zu einer vollständigen Lösung geben, aber als praktische Optimierung, frage ich mich, ob es eine Tabelle mit Frequenzen von Digramme und trigrams Pre-Computing (2- und 3-Buchstaben-Kombinationen) wert sein könnte basierend auf alle Wörter aus dem Wörterbuch, und verwenden Sie diese Suche zu priorisieren. Ich würde mit den Anfangsbuchstaben der Wörter gehen. Also, wenn Ihr Wörterbuch enthalten die Worte „Indien“, „Wasser“, „Extreme“ und „Außerordentlich“, dann Ihre vorausberechnete Tabelle könnte sein:
'IN': 1
'WA': 1
'EX': 2
Dann für diese Bigramme in der Größenordnung von Gemeinsamkeit suchen (erster EX, dann WA / IN)
Lesen Sie zunächst, wie eine der Sprache C # Designer ein ähnliches Problem gelöst: http: //blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Wie er, können Sie mit einem Wörterbuch und den canonacalize Wörter beginnen mit einem Wörterbuch aus einer Reihe von Buchstaben Erstellen alphabetisch auf eine Liste von Wörtern sortiert, die aus diesen Buchstaben geschrieben werden können.
Als nächstes starten die möglichen Wörter aus dem Vorstand zu schaffen und suchen sie. Ich vermute, dass Sie ziemlich weit kommen wird, aber es gibt sicherlich mehr Tricks, die Dinge beschleunigen könnte.
Ich schlage vor, dass Sie einen Baum von Buchstaben basierend auf Worte. Der Baum würde von einem Brief structs zusammengesetzt sein, wie folgt:
letter: char
isWord: boolean
Sie dann den Baum aufzubauen, wobei jede Tiefe einen neuen Buchstaben hinzuzufügen. Mit anderen Worten: auf der ersten Ebene würde es das Alphabet sein; dann aus jeder dieser Bäume, gäbe es noch weitere 26 Einträge sein, und so weiter, bis Sie alle Wörter aus Dinkel haben. Hängen Sie auf diesen geparsten Baum, und es werden alle möglichen Antworten schneller suchen.
Mit dieser Baum analysiert, kann man sehr schnell Lösungen finden. Hier ist der Pseudo-Code:
BEGIN:
For each letter:
if the struct representing it on the current depth has isWord == true, enter it as an answer.
Cycle through all its neighbors; if there is a child of the current node corresponding to the letter, recursively call BEGIN on it.
Dies könnte mit einem wenig dynamischen Programmierung beschleunigt werden. Zum Beispiel die beiden in Ihrer Probe ‚sind A die beide neben einem‚E‘und ein‚W‘, die (von dem Punkt sie treffen sie auf) wären identisch. Ich habe nicht genug Zeit haben, um wirklich den Code für diese buchstabieren, aber ich denke, Sie auf die Idee sammeln können.
Auch ich bin sicher, dass Sie andere Lösungen, wenn Sie Google für „Boggle Solver“ finden werden.
Just for fun, ich implementiert eine in bash. Es ist nicht super schnell, aber vernünftig.
Hilarious. Ich gab fast die gleiche Frage vor ein paar Tagen wegen des gleichen verdammten Spiel! Ich habe jedoch nicht, weil nur google gesucht boggle Löser python und hat alle Antworten, die ich nur wünschen kann.
ich diese Frage der Zeit erkennen, ist gekommen und gegangen, aber da ich auf einem Solver mich arbeitete, und stießen zufällig auf dieses, während über googeln, ich dachte, dass ich einen Verweis auf Mine schreiben sollte, da es ein bisschen von einigen der verschiedenen scheint andere.
wählte ich mit einem flachen Array für das Spielbrett zu gehen, und rekursive Jagden von jedem Buchstaben auf dem Brett zu tun, von gültigen Nachbarn gültigen Nachbarn durchquere, zur Verlängerung der Jagd, wenn die aktuelle Liste der Buchstaben, wenn ein gültiger Präfix ein Index. Während des Verfahren ist die Vorstellung der aktuellen Wortliste von Indizes in Board, keine Briefen, die ein Wort bilden. Wenn der Index überprüft, werden die Indizes übersetzt, um Buchstaben und die Überprüfung durchgeführt.
Der Index ist ein Brute-Force-Wörterbuch, das ein bisschen wie ein Trie ist, sondern ermöglicht Pythonic Abfragen des Index. Wenn die Wörter ‚Katze‘ und ‚cater‘ in der Liste enthalten sind, werden Sie diese erhalten im Wörterbuch:
d = { 'c': ['cat','cater'],
'ca': ['cat','cater'],
'cat': ['cat','cater'],
'cate': ['cater'],
'cater': ['cater'],
}
Wenn also die current_word sind ‚ca‘ wissen Sie, dass es sich um einen gültiger Präfix ist, weil 'ca' in d True zurück (weiter so das Board Traversal). Und wenn die current_word ist ‚Katze‘, dann wissen Sie, dass es sich um ein gültiges Wort ist, weil es ein gültiges Präfix ist und 'cat' in d['cat'] kehrt zu wahr.
Wenn, wie dies für einige lesbaren Code erlaubt das Gefühl, dass nicht zu langsam scheint. Wie jeder andere in diesem System die Kosten ist das Lesen / Aufbau des Index. das Board zu lösen, ist ziemlich viel Lärm.
Der Code ist unter http://gist.github.com/268079 . Es ist absichtlich vertikal und naiv mit vielen expliziten Gültigkeitsüberprüfung, weil ich das Problem ohne crufting es mit einem Bündel von Magie oder Dunkelheit.
verstehen wollteIch schrieb meinen Löser in C ++. Ich implementiert eine benutzerdefinierte Baumstruktur. Ich bin nicht sicher, kann es ein Trie in Betracht gezogen werden, aber es ist ähnlich. Jeder Knoten verfügt über 26 Zweige, 1 für jeden Buchstaben des Alphabets. Ich durchqueren die Zweige der boggle Platte parallel zu den Zweigen mein Wörterbuch. Wenn die Verzweigung nicht im Wörterbuch vorhanden ist, halte ich es auf dem Boggle Board suchen. Ich konvertiert alle Buchstaben auf dem Brett zu ints. So 'A' = 0. Da es nur Arrays ist, Nachschlag ist immer O (1). Jeder Knoten speichert, wenn es abgeschlossen ist, ein Wort, und wie viele Wörter existieren in ihren Kindern. Der Baum wird als Worte beschnitten werden wiederholt festgestellt, für die gleiche Wortsuche zu reduzieren. Ich glaube, Beschneidung ist auch O (1).
CPU: Pentium SU2700 mit 1,3 GHz
RAM: 3GB
Loads Wörterbuch von 178.590 Wörter in <1 Sekunde.
Behebt 100x100 Boggle (boggle.txt) in 4 Sekunden. ~ 44.000 Wörter gefunden.
einen 4x4 Boggle zu lösen, ist zu schnell einen aussagekräftigen Maßstab zu liefern. :)
ein Boggle Board mit N Reihen und M Spalten gegeben, nehmen wir an, die folgende:
- N * M ist wesentlich größer als die Anzahl der möglichen Wörter
- N * M ist wesentlich größer als das längste mögliche Wort
Unter diesen Annahmen wird die Komplexität dieser Lösung ist O (N * M).
Ich denke Vergleich Zeiten für diesen ein Beispiel Board in vielerlei Hinsicht laufen trifft nicht den Punkt, aber aus Gründen der Vollständigkeit, diese Lösung vervollständigt in <0,2 s auf meinem modernen MacBook Pro.
Diese Lösung wird alle möglichen Pfade für jedes Wort im Korpus finden.
#!/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}"
Diese Lösung gibt auch die Richtung, in der jeweiligen Karte suchen
Algo:
1. Uses trie to save all the word in the english to fasten the search
2. The uses DFS to search the words in Boggle
Ausgabe:
Found "pic" directions from (4,0)(p) go → →
Found "pick" directions from (4,0)(p) go → → ↑
Found "pickman" directions from (4,0)(p) go → → ↑ ↑ ↖ ↑
Found "picket" directions from (4,0)(p) go → → ↑ ↗ ↖
Found "picked" directions from (4,0)(p) go → → ↑ ↗ ↘
Found "pickle" directions from (4,0)(p) go → → ↑ ↘ →
Code:
from collections import defaultdict
from nltk.corpus import words
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
english_words = words.words()
# If you wan to remove stop words
# stop_words = set(stopwords.words('english'))
# english_words = [w for w in english_words if w not in stop_words]
boggle = [
['c', 'n', 't', 's', 's'],
['d', 'a', 't', 'i', 'n'],
['o', 'o', 'm', 'e', 'l'],
['s', 'i', 'k', 'n', 'd'],
['p', 'i', 'c', 'l', 'e']
]
# Instead of X and Y co-ordinates
# better to use Row and column
lenc = len(boggle[0])
lenr = len(boggle)
# Initialize trie datastructure
trie_node = {'valid': False, 'next': {}}
# lets get the delta to find all the nighbors
neighbors_delta = [
(-1,-1, "↖"),
(-1, 0, "↑"),
(-1, 1, "↗"),
(0, -1, "←"),
(0, 1, "→"),
(1, -1, "↙"),
(1, 0, "↓"),
(1, 1, "↘"),
]
def gen_trie(word, node):
"""udpates the trie datastructure using the given word"""
if not word:
return
if word[0] not in node:
node[word[0]] = {'valid': len(word) == 1, 'next': {}}
# recursively build trie
gen_trie(word[1:], node[word[0]])
def build_trie(words, trie):
"""Builds trie data structure from the list of words given"""
for word in words:
gen_trie(word, trie)
return trie
def get_neighbors(r, c):
"""Returns the neighbors for a given co-ordinates"""
n = []
for neigh in neighbors_delta:
new_r = r + neigh[0]
new_c = c + neigh[1]
if (new_r >= lenr) or (new_c >= lenc) or (new_r < 0) or (new_c < 0):
continue
n.append((new_r, new_c, neigh[2]))
return n
def dfs(r, c, visited, trie, now_word, direction):
"""Scan the graph using DFS"""
if (r, c) in visited:
return
letter = boggle[r][c]
visited.append((r, c))
if letter in trie:
now_word += letter
if trie[letter]['valid']:
print('Found "{}" {}'.format(now_word, direction))
neighbors = get_neighbors(r, c)
for n in neighbors:
dfs(n[0], n[1], visited[::], trie[letter], now_word, direction + " " + n[2])
def main(trie_node):
"""Initiate the search for words in boggle"""
trie_node = build_trie(english_words, trie_node)
# print the board
print("Given board")
for i in range(lenr):print (boggle[i])
print ('\n')
for r in range(lenr):
for c in range(lenc):
letter = boggle[r][c]
dfs(r, c, [], trie_node, '', 'directions from ({},{})({}) go '.format(r, c, letter))
if __name__ == '__main__':
main(trie_node)
Ich habe eine Lösung in OCaml implementiert. Es vorab kompiliert Wörterbuch als trie und verwendet Zweibuchstabenfolge Frequenzen Kanten zu beseitigen, die noch nie in einem Wort erscheinen könnten zu weiterer Verarbeitung zu beschleunigen.
Es löst Ihr Beispiel Brett in 0,35ms (mit zusätzlichem 6 ms Anlaufzeit, die meist dem Laden die Trie in dem Speicher verwendet ist).
Die Lösungen gefunden:
["swami"; "emile"; "limbs"; "limbo"; "limes"; "amble"; "tubs"; "stub";
"swam"; "semi"; "seam"; "awes"; "buts"; "bole"; "boil"; "west"; "east";
"emil"; "lobs"; "limb"; "lime"; "lima"; "mesa"; "mews"; "mewl"; "maws";
"milo"; "mile"; "awes"; "amie"; "axle"; "elma"; "fame"; "ubs"; "tux"; "tub";
"twa"; "twa"; "stu"; "saw"; "sea"; "sew"; "sea"; "awe"; "awl"; "but"; "btu";
"box"; "bmw"; "was"; "wax"; "oil"; "lox"; "lob"; "leo"; "lei"; "lie"; "mes";
"mew"; "mae"; "maw"; "max"; "mil"; "mix"; "awe"; "awl"; "elm"; "eli"; "fax"]
A Node.JS JavaScript-Lösung. Ermittelt alle 100 einzigartigen Wörter in weniger als einer Sekunde, die Lesewörterbuchdatei enthält (MBA 2012).
Ausgabe:
[ "FAM", "TUX", "TUB", "FAE", "ELI", "ELM", "ELB", "TWA", "TWA", "SAW", "AMI", "SWA",“ SWA“, "AME", "SEA", "SEW", "AES", "AWL", "AWE", "SEA", "AWA", "MIX", "MIL", "AST", "ASE" , "MAX", "MAE", "MAW", "MEW", "AWE", "MES", "AWL", "LIE", "LIM", "AWA", "AES", "BUT",“ BLO“, "WAS", "WAE", "WEA", "LEI", "LEO", "LOB", "LOX", "WEM", "OIL", "OLM", "WEA", "WAE" "Wachs", "WAF", "MILO", "Osten", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "OIME", "AXIL", "Westen",“ TWAE“, "Limb", "WASE", "WAST", "Bleo", "Stub", "KOCHEN", "BOLE", "lime", "Sawt", "LIMA", "MESA", "mewl" "ACHSE", "FAME", "ASEM", "mile", "AMIL", "Sax", "Naht", "SEMI", "SWAM", "AMBO", "AMLI", "axile",“ AMBLE“, "SWAMI", "AWEST", "AWEST", "LIMAX", "LIMES", "Limbu", "Limbo", "eMBox", "semble", "EMBOLE", "Wamble", "FAMBLE" ]
Code:
var fs = require('fs')
var Node = function(value, row, col) {
this.value = value
this.row = row
this.col = col
}
var Path = function() {
this.nodes = []
}
Path.prototype.push = function(node) {
this.nodes.push(node)
return this
}
Path.prototype.contains = function(node) {
for (var i = 0, ii = this.nodes.length; i < ii; i++) {
if (this.nodes[i] === node) {
return true
}
}
return false
}
Path.prototype.clone = function() {
var path = new Path()
path.nodes = this.nodes.slice(0)
return path
}
Path.prototype.to_word = function() {
var word = ''
for (var i = 0, ii = this.nodes.length; i < ii; ++i) {
word += this.nodes[i].value
}
return word
}
var Board = function(nodes, dict) {
// Expects n x m array.
this.nodes = nodes
this.words = []
this.row_count = nodes.length
this.col_count = nodes[0].length
this.dict = dict
}
Board.from_raw = function(board, dict) {
var ROW_COUNT = board.length
, COL_COUNT = board[0].length
var nodes = []
// Replace board with Nodes
for (var i = 0, ii = ROW_COUNT; i < ii; ++i) {
nodes.push([])
for (var j = 0, jj = COL_COUNT; j < jj; ++j) {
nodes[i].push(new Node(board[i][j], i, j))
}
}
return new Board(nodes, dict)
}
Board.prototype.toString = function() {
return JSON.stringify(this.nodes)
}
Board.prototype.update_potential_words = function(dict) {
for (var i = 0, ii = this.row_count; i < ii; ++i) {
for (var j = 0, jj = this.col_count; j < jj; ++j) {
var node = this.nodes[i][j]
, path = new Path()
path.push(node)
this.dfs_search(path)
}
}
}
Board.prototype.on_board = function(row, col) {
return 0 <= row && row < this.row_count && 0 <= col && col < this.col_count
}
Board.prototype.get_unsearched_neighbours = function(path) {
var last_node = path.nodes[path.nodes.length - 1]
var offsets = [
[-1, -1], [-1, 0], [-1, +1]
, [ 0, -1], [ 0, +1]
, [+1, -1], [+1, 0], [+1, +1]
]
var neighbours = []
for (var i = 0, ii = offsets.length; i < ii; ++i) {
var offset = offsets[i]
if (this.on_board(last_node.row + offset[0], last_node.col + offset[1])) {
var potential_node = this.nodes[last_node.row + offset[0]][last_node.col + offset[1]]
if (!path.contains(potential_node)) {
// Create a new path if on board and we haven't visited this node yet.
neighbours.push(potential_node)
}
}
}
return neighbours
}
Board.prototype.dfs_search = function(path) {
var path_word = path.to_word()
if (this.dict.contains_exact(path_word) && path_word.length >= 3) {
this.words.push(path_word)
}
var neighbours = this.get_unsearched_neighbours(path)
for (var i = 0, ii = neighbours.length; i < ii; ++i) {
var neighbour = neighbours[i]
var new_path = path.clone()
new_path.push(neighbour)
if (this.dict.contains_prefix(new_path.to_word())) {
this.dfs_search(new_path)
}
}
}
var Dict = function() {
this.dict_array = []
var dict_data = fs.readFileSync('./web2', 'utf8')
var dict_array = dict_data.split('\n')
for (var i = 0, ii = dict_array.length; i < ii; ++i) {
dict_array[i] = dict_array[i].toUpperCase()
}
this.dict_array = dict_array.sort()
}
Dict.prototype.contains_prefix = function(prefix) {
// Binary search
return this.search_prefix(prefix, 0, this.dict_array.length)
}
Dict.prototype.contains_exact = function(exact) {
// Binary search
return this.search_exact(exact, 0, this.dict_array.length)
}
Dict.prototype.search_prefix = function(prefix, start, end) {
if (start >= end) {
// If no more place to search, return no matter what.
return this.dict_array[start].indexOf(prefix) > -1
}
var middle = Math.floor((start + end)/2)
if (this.dict_array[middle].indexOf(prefix) > -1) {
// If we prefix exists, return true.
return true
} else {
// Recurse
if (prefix <= this.dict_array[middle]) {
return this.search_prefix(prefix, start, middle - 1)
} else {
return this.search_prefix(prefix, middle + 1, end)
}
}
}
Dict.prototype.search_exact = function(exact, start, end) {
if (start >= end) {
// If no more place to search, return no matter what.
return this.dict_array[start] === exact
}
var middle = Math.floor((start + end)/2)
if (this.dict_array[middle] === exact) {
// If we prefix exists, return true.
return true
} else {
// Recurse
if (exact <= this.dict_array[middle]) {
return this.search_exact(exact, start, middle - 1)
} else {
return this.search_exact(exact, middle + 1, end)
}
}
}
var board = [
['F', 'X', 'I', 'E']
, ['A', 'M', 'L', 'O']
, ['E', 'W', 'B', 'X']
, ['A', 'S', 'T', 'U']
]
var dict = new Dict()
var b = Board.from_raw(board, dict)
b.update_potential_words()
console.log(JSON.stringify(b.words.sort(function(a, b) {
return a.length - b.length
})))
Also habe ich diese anderen PHP Weg zur Lösung hinzufügen wollte, da jeder PHP liebt. Es ist ein bisschen von Refactoring ich tun möchte, wie ein regexpression Spiel gegen die Wörterbuch-Datei, aber im Moment bin ich nur das gesamte Wörterbuch-Datei in ein wordlist geladen werden.
Ich tat dies eine verknüpfte Liste Idee verwenden. Jeder Knoten hat einen Zeichenwert, einen Ortswert und einen nächsten Zeiger.
Der Positionswert ist, wie ich herausgefunden habe, wenn zwei Knoten verbunden sind.
1 2 3 4
11 12 13 14
21 22 23 24
31 32 33 34
, die Gitter verwenden So weiß ich zwei Knoten verbunden sind, wenn der Standort des ersten Knotens den zweiten Knoten Lage +/- 1 für die gleiche Zeile entspricht, +/- 9, 10, 11 für die Zeile oben und unten.
Ich verwende Rekursion für die Hauptsuch. Es dauert ein Wort aus der Wortliste, findet alle möglichen Ansatzpunkte, und dann findet rekursiv die nächstmögliche Verbindung, wenn man bedenkt, dass es nicht zu einem Ort gehen kann es schon mit (weshalb ich $ notInLoc hinzufügen).
Wie auch immer, ich weiß es einige Refactoring braucht, und würde gerne Gedanken über hören, wie man es machen sauberen, aber es produziert die richtigen Ergebnisse auf der Grundlage der Wörterbuch-Datei Ich verwende. Je nach Anzahl der Vokale und Kombinationen auf dem Brett, dauert es etwa 3 bis 6 Sekunden. Ich weiß, dass ich einmal die Wörterbuchergebnisse preg_match, dass erheblich reduzieren wird.
<?php
ini_set('xdebug.var_display_max_depth', 20);
ini_set('xdebug.var_display_max_children', 1024);
ini_set('xdebug.var_display_max_data', 1024);
class Node {
var $loc;
function __construct($value) {
$this->value = $value;
$next = null;
}
}
class Boggle {
var $root;
var $locList = array (1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34);
var $wordList = [];
var $foundWords = [];
function __construct($board) {
// Takes in a board string and creates all the nodes
$node = new Node($board[0]);
$node->loc = $this->locList[0];
$this->root = $node;
for ($i = 1; $i < strlen($board); $i++) {
$node->next = new Node($board[$i]);
$node->next->loc = $this->locList[$i];
$node = $node->next;
}
// Load in a dictionary file
// Use regexp to elimate all the words that could never appear and load the
// rest of the words into wordList
$handle = fopen("dict.txt", "r");
if ($handle) {
while (($line = fgets($handle)) !== false) {
// process the line read.
$line = trim($line);
if (strlen($line) > 2) {
$this->wordList[] = trim($line);
}
}
fclose($handle);
} else {
// error opening the file.
echo "Problem with the file.";
}
}
function isConnected($node1, $node2) {
// Determines if 2 nodes are connected on the boggle board
return (($node1->loc == $node2->loc + 1) || ($node1->loc == $node2->loc - 1) ||
($node1->loc == $node2->loc - 9) || ($node1->loc == $node2->loc - 10) || ($node1->loc == $node2->loc - 11) ||
($node1->loc == $node2->loc + 9) || ($node1->loc == $node2->loc + 10) || ($node1->loc == $node2->loc + 11)) ? true : false;
}
function find($value, $notInLoc = []) {
// Returns a node with the value that isn't in a location
$current = $this->root;
while($current) {
if ($current->value == $value && !in_array($current->loc, $notInLoc)) {
return $current;
}
if (isset($current->next)) {
$current = $current->next;
} else {
break;
}
}
return false;
}
function findAll($value) {
// Returns an array of nodes with a specific value
$current = $this->root;
$foundNodes = [];
while ($current) {
if ($current->value == $value) {
$foundNodes[] = $current;
}
if (isset($current->next)) {
$current = $current->next;
} else {
break;
}
}
return (empty($foundNodes)) ? false : $foundNodes;
}
function findAllConnectedTo($node, $value, $notInLoc = []) {
// Returns an array of nodes that are connected to a specific node and
// contain a specific value and are not in a certain location
$nodeList = $this->findAll($value);
$newList = [];
if ($nodeList) {
foreach ($nodeList as $node2) {
if (!in_array($node2->loc, $notInLoc) && $this->isConnected($node, $node2)) {
$newList[] = $node2;
}
}
}
return (empty($newList)) ? false : $newList;
}
function inner($word, $list, $i = 0, $notInLoc = []) {
$i++;
foreach($list as $node) {
$notInLoc[] = $node->loc;
if ($list2 = $this->findAllConnectedTo($node, $word[$i], $notInLoc)) {
if ($i == (strlen($word) - 1)) {
return true;
} else {
return $this->inner($word, $list2, $i, $notInLoc);
}
}
}
return false;
}
function findWord($word) {
if ($list = $this->findAll($word[0])) {
return $this->inner($word, $list);
}
return false;
}
function findAllWords() {
foreach($this->wordList as $word) {
if ($this->findWord($word)) {
$this->foundWords[] = $word;
}
}
}
function displayBoard() {
$current = $this->root;
for ($i=0; $i < 4; $i++) {
echo $current->value . " " . $current->next->value . " " . $current->next->next->value . " " . $current->next->next->next->value . "<br />";
if ($i < 3) {
$current = $current->next->next->next->next;
}
}
}
}
function randomBoardString() {
return substr(str_shuffle(str_repeat("abcdefghijklmnopqrstuvwxyz", 16)), 0, 16);
}
$myBoggle = new Boggle(randomBoardString());
$myBoggle->displayBoard();
$x = microtime(true);
$myBoggle->findAllWords();
$y = microtime(true);
echo ($y-$x);
var_dump($myBoggle->foundWords);
?>
Ich weiß, ich bin wirklich spät auf der Party, aber ich habe realisiert, als Codierung Übung, ein boggle Solver in verschiedenen Programmiersprachen (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) und ich dachte, dass jemand in denen interessiert sein könnte, also lasse ich Link hier: https://github.com/AmokHuginnsson/boggle-solvers
Hier ist die Lösung vordefinierte Wörter in NLTK Toolkit NLTK hat nltk.corpus Paket, dass wir Paket namens Worte haben und es enthält mehr als 2Lakhs englische Worte, die Sie einfach alle in Ihr Programm verwenden können.
Nach der Erstellung Ihrer Matrix in ein Zeichenfeld umwandeln und diesen Code ausführen
import nltk
from nltk.corpus import words
from collections import Counter
def possibleWords(input, charSet):
for word in input:
dict = Counter(word)
flag = 1
for key in dict.keys():
if key not in charSet:
flag = 0
if flag == 1 and len(word)>5: #its depends if you want only length more than 5 use this otherwise remove that one.
print(word)
nltk.download('words')
word_list = words.words()
# prints 236736
print(len(word_list))
charSet = ['h', 'e', 'l', 'o', 'n', 'v', 't']
possibleWords(word_list, charSet)
Ausgabe:
eleven
eleventh
elevon
entente
entone
ethene
ethenol
evolve
evolvent
hellhole
helvell
hooven
letten
looten
nettle
nonene
nonent
nonlevel
notelet
novelet
novelette
novene
teenet
teethe
teevee
telethon
tellee
tenent
tentlet
theelol
toetoe
tonlet
toothlet
tootle
tottle
vellon
velvet
velveteen
venene
vennel
venthole
voeten
volent
volvelle
volvent
voteen
Ich hoffe, dass Sie es.
Hier ist meine Java-Implementierung: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
Trie bauen dauerte 0 Stunden, 0 Minuten, 1 Sekunde, 532 Millisekunden
Word-Benutzer dauerte 0 Stunden, 0 Minuten, 0 Sekunden, 92 Millisekunden
eel eeler eely eer eke eker eld eleut elk ell
elle epee epihippus ere erept err error erupt eurus eye
eyer eyey hip hipe hiper hippish hipple hippus his hish
hiss hist hler hsi ihi iphis isis issue issuer ist
isurus kee keek keeker keel keeler keep keeper keld kele
kelek kelep kelk kell kelly kelp kelper kep kepi kept
ker kerel kern keup keuper key kyl kyle lee leek
leeky leep leer lek leo leper leptus lepus ler leu
ley lleu lue lull luller lulu lunn lunt lunule luo
lupe lupis lupulus lupus lur lure lurer lush lushly lust
lustrous lut lye nul null nun nupe nurture nurturer nut
oer ore ort ouphish our oust out outpeep outpeer outpipe
outpull outpush output outre outrun outrush outspell outspue outspurn outspurt
outstrut outstunt outsulk outturn outusure oyer pee peek peel peele
peeler peeoy peep peeper peepeye peer pele peleus pell peller
pelu pep peplus pepper pepperer pepsis per pern pert pertussis
peru perule perun peul phi pip pipe piper pipi pipistrel
pipistrelle pipistrellus pipper pish piss pist plup plus plush ply
plyer psi pst puerer pul pule puler pulk pull puller
pulley pullus pulp pulper pulu puly pun punt pup puppis
pur pure puree purely purer purr purre purree purrel purrer
puru purupuru pus push puss pustule put putt puture ree
reek reeker reeky reel reeler reeper rel rely reoutput rep
repel repeller repipe reply repp reps reree rereel rerun reuel
roe roer roey roue rouelle roun roup rouper roust rout
roy rue ruelle ruer rule ruler rull ruller run runt
rupee rupert rupture ruru rus rush russ rust rustre rut
shi shih ship shipper shish shlu sip sipe siper sipper
sis sish sisi siss sissu sist sistrurus speel speer spelk
spell speller splurt spun spur spurn spurrer spurt sput ssi
ssu stre stree streek streel streeler streep streke streperous strepsis
strey stroup stroy stroyer strue strunt strut stu stue stull
stuller stun stunt stupe stupeous stupp sturnus sturt stuss stut
sue suer suerre suld sulk sulker sulky sull sully sulu
sun sunn sunt sunup sup supe super superoutput supper supple
supplely supply sur sure surely surrey sus susi susu susurr
susurrous susurrus sutu suture suu tree treey trek trekker trey
troupe trouper trout troy true truer trull truller truly trun
trush truss trust tshi tst tsun tsutsutsi tue tule tulle
tulu tun tunu tup tupek tupi tur turn turnup turr
turus tush tussis tussur tut tuts tutu tutulus ule ull
uller ulu ululu unreel unrule unruly unrun unrust untrue untruly
untruss untrust unturn unurn upper upperer uppish uppishly uppull uppush
upspurt upsun upsup uptree uptruss upturn ure urn uro uru
urus urushi ush ust usun usure usurer utu yee yeel
yeld yelk yell yeller yelp yelper yeo yep yer yere
yern yoe yor yore you youl youp your yourn yoy
Hinweis: I verwendet, um das Wörterbuch und Zeichenmatrix zu Beginn dieses Fadens. Der Code wurde auf mein MacBookPro laufen, ist unten einige Informationen über die Maschine.
Modellname: MacBook Pro
Modell-Identifizierung: MacBookPro8,1
Prozessortyp: Intel Core i5
Prozessorgeschwindigkeit: 2,3 GHz
Anzahl der Prozessoren: 1 |
Gesamtzahl der Kerne: 2
L2-Cache (pro Kern): 256 KB
L3 Cache: 3 MB
Speicher: 4 GB
Boot-ROM-Version: MBP81.0047.B0E
SMC Version (System): 1.68f96
Ich löste dies auch mit Java. Meine Implementierung ist 269 Zeilen lang und ziemlich einfach zu bedienen. Zuerst müssen Sie eine neue Instanz der Boggler Klasse erstellen und dann die Funktion mit dem Netz als Parameter lösen nennen. Es dauert etwa 100 ms das Wörterbuch von 50 000 Worten auf meinem Computer zu laden und es findet die Worte in etwa 10-20 ms. Die gefundenen Wörter werden in einer Arraylist, foundWords gespeichert.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.URISyntaxException;
import java.net.URL;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Boggler {
private ArrayList<String> words = new ArrayList<String>();
private ArrayList<String> roundWords = new ArrayList<String>();
private ArrayList<Word> foundWords = new ArrayList<Word>();
private char[][] letterGrid = new char[4][4];
private String letters;
public Boggler() throws FileNotFoundException, IOException, URISyntaxException {
long startTime = System.currentTimeMillis();
URL path = GUI.class.getResource("words.txt");
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(path.toURI()).getAbsolutePath()), "iso-8859-1"));
String line;
while((line = br.readLine()) != null) {
if(line.length() < 3 || line.length() > 10) {
continue;
}
this.words.add(line);
}
}
public ArrayList<Word> getWords() {
return this.foundWords;
}
public void solve(String letters) {
this.letters = "";
this.foundWords = new ArrayList<Word>();
for(int i = 0; i < letters.length(); i++) {
if(!this.letters.contains(letters.substring(i, i + 1))) {
this.letters += letters.substring(i, i + 1);
}
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
this.letterGrid[i][j] = letters.charAt(i * 4 + j);
}
}
System.out.println(Arrays.deepToString(this.letterGrid));
this.roundWords = new ArrayList<String>();
String pattern = "[" + this.letters + "]+";
for(int i = 0; i < this.words.size(); i++) {
if(this.words.get(i).matches(pattern)) {
this.roundWords.add(this.words.get(i));
}
}
for(int i = 0; i < this.roundWords.size(); i++) {
Word word = checkForWord(this.roundWords.get(i));
if(word != null) {
System.out.println(word);
this.foundWords.add(word);
}
}
}
private Word checkForWord(String word) {
char initial = word.charAt(0);
ArrayList<LetterCoord> startPoints = new ArrayList<LetterCoord>();
int x = 0;
int y = 0;
for(char[] row: this.letterGrid) {
x = 0;
for(char letter: row) {
if(initial == letter) {
startPoints.add(new LetterCoord(x, y));
}
x++;
}
y++;
}
ArrayList<LetterCoord> letterCoords = null;
for(int initialTry = 0; initialTry < startPoints.size(); initialTry++) {
letterCoords = new ArrayList<LetterCoord>();
x = startPoints.get(initialTry).getX();
y = startPoints.get(initialTry).getY();
LetterCoord initialCoord = new LetterCoord(x, y);
letterCoords.add(initialCoord);
letterLoop: for(int letterIndex = 1; letterIndex < word.length(); letterIndex++) {
LetterCoord lastCoord = letterCoords.get(letterCoords.size() - 1);
char currentChar = word.charAt(letterIndex);
ArrayList<LetterCoord> letterLocations = getNeighbours(currentChar, lastCoord.getX(), lastCoord.getY());
if(letterLocations == null) {
return null;
}
for(int foundIndex = 0; foundIndex < letterLocations.size(); foundIndex++) {
if(letterIndex != word.length() - 1 && true == false) {
char nextChar = word.charAt(letterIndex + 1);
int lastX = letterCoords.get(letterCoords.size() - 1).getX();
int lastY = letterCoords.get(letterCoords.size() - 1).getY();
ArrayList<LetterCoord> possibleIndex = getNeighbours(nextChar, lastX, lastY);
if(possibleIndex != null) {
if(!letterCoords.contains(letterLocations.get(foundIndex))) {
letterCoords.add(letterLocations.get(foundIndex));
}
continue letterLoop;
} else {
return null;
}
} else {
if(!letterCoords.contains(letterLocations.get(foundIndex))) {
letterCoords.add(letterLocations.get(foundIndex));
continue letterLoop;
}
}
}
}
if(letterCoords != null) {
if(letterCoords.size() == word.length()) {
Word w = new Word(word);
w.addList(letterCoords);
return w;
} else {
return null;
}
}
}
if(letterCoords != null) {
Word foundWord = new Word(word);
foundWord.addList(letterCoords);
return foundWord;
}
return null;
}
public ArrayList<LetterCoord> getNeighbours(char letterToSearch, int x, int y) {
ArrayList<LetterCoord> neighbours = new ArrayList<LetterCoord>();
for(int _y = y - 1; _y <= y + 1; _y++) {
for(int _x = x - 1; _x <= x + 1; _x++) {
if(_x < 0 || _y < 0 || (_x == x && _y == y) || _y > 3 || _x > 3) {
continue;
}
if(this.letterGrid[_y][_x] == letterToSearch && !neighbours.contains(new LetterCoord(_x, _y))) {
neighbours.add(new LetterCoord(_x, _y));
}
}
}
if(neighbours.isEmpty()) {
return null;
} else {
return neighbours;
}
}
}
class Word {
private String word;
private ArrayList<LetterCoord> letterCoords = new ArrayList<LetterCoord>();
public Word(String word) {
this.word = word;
}
public boolean addCoords(int x, int y) {
LetterCoord lc = new LetterCoord(x, y);
if(!this.letterCoords.contains(lc)) {
this.letterCoords.add(lc);
return true;
}
return false;
}
public void addList(ArrayList<LetterCoord> letterCoords) {
this.letterCoords = letterCoords;
}
@Override
public String toString() {
String outputString = this.word + " ";
for(int i = 0; i < letterCoords.size(); i++) {
outputString += "(" + letterCoords.get(i).getX() + ", " + letterCoords.get(i).getY() + ") ";
}
return outputString;
}
public String getWord() {
return this.word;
}
public ArrayList<LetterCoord> getList() {
return this.letterCoords;
}
}
class LetterCoord extends ArrayList {
private int x;
private int y;
public LetterCoord(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
@Override
public boolean equals(Object o) {
if(!(o instanceof LetterCoord)) {
return false;
}
LetterCoord lc = (LetterCoord) o;
if(this.x == lc.getX() &&
this.y == lc.getY()) {
return true;
}
return false;
}
@Override
public int hashCode() {
int hash = 7;
hash = 29 * hash + this.x;
hash = 24 * hash + this.y;
return hash;
}
}
Ich löste dies in c. Es dauert etwa 48 ms auf meinem Rechner (mit rund 98% der Zeit das Wörterbuch von der Festplatte ausgegeben Laden und die Schaffung der Trie) laufen zu lassen. Das Wörterbuch wird / usr / share / dict / amerikanisch-Englisch, das hat 62.886 Wörter.
Ich löste dies perfekt und sehr schnell. Ich steckte es in einen Android-App. Sehen Sie das Video auf dem Link Play Store, um es in Aktion zu sehen.
Wort Cheats ist eine App, die „Risse“ jedes Matrix-Stil Wortspiel. Diese App wurde gebaut zu mir zu Wort Scrambler betrüge zu helfen. Es kann für die Wortsuche verwendet werden, ruzzle, Worte, Wortsucher, Wort Risse, seien sie sprachlos, und vieles mehr!
Man kann hier gesehen https://play.google.com/store/apps/details ? id = com.harris.wordcracker
Sehen Sie sich die App in Aktion im Video https://www.youtube.com/watch?v=DL2974WmNAI
