Comment trouver la liste des mots possibles à partir d'une matrice de lettre [Boggle Solver]
https://stackoverflow.com/questions/746082
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ces derniers temps je joue un jeu sur mon iPhone appelé Scramble. Certains d'entre vous connaissent peut-être ce jeu comme Boggle. Essentiellement, quand le jeu commence, vous obtenez une matrice de lettres comme ceci:
F X I E
A M L O
E W B X
A S T U
Le but du jeu est de trouver autant de mots que vous pouvez qui peut être formé en enchaînant les lettres ensemble. Vous pouvez commencer par une lettre, et toutes les lettres qui l'entourent sont un jeu équitable, et une fois que vous passez à la lettre suivante, toutes les lettres qui entourent cette lettre sont jeu juste, sauf pour les lettres utilisées précédemment . Ainsi, dans la grille ci-dessus, par exemple, je pourrais venir avec les mots LOB, TUX, SEA, FAME, etc. Les mots doivent être d'au moins 3 caractères et pas plus de caractères NxN, qui serait 16 dans ce jeu, mais peut varier dans certaines implémentations. Bien que ce jeu est amusant et addictif, je suis apparemment pas très bon et je voulais tricher un peu en faisant un programme qui me donnerait les meilleurs mots possibles (plus le mot le vous obtenez plus de points).
(source: boggled.org )
Je suis, malheureusement, pas très bon avec des algorithmes ou leur efficacité et ainsi de suite. Ma première tentative utilise un dictionnaire comme celui-ci (~ 2.3MB) et effectue une recherche linéaire essayant de faire correspondre les combinaisons avec les entrées du dictionnaire. Cela prend un très de temps pour trouver les mots possibles, et puisque vous obtenez seulement 2 minutes par tour, il est tout simplement pas suffisant.
Je suis curieux de voir si les Stackoverflowers peuvent trouver des solutions plus efficaces. Je suis la plupart du temps à la recherche de solutions en utilisant le Big 3 Ps. Python, PHP et Perl, bien que quoi que ce soit avec Java ou C ++ est cool aussi, puisque la vitesse est essentielle
SOLUTIONS ACTUELLES :
- Adam Rosenfield, Python, ~ 20 ans
- John Fouhy, Python, ~ 3 s
- Kent Fredric, Perl, ~ 1 s
- Darius Bacon, Python, ~ 1 s
- rvarcher, VB.NET (lien direct) , ~ 1 s
- Paolo Bergantino, PHP (lien direct) , 5s ~ (~ 2 s localement )
La solution
Ma réponse fonctionne comme les autres, mais je vais le poster, car il semble un peu plus rapide que les autres solutions de Python, de mettre en place plus rapidement le dictionnaire. (J'ai vérifié contre la solution de John Fouhy.) Après l'installation, le temps de résoudre est dans le bruit.
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)
Utilisation de l'échantillon:
# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))
Edit:. Filtrer les mots de moins de 3 longues lettres
Edit 2: Je suis curieux de savoir pourquoi la solution Perl de Kent Fredric était plus rapide; il se trouve à utiliser l'expression régulière correspondant à la place d'un ensemble de caractères. Faire la même chose en Python à propos de double la vitesse.
Autres conseils
La solution la plus rapide que vous allez obtenir impliquera probablement le stockage de votre dictionnaire dans un rel="noreferrer"> Trie . Ensuite, créer une file d'attente de triplets ( x , y , s ), où chaque élément de la file d'attente correspond à un préfixe s d'un mot qui peut être écrit dans la grille, se terminant à l'emplacement ( x , y ). Initialiser la file d'attente avec N x N éléments (où N est la taille de la grille), un élément pour chaque carré de la grille. Ensuite, l'algorithme se déroule comme suit:
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
Si vous stockez votre dictionnaire dans une structure arborescente, tester si + c est un mot ou un préfixe d'un mot qui peut être fait en temps constant (à condition que vous aussi garder une partie des métadonnées supplémentaires dans chaque donnée de files d'attente, par exemple un pointeur vers le noeud courant dans la trie), de sorte que le temps d'exécution de cet algorithme est O (nombre de mots qui peuvent être orthographié).
[Modifier] Voici une implémentation en Python que je viens codé jusqu'à:
#!/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
Exemple d'utilisation:
d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))
Sortie:
[ 'fa', 'xi', 'ie', 'io', 'el', 'am', 'hache', 'ae', 'aw', 'mi', 'ma', « moi », 'lo', 'li', 'oe', 'bœuf', 'em', 'ea', 'ea', 'es', 'wa', 'nous', 'wa', 'bo', 'bu', 'comme', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', « eli », 'orme', 'elb', 'ami', 'ama', 'ame', 'aes', 'alêne', 'awa', 'crainte', 'awa', 'mélange', 'mim', 'mil', 'mam', 'max', 'mae', 'maw', 'Mew', 'mem', 'mes', 'lob', 'LOX', 'lei', 'leo', « mensonge », 'lim', 'huile', 'olm', 'brebis', 'EME', 'cire', 'WAF', 'WAE', 'WAW', 'WEM', 'WEA', 'WEA', 'était', 'waw', 'WAE', 'bob', 'blo', 'Bub', 'mais', 'ast', 'ase', 'asa', 'alène', 'awa', « la crainte », 'awa', 'aes', 'swa', 'swa', 'coudre', 'mer', 'mer', 'vu', 'tux', 'baignoire', 'Tut', 'twa', 'TWA', 'tst', 'utu', 'fama', 'renommée', 'ixil', 'imam', 'amli', 'amil', 'ambon', 'aisselle', 'essieu', « mimi », 'Mima', 'mime', 'milo', 'mile', 'miaulement', 'mese', 'mesa', 'lolo', 'lobo', 'lima', 'lime', 'membre', 'lile', 'Oime', 'oléo', 'Olio', 'hautbois', 'obol', 'Émim', 'emil', 'est', 'facilité', 'wame', 'Wawa', « Wawa ' 'Weam', 'ouest', 'wese', 'wast',' wa se », 'Wawa', 'Wawa', 'ébullition', 'bolo', 'bole', 'bobo', 'blob', 'bleo', 'bubon', 'asem', 'talon', 'stut' 'nagé', 'semi', 'seme', 'joint', 'seax', 'Sasa', 'Sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', ' ilima », 'amble', 'axile', 'awest', 'mamie', 'mambo', 'maxime', 'MEASE', 'mesem', 'limax', 'citrons verts', 'limbes', 'Limbu' 'obole', 'Emesa', 'embox', 'awest', 'swami', 'famble', 'mimble', 'maxima', 'Embolo', 'embole', 'Wamble', 'Semese', ' Semble », 'Sawbwa', 'Sawbwa']
Notes: Ce programme ne fonctionne pas les mots de sortie 1 lettre, ou filtrer par longueur de mot du tout. C'est facile d'ajouter, mais pas vraiment pertinente au problème. Il produit également quelques mots à plusieurs reprises si elles peuvent être orthographié de plusieurs façons. Si un mot donné peut être orthographié de différentes façons (pire des cas: chaque lettre dans la grille est le même (par exemple, « A ») et un mot comme « aaaaaaaaaa » est dans votre dictionnaire), le temps d'exécution va obtenir horriblement exponentielle . Filtrer les doublons et le tri est triviale à due après l'algorithme est terminé.
Pour un dictionnaire speedup, il y a une transformation générale / processus, vous pouvez faire pour réduire considérablement les comparaisons dictionnaire à l'avance.
Étant donné que la grille ci-dessus ne contient que 16 caractères, certains d'entre eux en double, vous pouvez réduire considérablement le nombre de clés au total dans votre dictionnaire en filtrant simplement les entrées qui ont des caractères impossibles à atteindre.
Je pensais que c'était l'optimisation évidente mais en voyant que personne ne l'ai fait je le mentionner.
Il me réduit d'un dictionnaire de 200.000 clés pour seulement 2 000 clés simplement au cours de la passe d'entrée. Ce au moins réduit la surcharge de la mémoire, et qui est sûr de la carte à une augmentation de la vitesse quelque part que la mémoire est infiniment rapide.
Mise en œuvre Perl
Ma mise en œuvre est un peu trop lourde parce que j'accordé de l'importance d'être en mesure de connaître le chemin exact de chaque chaîne extraite, non seulement la validité qui y sont.
J'ai aussi quelques adaptions là qui permettrait théoriquement une grille avec des trous pour fonctionner, et les grilles avec différentes lignes de taille (en supposant que vous obtenez le droit d'entrée et il aligne en quelque sorte).
Le début du filtre est de loin le plus significative goulot d'étranglement dans ma demande, comme précédemment soupçonné, en commentant cette ligne, il gonflerait de 1,5s à 7,5s.
Lors de son exécution, il semble penser tous les chiffres simples sont leurs propres mots valides, mais je suis assez sûr des thats en raison de la façon dont fonctionne le fichier dictionnaire.
Il est un peu gonflé, mais au moins je réutiliser :: Arbre de Trie CPAN
Certaines d'entre elles a été inspiré en partie par les implémentations existantes, certaines d'entre elles je l'avais déjà à l'esprit.
La critique constructive et les moyens de l'améliorer d'accueil (/ moi, il note jamais recherche CPAN pour un solveur Boggle , mais cela était plus amusant de travailler)
mise à jour pour les nouveaux critères
#!/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 ) ;
};
Arc / informations d'exécution pour la comparaison:
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% ==============================
Plus marmonnements sur cette optimisation Regex
L'optimisation de regex J'utilise est inutile pour les dictionnaires multi-résolution, et pour plusieurs résoudre, vous aurez besoin d'un dictionnaire complet, pas un pré-coupé.
Cependant, cela dit, pour un arrêt, permet de résoudre son très rapide. (Perl regex sont en C! :))
Voici quelques ajouts de code différents:
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 minutes.
Vous pouvez diviser le problème en deux morceaux:
- Une sorte d'algorithme de recherche qui énumérer les chaînes possibles dans la grille.
- Une façon de vérifier si une chaîne est un mot valide.
Idéalement, (2) devrait également inclure un moyen de tester si une chaîne est un préfixe d'un mot valide - cela vous permettra d'élaguer votre recherche et d'enregistrer un tas de temps
. est une solution de (2) deAdam Rosenfield Trie. Il est élégant et probablement ce que votre spécialiste des algorithmes préférerait, mais avec les langues modernes et des ordinateurs modernes, nous pouvons être un peu plus paresseux. , Comme Kent suggère également, nous pouvons réduire notre taille du dictionnaire en supprimant les mots qui ont des lettres ne sont pas présents dans la grille. Voici quelques 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; test préfixe à temps constant. Il faut quelques secondes pour charger le dictionnaire que vous LIÉ, mais seulement un couple :-) (notez que words <= prefixes)
, pour une partie (1), je suis enclin à penser en termes de graphiques. Je vais construire un dictionnaire qui ressemble à ceci:
graph = { (x, y):set([(x0,y0), (x1,y1), (x2,y2)]), }
i.e.. graph[(x, y)] est l'ensemble des coordonnées que vous pouvez atteindre à partir (x, y) de position. Je vais aussi ajouter un None de noeud fictif qui se connecte à tout.
bâtiment il est un peu maladroit, parce qu'il ya 8 positions possibles et vous devez faire la vérification des limites. Voici un code python de façon correspondante maladroite:
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))
Ce code crée également un (x,y) de cartographie dictionnaire au caractère correspondant. Cela me permet de transformer une liste des positions en un mot:
def to_word(chardict, pos_list):
return ''.join(chardict[x] for x in pos_list)
Enfin, nous faisons une recherche en profondeur d'abord. La procédure de base est:
- La recherche arrive à un nœud particulier.
- Vérifiez si le chemin pourrait jusqu'à faire partie d'un mot. Dans le cas contraire, ne pas explorer cette branche plus loin.
- Vérifiez si le chemin est jusqu'à présent un mot. Si oui, ajouter à la liste des résultats.
- Découvrez tous les enfants ne fait pas partie du chemin jusqu'à présent.
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)
Exécuter le code comme:
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)
et inspecter res pour voir les réponses. Voici une liste de mots trouvés pour votre exemple, triées par taille:
['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']
Le code prend (littéralement) quelques secondes pour charger le dictionnaire, mais le reste est instantanée sur ma machine.
Ma tentative en Java. Il faut environ 2 s pour lire le fichier et construire Trie, et environ 50 ms pour résoudre le casse-tête. J'ai utilisé le dictionnaire lié à la question (il a quelques mots que je ne connaissais pas existez en anglais tels que 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
Le code source se compose de 6 classes. Je vais les poster ci-dessous (si ce n'est pas la bonne pratique sur StackOverflow, s'il vous plaît me dire).
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;
}
}
Je pense que vous allez probablement passer plus de temps à essayer de faire correspondre des mots qui par votre grille de lettres ne peut peut-être construit. Donc, la première chose que je voudrais faire est d'essayer d'accélérer cette étape et que vous devriez obtenir la plupart du chemin.
Pour cela, je réexprimer la grille comme une table de possibles « mouvements » qui vous indexez par la lettre que vous êtes à la recherche en transition à.
Démarrage en attribuant à chaque lettre d'un alphabet de votre numéro complet (A = 0, B = 1, C = 2, ... et ainsi de suite).
Prenons cet exemple:
h b c d
e e g h
l l k l
m o f p
Et pour l'instant, permet d'utiliser l'alphabet des lettres que nous avons (en général, vous voudrez probablement utiliser le même alphabet chaque fois):
b | c | d | e | f | g | h | k | l | m | o | p
---+---+---+---+---+---+---+---+---+---+----+----
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
Ensuite, vous faites un tableau booléen 2D qui indique si vous avez une certaine transition lettre disponible:
| 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
Maintenant, allez dans votre liste de mots et de convertir les mots aux transitions:
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
Ensuite, vérifiez si ces transitions sont autorisées en les regardant dans votre table:
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
S'ils sont tous autorisés, il y a une chance que peut-être trouvé ce mot.
Par exemple, le mot "casque" peut être exclue sur la 4ème transition (m e: HelMET)., Puisque cette entrée dans votre table est false
Et peut exclure le mot hamster dehors, depuis la première (h à a) la transition n'est pas autorisé (n'existe même pas dans votre tableau).
Maintenant, pour les sans doute très peu de mots que vous reste n'a pas éliminé, essayez de les trouver en fait dans la grille de la façon que vous faites maintenant ou comme suggéré dans certaines des autres réponses ici. Ceci permet d'éviter les faux positifs qui résultent de sauts entre les lettres identiques dans votre grille. Par exemple, le mot « aide » est autorisée par la table, mais pas par la grille.
Quelques conseils supplémentaires d'amélioration de la performance sur cette idée:
-
Au lieu d'utiliser un tableau 2D, utilisez un tableau 1D et calculer simplement l'indice de la deuxième lettre vous. Ainsi, au lieu d'un tableau de 12x12 comme ci-dessus, faire un tableau 1D de longueur 144. Ensuite, si vous utilisez toujours le même alphabet (ie un 26x26 = array 676x1 pour l'alphabet anglais standard), même si toutes les lettres apparaissent dans votre grille , vous pouvez pré-calculer les indices dans ce tableau 1D que vous devez tester pour répondre à vos mots du dictionnaire. Par exemple, les indices de « bonjour » dans l'exemple ci-dessus serait
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 -
Étendre l'idée d'une table 3D (exprimée en tableau 1D), à savoir tous les permis de 3 lettres. De cette façon, vous pouvez éliminer encore plus de mots immédiatement et vous réduisez le nombre de recherches de tableau pour chaque mot de 1: Pour « bonjour », vous avez seulement besoin 3 du tableau: lookups hel, ell, llo. Il sera très rapide à cette table, en passant, comme il n'y a que 400 possibles 3 lettres-mouvements dans votre réseau.
-
Pre-calculer les indices des mouvements dans votre réseau que vous devez inclure dans votre table. Pour l'exemple ci-dessus, vous devez définir les entrées suivantes « True »:
(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] . : - représentent également votre grille de jeu dans un tableau 1-D avec 16 entrées et ont la table pré-calculée 3. contiennent les indices dans ce tableau.
Je suis sûr que si vous utilisez cette approche, vous pouvez obtenir votre code à exécuter incroyablement rapide, si vous avez le précalculée dictionnaire et déjà chargé dans la mémoire.
BTW: Une autre bonne chose à faire, si vous construisez un jeu, est d'exécuter ce genre de choses immédiatement en arrière-plan. Commencer à générer et résoudre le premier jeu alors que l'utilisateur est toujours à la recherche à l'écran de titre sur votre application et obtenir son doigt en position d'appuyer sur « Play ». Ensuite, générer et résoudre le prochain jeu que l'utilisateur joue le précédent. Cela devrait vous donner beaucoup de temps pour exécuter votre code.
(j'aime ce problème, donc je vais probablement être tenté de mettre en œuvre ma proposition en Java dans les prochains jours pour voir comment il fait effectuer ... Je vais poster le code ici une fois que je fais.)
Mise à jour:
Ok, j'avais un peu de temps aujourd'hui et mis en œuvre cette idée en 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();
}
}
Voici quelques résultats:
Pour la grille de l'image affichée dans la question initiale (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
Pour les lettres affichées comme l'exemple dans la question initiale (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
Pour la grille de 5x5-suivante:
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
il donne ceci:
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
Pour cela, j'utilisé le TWL06 Scrabble Word List du tournoi , puisque le lien dans la question initiale de ne fonctionne plus . Ce fichier est 1.85MB, donc il est un peu plus court. Et la fonction buildDictionary jette tous les mots avec moins de 3 lettres.
Voici quelques observations sur les performances de celle-ci:
-
Il est environ 10 fois plus lent que la performance déclarée de la mise en œuvre de Victor OCaml Nicollet. Que cela est causé par l'algorithme différent, le dictionnaire plus court il a utilisé, le fait que son code est compilé et le mien fonctionne dans une machine virtuelle Java, ou les performances de nos ordinateurs (le mien est un processeur Intel Q6600 @ 2.4MHz en cours d'exécution Windows XP), Je ne sais pas. Mais il est beaucoup plus rapide que les résultats pour les autres implémentations cités à la fin de la question initiale. Donc, si cet algorithme est supérieur au dictionnaire Trie ou non, je ne sais pas à ce point.
-
La méthode de table utilisée dans
checkWordTriplets()donne une très bonne approximation des réponses réelles. Seulement 1 en 3-5 mots adoptés par elle échouera le testcheckWords()(voir nombre de candidats vs nombre de mots réels ci-dessus). -
Quelque chose que vous ne pouvez pas voir ci-dessus: La fonction
checkWordTriplets()prend environ 3.65ms et est donc totalement dominante dans le processus de recherche. La fonctioncheckWords()prend à peu près les 0,05-0,20 ms restants. -
Le temps d'exécution de la fonction
checkWordTriplets()dépend linéairement de la taille du dictionnaire et est pratiquement indépendante de la taille de la carte! -
Le temps d'exécution de
checkWords()dépend de la taille de la carte et le nombre de mots pas exclu parcheckWordTriplets(). -
La mise en œuvre de
checkWords()ci-dessus est la première version la plus stupide que je suis venu avec. Il est fondamentalement pas optimisé du tout. Mais par rapport àcheckWordTriplets()il est hors de propos pour la performance globale de l'application, donc je ne vous inquiétez pas à ce sujet. Mais , si la taille de la carte devient plus grande, cette fonction sera plus lente et obtenir plus de temps et éventuellement commencer à la matière. Ensuite, il devrait être optimisé aussi bien. -
Une bonne chose au sujet de ce code est sa flexibilité:
- Vous pouvez facilement changer la taille de la carte. Ligne de mise à jour 10 et le tableau de chaînes est passé à
initializeBoard() - Il peut prendre en charge alphabets plus / différents et peut gérer des choses comme le traitement « Qu » comme une lettre sans frais généraux de performance. Pour ce faire, il faudrait mettre à jour la ligne 9 et le couple des endroits où les personnages sont convertis en nombre (actuellement simplement en soustrayant 65 de la valeur ASCII)
- Vous pouvez facilement changer la taille de la carte. Ligne de mise à jour 10 et le tableau de chaînes est passé à
Ok, mais je pense que maintenant ce poste est waaaay assez longtemps. Je peux certainement répondre à toutes les questions que vous pourriez avoir, mais passons à autre chose que les commentaires.
Étonnamment, personne ne tenta une version PHP de cela.
Ceci est une version de PHP travail de la solution Python John Fouhy.
Bien que je pris quelques conseils de réponses de tous les autres, ce sont la plupart du temps copié de John.
$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);
Voici un lien direct si vous voulez l'essayer. Même si cela prend ~ 2s dans ma machine locale, il faut 5 s ~ sur mon serveur web. Dans les deux cas, il est très rapide. Pourtant, cependant, il est tout à fait que je peux imaginer hideux si le temps peut être considérablement réduite. Tous les conseils sur la façon d'accomplir cela serait apprécié. Le manque de tuples de PHP fait les coordonnées étranges de travailler avec et mon incapacité à comprendre exactement ce que l'enfer se passe n'a pas aidé du tout.
EDIT :. Quelques corrections font prendre moins de 1 s sur place
Pas intéressé par VB? :) Je ne pouvais pas résister. Je l'ai résolu différemment que la plupart des solutions présentées ici.
Mes temps sont:
- Chargement du dictionnaire et préfixes mot dans un Hashtable:. 0,5 à 1 seconde
- Trouver les mots: moyenne de moins de 10 millisecondes .
EDIT: Dictionnaire des temps de chargement sur le serveur hôte Web sont en cours d'exécution d'environ 1 à 1,5 secondes de plus que mon ordinateur personnel
.Je ne sais pas à quel point les temps vont se détériorer avec une charge sur le serveur.
J'ai écrit ma solution comme une page web en .Net. myvrad.com/boggle
J'utilise le dictionnaire référencé dans la question initiale.
Les lettres ne sont pas réutilisés dans un mot. Seuls les mots 3 caractères ou plus se trouvent.
J'utilise une table de hachage de tous les préfixes de mots uniques et des mots au lieu d'une structure arborescente. Je ne savais pas des années donc j'appris Trie quelque chose. L'idée de créer une liste de préfixes de mots en plus des mots complets est ce qui a finalement obtenu mon temps à un nombre respectable.
Lire les commentaires de code pour plus de détails.
Voici le 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
Dès que j'ai vu l'énoncé du problème, je pensais « Trie ». Mais voyant que plusieurs autres affiches font usage de cette approche, je cherchais une autre approche juste pour être différent. Hélas, l'approche Trie fonctionne mieux. J'ai couru la solution Perl de Kent sur ma machine et il a fallu 0,31 secondes pour exécuter, après l'adaptation à utiliser mon fichier dictionnaire. Ma propre implémentation de Perl requis 0,54 secondes pour exécuter.
Ce fut mon approche:
-
Créer un hachage de transition pour modéliser les transitions juridiques.
-
itérer les 16 ^ 3 possibles trois combinaisons de lettres.
- Dans la boucle, exclure des transitions illégales et des visites répétées à la même place. Former toutes les séquences 3 lettres juridiques et les stocker dans une table de hachage.
-
Ensuite, boucle à travers tous les mots dans le dictionnaire.
- Exclure les mots qui sont trop longues ou courtes
- Faites glisser une fenêtre de 3 lettres dans chaque mot et voir si elle est parmi les combos 3 lettres de l'étape 2. Exclure des mots qui échouent. Ceci élimine la plupart des non-matches.
- Si pas encore éliminé, utilisez un algorithme récursif pour voir si le mot peut être formé en faisant des chemins à travers le puzzle. (Cette partie est lente, mais appelée rarement.)
-
Imprimer les mots que j'ai trouvé.
J'ai essayé 3 lettres et des séquences de 4 lettres, mais des séquences de 4 lettres ont ralenti le programme vers le bas.
Dans mon code, j'utilise / usr / share / dict / mots pour mon dictionnaire. Il est livré en standard sur MAC OS X et de nombreux systèmes Unix. Vous pouvez utiliser un autre fichier si vous voulez. Pour casser un autre casse-tête, il suffit de changer la @puzzle variable. Ce serait facile d'adapter pour les matrices plus grandes. Vous juste besoin de changer le hachage% et le hachage% des transitions.
La force de cette solution est que le code est court, et les structures de données simples.
Voici le code Perl (qui utilise trop de variables globales, je sais):
#!/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.
}
Je sais que je suis super en retard, mais j'ai fait un de ces un certain temps il y a PHP - juste pour le plaisir aussi ...
http://www.lostsockdesign.com.au/ bac à sable / Boggle / index.php? lettres = fxieamloewbxastu Trouvé 75 mots (133 pts) 0.90108 secondes
F.........X..I..............E...............
A......................................M..............................L............................O...............................
E....................W............................B..........................X
A..................S..................................................T.................U....
donne une indication de ce que le programme est en train de faire - chaque lettre est où il commence à chercher à travers les modèles tandis que chaque « » montre un chemin qu'il a essayé de prendre. Le plus '.' il y a plus il a fait des recherches.
Faites-moi savoir si vous voulez que le code ... il est un mélange horrible de PHP et HTML qui n'a jamais été destiné à voir la lumière du jour si je n'ose pas poster ici: P
J'ai passé 3 mois à travailler sur une solution au 10 meilleur point 5x5 dense problème de planches Boggle.
Le problème est maintenant résolu et aménagé avec une divulgation complète sur 5 pages Web. S'il vous plaît me contacter pour des questions.
L'algorithme d'analyse de la carte utilise une pile explicite pour traverser pseudo-récursive les places du conseil par un mot graphe acyclique orienté avec l'information enfant direct, et un mécanisme de suivi de l'horodatage. Cela peut très bien être plus structure de données de lexique avancé au monde.
Le système évalue quelque 10 000 tres bonne par seconde sur un quad core. (9500+ points)
Parent Web Page:
DeepSearch.c - http://www.pathcom.com/~vadco/deep. html
Component Pages Web:
Optimal Tableau de bord - http://www.pathcom.com/~vadco/binary.html
Lexique avancée Structure - http://www.pathcom.com/~vadco/adtdawg. html
Analyse Conseil algorithme - http://www.pathcom.com/~vadco/guns. html
Traitement parallèle par lots - http://www.pathcom.com/~vadco/parallel. html
- Cet ensemble complet de travail n'intéressera une personne qui demande le meilleur.
Votre algorithme de recherche diminue sans cesse la liste de mots que votre recherche continue?
Par exemple, dans la recherche ci-dessus il n'y a que 13 lettres que vos mots peuvent commencer avec (réduire efficacement la moitié autant de lettres de départ).
Comme vous ajoutez plus de permutations de lettres il diminuer encore les jeux de mots disponibles en diminuant la recherche nécessaire.
Je commence là.
Je dois donner plus penser à une solution complète, mais comme une optimisation à portée de main, je me demande s'il pourrait être utile avant le calcul d'une table des fréquences de digrammes et trigrammes (2 et de 3 lettres) sur la base sur tous les mots de votre dictionnaire, et l'utiliser pour donner la priorité à votre recherche. Je vais avec les premières lettres des mots. Donc, si votre dictionnaire contient les mots « Inde », « L'eau », « extrême » et « extraordinaire », alors votre table précalculée pourrait être:
'IN': 1
'WA': 1
'EX': 2
Recherchez ensuite ces digrammes dans l'ordre des points communs (première EX, puis WA / IN)
D'abord, lisez comment l'un des concepteurs du langage C # Correction d'un problème connexe: http: //blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Comme lui, vous pouvez commencer par un dictionnaire et les mots canonacalize en créant un dictionnaire à partir d'un tableau de lettres classées par ordre alphabétique à une liste de mots qui peuvent être orthographiés de ces lettres.
Ensuite, commencer à créer les mots possibles du conseil d'administration et les regardant. Je pense que vous obtiendrez assez loin, mais il y a certainement plus de trucs qui pourraient accélérer les choses.
Je suggère faire un arbre de lettres à base de mots. L'arbre serait composé d'une lettre struct, comme ceci:
letter: char
isWord: boolean
Ensuite, vous construisez l'arbre, chaque profondeur l'ajout d'une nouvelle lettre. En d'autres termes, le premier niveau il y aurait l'alphabet; puis de chacun de ces arbres, il y aurait encore une autre 26 entrées, et ainsi de suite, jusqu'à ce que vous avez orthographié tous les mots. Accrochez-vous à cet arbre analysable, et ça va faire toutes les réponses possibles pour rechercher plus rapidement.
Avec cette arbre analysé, vous pouvez très rapidement trouver des solutions. Voici le 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.
Cela pourrait être accéléré avec un peu de programmation dynamique. Par exemple, dans l'échantillon, les deux « A 'sont tous les deux à côté d'un « E » et « W », qui (du point ils les frappent sur) seraient identiques. Je n'ai pas assez de temps pour épeler vraiment le code pour cela, mais je pense que vous pouvez recueillir l'idée.
En outre, je suis sûr que vous trouverez d'autres solutions si vous Google pour « solveur Boggle ».
Juste pour le plaisir, je un bash mis en œuvre. Il est pas super rapide, mais raisonnable.
Hilarant. Je faillis posté la même question il y a quelques jours en raison du même jeu sacrément! Je ne l'ai pas mais parce que recherché google pour python solveur Boggle et a obtenu toutes les réponses que je pouvais souhaiter.
Je me rends compte est venu et allé le temps de cette question, mais depuis que je travaillais moi-même sur un solveur, et sommes tombés sur ce tout en googler à propos, je pensais que je devrais poster une référence à la mienne car il semble un peu différent de certains des autres.
J'ai choisi d'aller avec un tableau plat pour le plateau de jeu, et de faire des chasses récursives de chaque lettre sur la carte, traversant de voisin valide voisin valide, l'extension de la chasse si la liste actuelle des lettres si un préfixe valide Un index. En traversant la notion du mot actuel est la liste des index en conseil, et non pas des lettres qui composent un mot. Lors de la vérification de l'index, les index sont convertis en lettres et le chèque fait.
L'indice est un dictionnaire de la force brute qui est un peu comme une structure arborescente, mais permet des requêtes pythonique de l'indice. Si les sont dans la liste des mots de chat 'et « Cater », vous obtenez ce dans le dictionnaire:
d = { 'c': ['cat','cater'],
'ca': ['cat','cater'],
'cat': ['cat','cater'],
'cate': ['cater'],
'cater': ['cater'],
}
Donc, si le current_word est « ca » vous savez qu'il est un préfixe valide car 'ca' in d renvoie True (donc continuer la traversée du conseil d'administration). Et si le current_word est « chat », alors vous savez qu'il est un mot valide, car il est un préfixe valide et 'cat' in d['cat'] retourne vrai aussi.
Si senti comme cela a permis un certain code lisible qui ne semble pas trop lent. Comme tout le monde la dépense dans ce système est en train de lire / construction de l'index. La résolution du conseil d'administration est à peu près le bruit.
Le code est à http://gist.github.com/268079 . Il est volontairement vertical et naïf avec beaucoup de contrôle de validité explicite parce que je voulais comprendre le problème sans crufting il avec un tas de magie ou de l'obscurité.
J'ai écrit mon solveur en C ++. Je mis en œuvre une structure d'arbre personnalisé. Je ne suis pas sûr qu'il peut être considéré comme un mais il est arborescente similaire. Chaque nœud a 26 branches, 1 pour chaque lettre de l'alphabet. Je traverse les branches du conseil Boggle en parallèle avec les branches de mon dictionnaire. Si la branche n'existe pas dans le dictionnaire, j'arrête la recherche sur la carte Boggle. Je convertir toutes les lettres sur la planche à ints. Donc, « A » = 0. Comme il est juste des réseaux, la recherche est toujours O (1). Chaque nœud stocke si elle complète un mot et combien de mots existent dans ses enfants. L'arbre est émondé que les mots sont trouvés pour réduire la recherche à plusieurs reprises pour les mêmes mots. Je crois que la taille est également O (1).
CPU: Pentium SU2700 1.3GHz
RAM: 3 Go
Charge dictionnaire de 178,590 mots <1 seconde.
Résout 100x100 Boggle (boggle.txt) en 4 secondes. ~ 44.000 mots trouvés.
La résolution d'un 4x4 Boggle est trop rapide pour fournir un point de repère significatif. :)
Étant donné une carte Boggle avec des lignes N et M colonnes, supposons que les éléments suivants:
- N * M est sensiblement plus grand que le nombre de mots possibles
- N * M est sensiblement plus grand que le mot le plus long possible
Sous ces hypothèses, la complexité de cette solution est O (N * M).
Je pense que l'on compare les temps en cours d'exécution pour cette carte un exemple à bien des égards, mais pas la question, par souci d'exhaustivité, cette solution se termine en l'<0,2s sur mon MacBook Pro moderne.
Cette solution trouvera tous les chemins possibles pour chaque mot dans le corpus.
#!/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}"
Cette solution donne également la direction de la recherche dans le conseil donné
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
Sortie:
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)
Je mis en œuvre une solution OCaml. Il précompile un dictionnaire comme Trie, et utilise des fréquences de séquence à deux lettres pour éliminer les bords qui ne pourrait jamais apparaître dans un mot pour accélérer encore le traitement.
Il permet de résoudre votre conseil exemple en 0.35ms (avec un 6ms supplémentaire de temps de démarrage qui est principalement lié au chargement de la mémoire) Trie en.
Les solutions trouvées:
["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"]
Une solution Node.JS JavaScript. Calcule tous les 100 mots uniques en moins d'une seconde qui comprend la lecture du fichier dictionnaire (MBA 2012).
Sortie:
[ "FAM", "TUX", "TUB", "EAF", "ELI", "ELM", "ELB", "TWA", "TWA", "SAW", "AMI", "SWA", » SWA », "AME", "SEA", "SEW", "AES", "AWL", "AWE", "mer", "AWA", "MIX", "MIL", "AST", "ASE" , "MAX", "mae", "MAW", "MEW", "AWE", "MES", "AWL", "LIE", "LIM", "AWA", "AES", "mais", » BLO », "était", "WAE", "WEA", "LEI", "LEO", "LOB", "LOX", "WEM", "huile", "OLM", "WEA", "WAE" , "CIRE", "WAF", "MILO", "EST", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "Oime", "Aisselle", "WEST", » TWAE », "LIMB", "WASE", "WAST", "bleo", "STUB", "BOIL", "Bole", "LIME", "SAWT", "LIMA", "MESA", "miaulement" , "ESSIEU", "FAME", "ASEM", "MILLE", "AMIL", "Seax", "SEAM", "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
})))
Alors, je voulais ajouter une autre façon PHP de résoudre, puisque tout le monde aime PHP. Il y a un peu de refactoring je voudrais faire, comme l'utilisation d'un match de regexpression contre le fichier dictionnaire, mais en ce moment je suis juste charger tout le fichier dictionnaire dans une liste de mots.
Je l'ai fait en utilisant une idée de liste chaînée. Chaque nœud a une valeur de caractère, une valeur de l'emplacement, et un pointeur suivant.
La valeur de l'emplacement est de savoir comment j'ai trouvé si deux noeuds sont connectés.
1 2 3 4
11 12 13 14
21 22 23 24
31 32 33 34
Donc, en utilisant cette grille, je sais que deux noeuds sont connectés si le premier emplacement de noeud est égale à la deuxième noeuds emplacement +/- 1 pour la même rangée, +/- 9, 10, 11 pour la ligne au-dessus et au-dessous.
J'utilise récursion pour la recherche principale. Il faut un mot de la liste des mots, trouve tous les points de départ possibles, puis trouve récursive la prochaine connexion possible, en gardant à l'esprit qu'il ne peut pas aller à un endroit, il est déjà à l'aide (ce qui est la raison pour laquelle j'ajoute $ notInLoc).
Quoi qu'il en soit, je sais qu'il a besoin d'un refactoring, et je serais ravi d'entendre les pensées sur la façon de le rendre plus propre, mais il produit des résultats corrects en fonction du fichier dictionnaire que je utilise. En fonction du nombre de voyelles et des combinaisons sur la carte, il faut environ 3 à 6 secondes. Je sais qu'une fois que je preg_match les résultats du dictionnaire, qui permettra de réduire de manière significative.
<?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);
?>
Je sais que je suis vraiment en retard à la fête mais je l'ai mis en œuvre, comme un exercice de codage, un solveur Boggle dans plusieurs langages de programmation (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) et je pensais que quelqu'un pourrait être intéressé par ceux-ci, donc je laisse le lien ici: https://github.com/AmokHuginnsson/boggle-solvers
Voici la solution en utilisant des mots prédéfinis dans NLTK boîte à outils NLTK a paquet nltk.corpus dans ce que nous avons appelé des mots de paquet et il contient plus de mots anglais 2Lakhs vous pouvez simplement utiliser tous dans votre programme.
Une fois la création de votre matrice convertir en un tableau de caractères et exécuter ce code
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)
Sortie:
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
J'espère que vous l'obtenez.
Voici mon implémentation java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
build a 0 Trie heures, 0 minutes, 1 seconde, 532 millisecondes
Recherche par mot clé a 0 heures, 0 minutes, 0 secondes, 92 millisecondes
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
Remarque: J'ai utilisé la matrice de dictionnaire et de caractère au début de ce fil. Le code a été exécuté sur mon MacBookPro, ci-dessous quelques informations sur la machine.
Nom du modèle: MacBook Pro
Modèle Identifiant: MacBookPro8,1
Nom du processeur: Intel Core i5
Vitesse du processeur: 2,3 GHz
Nombre de processeurs: 1
Nombre total de coeurs: 2
Cache L2 (par noyau): 256 KB
Cache L3: 3 MB
Mémoire: 4 Go
Boot ROM Version: MBP81.0047.B0E
Version SMC (système): 1.68f96
Je résolu ce problème aussi, avec Java. Ma mise en œuvre est de 269 lignes long et assez facile à utiliser. D'abord, vous devez créer une nouvelle instance de la classe Boggler puis appeler la fonction solve avec la grille en tant que paramètre. Il faut environ 100 ms pour charger le dictionnaire de 50 000 mots sur mon ordinateur et il trouve les mots environ 10-20 ms. Les mots trouvés sont stockés dans un ArrayList, foundWords.
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;
}
}
Je résolu ce problème en c. Il faut environ 48 ms pour fonctionner sur ma machine (avec environ 98% du temps passé le chargement du dictionnaire à partir du disque et la création de la structure arborescente). Le dictionnaire est / usr / share / dict / american-anglais qui a 62886 mots.
Je résolu ce problème parfaitement et très rapide. Je l'ai mis dans une application Android. Voir la vidéo sur le lien de magasin de jeu pour le voir en action.
mot Cheats est une application qui « craque » tout style de matrice de jeu de mots. Cette application a été construit à me aider à tricher mot scrambler. Il peut être utilisé pour les recherches de mots, Ruzzle, mots, trouveur de mot, le crack de mot, Boggle, et plus encore!
On peut voir ici https://play.google.com/store/apps/details ? id = com.harris.wordcracker
Voir l'application en action dans la vidéo https://www.youtube.com/watch?v=DL2974WmNAI
