¿Cómo encontrar la lista de posibles palabras de una matriz de carta [Boggle Solver]
https://stackoverflow.com/questions/746082
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Últimamente he estado jugando un juego en mi iPhone llamado Scramble. Algunos de ustedes saben este juego como Boggle. Esencialmente, cuando se inicia el juego se obtiene una matriz de letras, así:
F X I E
A M L O
E W B X
A S T U
El objetivo del juego es encontrar todas las palabras que se pueden que se pueden formar por el encadenamiento de letras juntas. Puede comenzar con cualquier letra, y todas las letras que lo rodean son un juego justo, y luego una vez que pasa a la siguiente letra, todas las cartas que rodean esa carta es un juego justo, a excepción de las cartas usadas previamente . Así que en la rejilla superior, por ejemplo, podría llegar a las palabras LOB, TUX, SEA, FAME, etc. Las palabras deben tener al menos 3 caracteres y no más de caracteres NxN, lo que sería 16 en este juego, pero puede variar en algunas implementaciones. Si bien este juego es divertido y adictivo, no soy aparentemente muy bueno en eso y quería engañar un poco al hacer un programa que me daría las mejores palabras posibles (la más larga sea la palabra, más puntos obtienes).
(fuente: boggled.org )
Soy, por desgracia, no es muy bueno con los algoritmos o sus eficiencias y así sucesivamente. Mi primer intento utiliza un diccionario como este (~ 2.3MB) y hace una búsqueda lineal tratando de igualar las combinaciones con las entradas del diccionario. Esto toma un muy mucho tiempo para encontrar las palabras posibles, y ya que usted consigue solamente 2 minutos por ronda, simplemente no es suficiente.
Estoy interesado en ver si alguna Stackoverflowers pueden llegar a soluciones más eficientes. Estoy sobre todo en busca de soluciones utilizando los 3 grandes Sal:. Python, PHP y Perl, aunque nada con Java o C ++ es demasiado frío, ya que la velocidad es esencial
Las soluciones actuales
- Adam Rosenfield, Python, ~ 20s
- John Fouhy, Python, ~ 3s
- Kent Fredric, Perl, ~ 1s
- Darío Bacon, Python, ~ 1s
- rvarcher, VB.NET (enlace directo) , ~ 1s
- Paolo Bergantino, PHP (enlace directo) , 5s ~ (~ 2s localmente )
Solución
Mi respuesta funciona como los otros aquí, pero voy a publicar porque se ve un poco más rápido que las otras soluciones de Python, desde la creación del diccionario más rápido. (He comprobado esto en contra de la solución de John Fouhy.) Después de la configuración, el tiempo para resolver es en el ruido.
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)
Ejemplo de uso:
# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))
Editar:. Filtro las palabras de menos de 3 letras de longitud
Editar 2: que tenía curiosidad por qué solución Perl de Kent Fredric fue más rápido; resulta de utilizar las expresiones regulares a juego en lugar de un conjunto de caracteres. Hacer lo mismo en Python sobre duplica la velocidad.
Otros consejos
La solución más rápida que va a conseguir supondrá probablemente almacenar su diccionario en un trie . A continuación, crear una cola de tripletes ( x , y , s ), donde cada elemento en la cola corresponde a un prefijo s de una palabra que puede ser escrito en la cuadrícula, terminando en la posición ( x , y ). Inicializar la cola con N x N elementos (donde N es el tamaño de la cuadrícula), un elemento para cada cuadrado de la cuadrícula. Entonces, el algoritmo procede como sigue:
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 almacena su diccionario en un trie, probando si s + c es una palabra o un prefijo de una palabra que se puede hacer en un tiempo constante (que ya ha proporcionado también mantener algunos metadatos extra en cada dato de colas, tales como un puntero al nodo actual en el trie), por lo que el tiempo de ejecución de este algoritmo es O (número de palabras que se pueden deletreado).
[Editar] Aquí está una implementación en Python que acabo codificado por:
#!/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
Ejemplo de uso:
d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))
Salida:
[ 'fa', 'xi', 'es decir', 'io', 'el', 'am', 'hacha', 'ae', 'w', 'mi', 'ma', 'me ', 'lo', 'li', 'oe', 'buey', 'em', 'ea', 'ea', 'es', 'wa', 'nosotros', 'wa', 'Bo', 'bu', 'como', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli ', 'olmo', 'Elb', 'ami', 'ama', 'AME', 'aes', 'punzón', 'awa', 'temor', 'awa', 'mezcla', 'mim', 'mil', 'MAM', 'max', 'Mae', 'fauces', 'mew', 'mem', 'MES', 'globo', 'lox', 'Lei', 'leo', 'mentira ', '', 'aceite lim', 'olm', 'oveja', 'eme', 'cera', 'waf', 'wae', 'waw', 'wem', 'wea', 'wea', 'era', 'waw', 'wae', 'Bob', 'blo', 'Bub' 'pero', 'ast', 'asa', 'asa', 'punzón', 'awa', 'asombro ', 'awa', 'aes', 'SWA', 'SWA', 'coser', 'mar', 'mar', 'vio', 'smoking', 'bañera', 'Tut', 'TWA', 'TWA', 'tst', 'UTU', 'fama', 'fama', 'ixil', 'imán', 'Amli', 'amil', 'ambo', 'axil', 'eje', 'mimi ', 'mima', 'mimo', 'Milo', 'millas', 'maullido', 'mese', 'mesa', 'Lolo', 'Lobo', 'lima', 'cal', 'limbo', 'lile', 'Oime', 'oleo', 'olio', 'oboe', 'óbolo', 'emitas', 'Emil', 'este', 'facilidad', 'wame', 'wawa', 'wawa ' 'weam', 'West', 'wese', 'eras',' wa SE', 'wawa', 'wawa', 'hervir', 'bolo', 'bole', 'bobo', 'blob', 'bleo', 'bubo', 'asem', 'stub', 'stut' , 'nadaron', 'semi', 'costura' 'seme', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', ' ilima', 'preámbulo', 'axile', 'awest', 'mamie', 'Mambo', 'Maxim', 'Mease', 'mesem', 'Limax', 'limas', 'limbo', 'limbu' , 'obole', 'emesa', 'cuadro largo', 'awest', 'swami', 'famble',, 'máximos' 'mimble', 'embolo', 'embolia', 'Wamble', 'Semese', ' semble', 'sawbwa', 'sawbwa']
Notas: Este programa no emitirá palabras 1-carta, o un filtro de longitud de palabra en absoluto. Eso es fácil de añadir, pero no es realmente relevante para el problema. También genera algunas palabras varias veces si pueden ser escritos en múltiples formas. Si una palabra dada se puede escribir de muchas maneras diferentes (peor de los casos: cada letra en la red es la misma (por ejemplo, 'A') y una palabra como 'aaaaaaaaaa' está en su diccionario), entonces el tiempo de ejecución obtendrá terriblemente exponencial . El filtrado de duplicados y la clasificación es trivial debido después de que el algoritmo ha terminado.
Para una aceleración diccionario, hay una transformación / proceso que puede hacer para reducir en gran medida las comparaciones de diccionario antes de tiempo general.
Dado que la red anterior contiene sólo 16 caracteres, algunos de ellos duplicados, se puede reducir considerablemente el número de teclas en total en su diccionario simplemente filtrando las entradas que tienen caracteres inalcanzables.
Me pareció que era la optimización obvia pero al ver que nadie lo hice yo estoy mencionando.
Me redujo de un diccionario de 200.000 a sólo 2.000 llaves llaves simplemente durante el pase de entrada. Esto por lo menos reduce la sobrecarga de la memoria, y que está seguro de asignar a un aumento de la velocidad en algún lugar como memoria no es infinitamente rápido.
Perl Implementación
Mi aplicación es un poco de altos cargos porque coloqué importancia de ser capaz de conocer la ruta exacta de cada cadena extraída, no sólo la validez en el mismo.
También tengo unas pocas adaptaciones ahí que teóricamente permitir una rejilla con agujeros en él para funcionar, y las redes con diferentes líneas de tamaño (suponiendo que se obtiene el derecho de entrada y que se alinee de alguna manera).
El filtro temprana es con mucho el más importante cuello de botella en mi solicitud, como sospechaba anteriormente, al comentar que la línea hincha desde 1,5 segundos a 7.5s.
Tras la ejecución se parece pensar que todos los dígitos individuales se encuentran en sus propias palabras válidas, pero estoy bastante seguro de que eso es debido a la forma en que funciona el archivo de diccionario.
Es un poco hinchada, pero al menos reutilizar Árbol :: Trie de CPAN
Algunos de los que se inspiró en parte por las implementaciones existentes, algunos de los que yo tenía en mente ya.
crítica constructiva y formas en que se podría mejorar de bienvenida (/ Me notas nunca buscó CPAN para un solucionador de Boggle , pero esto fue más divertido trabajar fuera)
actualizado para los nuevos criterios
#!/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 ) ;
};
Arco información / ejecución para la comparación:
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% ==============================
Más murmullos en que la optimización de expresiones regulares
La optimización de expresiones regulares que utilizo es inútil para resolver los múltiples diccionarios, y para resolver los múltiples querrá un diccionario completo, no un pre-recortado uno.
Sin embargo, dicho esto, por una sola vez, resuelve su muy rápido. (Perl expresiones regulares son en C :))
Aquí es algunas adiciones de código diferentes:
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 minutos.
Se puede dividir el problema en dos piezas:
- Una especie de algoritmo de búsqueda que va a enumerar posibles cadenas en la red.
- Una forma de comprobar si una cadena es una palabra válida.
Lo ideal (2) también debe incluir una manera de comprobar si una cadena es un prefijo de una palabra válida - esto le permitirá a podar su búsqueda y ahorrar un montón entero de tiempo
. Triede Adam Rosenfield es una solución de (2). Es elegante y probablemente lo preferiría a su especialista en algoritmos, pero con las lenguas modernas y las computadoras modernas, que puede ser un poco más perezoso. Además, como sugiere Kent, podemos reducir el tamaño del diccionario descartando las palabras que tienen las cartas no están presentes en la red. Aquí hay algo de 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; constante de tiempo de las pruebas de prefijo. Se tarda un par de segundos para cargar el diccionario se ha vinculado, pero sólo un par :-) (notar que words <= prefixes)
Ahora, para la parte (1), me inclino a pensar en términos de gráficos. Así que voy a construir un diccionario que se ve algo como esto:
graph = { (x, y):set([(x0,y0), (x1,y1), (x2,y2)]), }
es decir. graph[(x, y)] es el conjunto de coordenadas que se puede llegar desde la posición (x, y). También voy a añadir un nodo ficticio None que conectará a todo.
Edificio que es un poco torpe, porque hay 8 posiciones posibles y hay que hacer una comprobación de límites. Aquí hay algo de código Python correspondientemente torpe:
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))
Este código también se acumula una (x,y) mapeo de diccionario para el carácter correspondiente. Esto me permite a su vez una lista de posiciones en una palabra:
def to_word(chardict, pos_list):
return ''.join(chardict[x] for x in pos_list)
Por último, hacemos una búsqueda en profundidad. El procedimiento básico es:
- La búsqueda llega a un nodo en particular.
- Compruebe si la ruta hasta el momento podría ser parte de una palabra. Si no es así, no explorar esta rama más.
- Compruebe si la ruta hasta el momento es una palabra. Si es así, añadir a la lista de resultados.
- Explore todos los niños que no forma parte de la ruta hasta el momento.
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)
Ejecutar el código como:
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)
e inspeccionar res para ver las respuestas. He aquí una lista de palabras encontradas por su ejemplo, ordenados por tamaño:
['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']
El código toma (literalmente) un par de segundos para cargar el diccionario, pero el resto es instantáneo en mi máquina.
Mi intento en Java. Se tarda unos 2 s para leer el archivo y construir trie, y alrededor de 50 ms para resolver el rompecabezas. He utilizado el diccionario vinculado en la cuestión (que tiene unas pocas palabras que yo no sabía que existe en Inglés como 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
El código fuente consta de 6 clases. Voy a publicar ellos a continuación (si esta no es la práctica correcta en StackOverflow, por favor dígame).
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;
}
}
Creo que probablemente pasará la mayor parte de su tiempo tratando de coincidir con palabras que no pueden posiblemente ser construido por su rejilla letra. Por lo tanto, lo primero que haría es tratar de acelerar ese paso y que debe conseguir que la mayor parte del camino.
Para esto, me gustaría volver a expresar la rejilla como una tabla de posibles "movimientos" que se indexa por la letra a la transición que está viendo.
Para empezar, asignando a cada letra un número de todo el alfabeto (A = 0, B = 1, C = 2, ... y así sucesivamente).
Tomemos este ejemplo:
h b c d
e e g h
l l k l
m o f p
Y por ahora, vamos a utilizar el alfabeto de las cartas que tenemos (por lo general lo que probablemente desea utilizar el mismo alfabeto entero cada vez):
b | c | d | e | f | g | h | k | l | m | o | p
---+---+---+---+---+---+---+---+---+---+----+----
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
A continuación, hacer una matriz booleana en 2D que indica si tiene una cierta transición letra 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
Ahora ve a través de su lista de palabras y convertir las palabras a las transiciones:
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
A continuación, comprobar si se permite que estas transiciones buscándolas en la tabla:
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
Si todos ellos están permitidos, hay una posibilidad de que esta palabra se podría encontrar.
Por ejemplo, la palabra "casco" se puede descartar que en el cuarto de transición (m ae: casco)., Ya que la entrada de la tabla es false
Y la palabra de hámster se puede descartar, ya que no se permite que el primero (h a a) la transición (ni siquiera existe en la tabla).
Ahora, para las Probablemente muy pocas palabras restantes que no eliminó, trate de encontrar realmente en la red de la forma en que lo está haciendo ahora o como se sugiere en algunas de las otras respuestas aquí. Esto es para evitar los falsos positivos que resultan de saltos entre cartas idénticas en su red. Por ejemplo la palabra "ayuda" es permitido por la mesa, pero no por la red.
Algunos consejos adicionales de mejora del rendimiento en esta idea:
-
En lugar de utilizar una matriz 2D, utilizar una matriz 1D y simplemente calcular el índice de la segunda carta a sí mismo. Así, en lugar de una matriz de 12x12 como la de arriba, hacer una serie 1D de longitud 144. Si a continuación, utilizar siempre el mismo alfabeto (es decir, un 26x26 = 676x1 matriz para el alfabeto Inglés estándar), aunque no todas las cartas se muestran en la cuadrícula , se puede pre-calcular los índices en esta matriz 1D que se necesita para poner a prueba para que coincida con sus palabras del diccionario. Por ejemplo, los índices para 'hola' en el ejemplo anterior serían
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 -
Extender la idea de una mesa de 3D (expresado como una matriz de 1D), es decir, todas las combinaciones permitidas de 3 letras. De esa manera usted puede eliminar aún más las palabras de inmediato y reducir el número de búsquedas de matriz para cada palabra por 1: Para 'hola', sólo necesita 3 búsquedas de matriz: hel, ell, llo. Va a ser muy rápida para construir esta tabla, por cierto, ya que sólo hay 400 posibles de 3 letras se mueve en su red.
-
Pre-calcular los índices de los movimientos en la cuadrícula que debe incluir en su mesa. Para el ejemplo anterior, es necesario establecer las siguientes entradas en '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] . : - también representar su rejilla de juego en una matriz de 1-D con 16 entradas y tienen la tabla pre-calcula en 3. contienen los índices en esta matriz.
Estoy seguro de que si se utiliza este enfoque puede obtener su código para ejecutar increíblemente rápida, si usted tiene el diccionario pre-computados y ya cargado en la memoria.
Por cierto: Otra buena cosa que hacer, si usted está construyendo un juego, es ejecutar este tipo de cosas de inmediato en el fondo. Comenzar a generar y resolver el primer juego, mientras que el usuario todavía está mirando la pantalla del título en su aplicación y conseguir su dedo en posición de presionar "Play". A continuación, generar y resolver el siguiente juego y cuando el usuario toca la anterior. Eso te dará una gran cantidad de tiempo para ejecutar el código.
(me gusta este problema, así que probablemente tendrá la tentación de poner en práctica mi propuesta en Java en algún momento en los próximos días para ver cómo sería en realidad llevar a cabo ... Voy a publicar el código aquí una vez que hago.)
ACTUALIZACIÓN:
Ok, tenía algo de tiempo hoy y práctica esta idea 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();
}
}
Estos son algunos resultados:
En la cuadrícula de la foto publicada en la pregunta original (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
En las cartas enviadas como el ejemplo en la pregunta original (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
En la siguiente 5x5 de la red:
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
se da esto:
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
Para ello he utilizado el TWL06 Torneo de Scrabble lista de palabras , ya que el vínculo en la pregunta original ya no funciona . Este archivo es 1.85MB, así que es un poco más corto. Y la función buildDictionary lanza a cabo todas las palabras con menos de 3 letras.
Aquí hay un par de observaciones sobre el cumplimiento de este:
-
Es aproximadamente 10 veces más lento que el rendimiento de la aplicación reportado OCaml de Victor Nicollet. Ya sea que esto es causado por los diferentes algoritmos, el diccionario más corto que utiliza, el hecho de que su código se compila y la mía se ejecuta en una máquina virtual de Java, o la realización de nuestros ordenadores (mina es un Q6600 @ 2,4 MHz Intel ejecutando WinXP), No lo sé. Pero es mucho más rápido que los resultados de las otras implementaciones citadas al final de la pregunta original. Por lo tanto, si este algoritmo es superior al diccionario trie o no, no sé en este momento.
-
El método de la tabla utilizada en
checkWordTriplets()produce una muy buena aproximación a las respuestas reales. Sólo 1 de cada 3-5 palabras pasaron por ella fallarán la pruebacheckWords()(Ver número de candidatos vs número de palabras reales arriba). -
Algo que no se puede ver arriba: La función
checkWordTriplets()tarda aproximadamente 3.65ms y por lo tanto es totalmente dominante en el proceso de búsqueda. La funcióncheckWords()ocupa más o menos los 0,05-0,20 ms restantes. -
El tiempo de ejecución de la función
checkWordTriplets()depende linealmente del tamaño del diccionario y es prácticamente independiente del tamaño del tablero! -
El tiempo de ejecución de
checkWords()depende del tamaño de la placa y el número de palabras no descartada porcheckWordTriplets(). -
La aplicación
checkWords()anterior es el más tonto primera versión que se me ocurrió. Básicamente no está optimizado en absoluto. Pero en comparación concheckWordTriplets()es irrelevante para el cumplimiento total de la aplicación, por lo que no se preocupe. Pero , si el tamaño de la placa se hace más grande, esta función cada vez más lento y eventualmente comenzar a importar. Entonces, tendría que ser optimizado también. -
Lo bueno de este código es su flexibilidad:
- Usted puede cambiar fácilmente el tamaño del tablero:. Actualización de la línea 10 y la matriz de cadena que se pasa a
initializeBoard() - Puede soportar diferentes alfabetos mayores / y puede manejar cosas como el tratamiento de 'Qu' como una carta sin ninguna sobrecarga de rendimiento. Para ello, sería necesario actualizar la línea 9 y el par de lugares donde los personajes se convierten en números (en la actualidad simplemente restando 65 a partir del valor ASCII)
- Usted puede cambiar fácilmente el tamaño del tablero:. Actualización de la línea 10 y la matriz de cadena que se pasa a
Está bien, pero creo que por ahora este post es muuuucho tiempo suficiente. Definitivamente puedo responder a cualquier pregunta que pueda tener, sino que vamos a pasar a los comentarios.
Sorprendentemente, nadie intentó una versión PHP de esta.
Esta es una versión de PHP de trabajo de la solución del pitón de John Fouhy.
A pesar de que tomé algunas indicaciones de respuestas de todos los demás, esto se copia todo 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);
Este es un enlace directo si quieres probarlo. Aunque toma ~ 2s en mi máquina local, se tarda ~ 5s en mi servidor web. En cualquiera de los casos, no es muy rápido. Aún así, sin embargo, es bastante horrible por lo que puedo imaginar el tiempo puede reducirse significativamente. Cualquier punteros sobre cómo lograr eso sería apreciada. falta de tuplas de PHP hizo las coordenadas extraños para trabajar con y mi incapacidad para comprender qué demonios está pasando no ayuda en absoluto.
Editar . Unos arreglos hacen tarda menos de 1s localmente
No está interesado en VB? :) no me pude resistir. He resuelto esto de manera diferente que muchas de las soluciones que se presentan aquí.
Mis tiempos son:
- Cargando el diccionario de palabras y prefijos en una tabla hash:. 0,5 a 1 segundo
- Encontrar las palabras: promedio de menos de 10 milisegundos .
EDIT: Diccionario tiempos de carga en el servidor de alojamiento web se están ejecutando alrededor de 1 a 1,5 segundos más que mi ordenador de casa
.No sé lo mal que los tiempos se deteriorarán con una carga en el servidor.
he escrito mi solución como una página Web en .Net. myvrad.com/boggle
Estoy usando el diccionario de referencia en la pregunta original.
Las letras no son reutilizados en una palabra. Sólo palabras 3 caracteres o más se encuentran.
Estoy usando una tabla hash de todos los prefijos y palabras de palabras únicas en lugar de un trie. No sabía acerca de trie así que aprendí algo allí. La idea de crear una lista de prefijos de palabras, además de las palabras completas es lo que finalmente consiguió mis tiempos a un número respetable.
Leer los comentarios de código para obtener detalles adicionales.
Aquí está el código:
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
Tan pronto como vi el planteamiento del problema, pensé "Trie". Pero ya que varios otros carteles realizados aplicación de este enfoque, busqué otro enfoque sólo para ser diferente. Por desgracia, el enfoque Trie tiene un mejor rendimiento. Corrí solución Perl de Kent en mi máquina y tardó 0.31 segundos para correr, después de adaptarla a usar mi archivo de diccionario. Mi propia aplicación requiere Perl 0.54 segundos para correr.
Esta fue mi enfoque:
-
Crear un hash de transición para modelar las transiciones legales.
-
Iterar a través de todos los 16 ^ 3 posibles tres combinaciones de letras.
- En el bucle, excluir transiciones ilegales y repetir las visitas a la misma plaza. Formar todas las secuencias de 3 letras legales y almacenarlos en un hash.
-
A continuación, recorrer todas las palabras del diccionario.
- Excluir palabras que son demasiado largo o corto
- Slide una ventana de 3 letras a través de cada palabra y ver si está entre los combos de 3 letras desde el paso 2. Excluir palabras que fracasan. Esto elimina la mayoría de los no partidos.
- Si todavía no se elimina, utilice un algoritmo recursivo para ver si la palabra se puede formar haciendo caminos a través del rompecabezas. (Esta parte es lenta, pero con poca frecuencia llamada.)
-
Imprime las palabras que encontré.
He intentado secuencias de 3 letras y de 4 letras, pero las secuencias de 4 letras frenado el programa de abajo.
En mi código, utilice / usr / share / dict / words para mi diccionario. Viene de serie en muchos sistemas Unix y MAC OS X. Se puede utilizar otro archivo si lo desea. Para descifrar un puzzle diferente, basta con cambiar la variable @puzzle. Esto sería fácil de adaptar para matrices más grandes. Sólo se necesita cambiar el hash% y transiciones% legalTransitions hash.
La fuerza de esta solución es que el código es corto, y las estructuras de datos simple.
Este es el código Perl (que utiliza demasiadas variables globales, lo sé):
#!/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.
}
Sé que soy super tarde pero hice uno de estos hace un tiempo en PHP - sólo por diversión también ...
http://www.lostsockdesign.com.au/ caja de arena / Boggle / index.php? = letras fxieamloewbxastu Encontrado 75 palabras (133 pts) en 0.90108 segundos
F.........X..I..............E...............
A......................................M..............................L............................O...............................
E....................W............................B..........................X
A..................S..................................................T.................U....
da alguna indicación de lo que el programa está haciendo realidad - cada letra es donde empieza mirando a través de los patrones mientras que cada uno ''. muestra un camino que se ha tratado de tomar. Cuanto más ''. no se cuanto más se ha buscado.
Quiero saber si desea que el código ... es una mezcla horrible de la PHP y HTML que nunca iba a ver la luz del día, así que no me atrevo a publicar aquí: P
Me pasé 3 meses trabajando en una solución al 10 mejor punto densa 5x5 problema tableros Boggle.
El problema ya está resuelto y se presentarán con la divulgación completa en 5 páginas web. Por favor, póngase en contacto conmigo con preguntas.
El algoritmo de análisis de placa utiliza una pila explícita a pseudo-recursivamente atravesar las casillas del tablero a través de un Dirigido acíclicos Palabra Gráfico con información directa niño, y un mecanismo de seguimiento de marca de tiempo. Esto puede muy bien ser la mayor estructura de datos léxico avanzado del mundo.
El esquema evalúa cerca de 10.000 muy buenas tablas por segundo en una de cuatro núcleos. (9500 + puntos)
Página Web de Padres:
DeepSearch.c - http://www.pathcom.com/~vadco/deep. html
Componentes Web Páginas:
óptima Marcador - http://www.pathcom.com/~vadco/binary.html
Avanzado Lexicon Estructura - http://www.pathcom.com/~vadco/adtdawg. html
Junta algoritmo de análisis - http://www.pathcom.com/~vadco/guns. html
Procesamiento por lotes paralelo - http://www.pathcom.com/~vadco/parallel. html
- Este amplio conjunto de obra sólo será de interés para una persona que exige lo mejor.
¿Su algoritmo de búsqueda disminuir continuamente la lista de palabras que su búsqueda continúa?
Por ejemplo, en la búsqueda anterior sólo hay 13 cartas que sus palabras pueden comenzar con (reduciendo efectivamente a la mitad de muchas cartas de partida).
A medida que agrega más permutaciones de letras que disminuiría aún más los conjuntos de palabras disponibles disminuyendo la búsqueda necesaria.
Yo empezaría allí.
tendría que prestar más atención a una solución completa, sino como una optimización de la mano, me pregunto si podría valer la pena pre-cálculo de una tabla de frecuencias de digramas y trigramas (de 2 y 3 combinaciones de letras) basada en todas las palabras del diccionario, y usar esto para dar prioridad a su búsqueda. Me gustaría ir con las letras iniciales de las palabras. Así que si su diccionario contiene las palabras "India", "agua", "extremo", y "extraordinario", entonces su pre-computados tabla podría ser:
'IN': 1
'WA': 1
'EX': 2
A continuación, busque estos digramas en el orden de lo común (EX primero, a continuación, WA / EN)
En primer lugar, leer cómo uno de los diseñadores del lenguaje C # resuelto un problema relacionado: http: //blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx .
Al igual que él, se puede comenzar con un diccionario y las palabras canonacalize mediante la creación de un diccionario de una serie de letras por orden alfabético a una lista de palabras que se pueden deletrear de esas cartas.
A continuación, se inicia la creación de las posibles palabras de la pizarra y mirando hacia arriba. Sospecho que lo llevará muy lejos, pero sin duda hay más trucos que pueden acelerar las cosas.
sugiero hacer un árbol de cartas basado en palabras. El árbol se compone de carta estructuras, como esto:
letter: char
isWord: boolean
A continuación, se construye el árbol, con cada profundidad de la adición de una nueva letra. En otras palabras, en el primer nivel que habría alfabeto; a continuación de cada uno de esos árboles, no habría otro otro 26 entradas, y así sucesivamente, hasta haber escrito todas las palabras. Colgar en este árbol analizada, y que va a hacer todas las respuestas posibles más rápido a mirar hacia arriba.
Con este analiza el árbol, se pueden encontrar muy rápidamente soluciones. Aquí está el pseudo-código:
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.
Esto podría ser acelerado con un poco de programación dinámica. Por ejemplo, en la muestra, los dos 'A son ambos lado de una 'E' y 'W', que (desde el punto que los golpean en) serían idénticos. No tengo suficiente tiempo para escribir realmente el código para esto, pero creo que se puede recoger la idea.
Además, estoy seguro de que encontrará otras soluciones si Google de "Boggle solucionador".
Sólo por diversión, he implementado una en bash. No es muy rápido, pero razonable.
hilarante. Casi me envió la misma pregunta hace unos días debido a la misma maldito juego! Sin embargo no lo hice porque justo buscado en Google de Boggle solucionador pitón y tiene todas las respuestas que pueda desear.
Me doy cuenta ha llegado el momento de esta cuestión y se ha ido, pero ya que estaba trabajando en un solucionador de mí mismo, y se topó con esto mientras googlear alrededor, pensé que debería publicar una referencia a la mía ya que parece un poco diferente de algunos de los otros.
he elegido para ir con una matriz plana para el tablero de juego, y para hacer cacerías recursivas de cada letra en el tablero, que atraviesa de vecino válido vecino válida, extendiendo la caza si la lista actual de las letras si un prefijo válido en un índice. Al atravesar la noción de la palabra actual lista de índices en la placa, no letras que forman una palabra es. Al comprobar el índice, los índices son traducidos a las letras y la comprobación de hecho.
El índice es un diccionario de fuerza bruta que es un poco como un trie, pero permite realizar consultas Pythonic del índice. Si las palabras 'gato' y 'atender' están en la lista, obtendrá esto en el diccionario:
d = { 'c': ['cat','cater'],
'ca': ['cat','cater'],
'cat': ['cat','cater'],
'cate': ['cater'],
'cater': ['cater'],
}
Así que si el current_word es 'ca' usted sabe que es un prefijo válido porque 'ca' in d devuelve True (por lo siguen el recorrido a bordo). Y si el current_word es 'gato', entonces usted sabe que es una palabra válida, ya que es un prefijo válido y devuelve True 'cat' in d['cat'] también.
Si se sentía como esta permitido por algún código legible que no parece demasiado lento. Como todo el mundo el gasto en este sistema es la lectura / construcción del índice. Resolver el tablero es más o menos ruido.
El código es en http://gist.github.com/268079 . Es intencionadamente ingenuas vertical y con una gran cantidad de comprobación de validez explícita porque quería entender el problema sin crufting arriba con un montón de magia o de la oscuridad.
escribí mi solucionador en C ++. He implementado una estructura de árbol personalizado. No estoy seguro de que se puede considerar un trie pero es similar. Cada nodo tiene 26 sucursales, 1 para cada letra del alfabeto. Recorro las ramas de la junta Boggle en paralelo con las ramas de mi diccionario. Si la rama no existe en el diccionario, dejo de buscar en el tablón de Boggle. Puedo convertir todas las cartas en el tablero para enteros. Así 'A' = 0. Puesto que es sólo matrices, operaciones de búsqueda siempre es O (1). Cada nodo almacena si se completa una palabra y cuántos existen palabras en sus hijos. El árbol se poda como las palabras se encuentran en varias ocasiones para reducir la búsqueda de las mismas palabras. Creo poda es también O (1).
CPU: Pentium SU2700 a 1,3 GHz
RAM: 3 GB
Las cargas diccionario de 178,590 palabras <1 segundo.
Resuelve 100x100 Boggle (boggle.txt) en 4 segundos. ~ 44.000 palabras encontradas.
La solución de un 4x4 Boggle es demasiado rápido para proporcionar un buen punto de referencia. :)
Dada una tabla de Boggle con N filas y M columnas, vamos a suponer lo siguiente:
- N * M es sustancialmente mayor que el número de posibles palabras
- N * M es sustancialmente mayor que la palabra más larga posible
Bajo estos supuestos, la complejidad de esta solución es O (N * M).
Creo que la comparación de los tiempos de ejecución de este un ejemplo bordo de muchas maneras, pero pierde el punto, en aras de la exhaustividad, esta solución se completa en <0,2 segundos en mi MacBook Pro moderna.
Esta solución va a encontrar todos los caminos posibles para cada palabra en el 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}"
Esta solución también da la dirección para buscar en la junta dada
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
Salida:
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 → → ↑ ↘ →
Código:
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)
implementado una solución en OCaml . Se pre-compila un diccionario como un trie, y utiliza de dos letras secuencia frecuencias para eliminar los bordes que nunca podría aparecer en una palabra para acelerar aún más el proceso.
Se resuelve su tablero ejemplo, en 0.35ms (con un 6 ms adicionales de tiempo de puesta en marcha que se relaciona principalmente con la carga del trie en la memoria).
Las soluciones encontraron:
["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"]
Una solución Node.JS JavaScript. Calcula todas las 100 palabras únicas en menos de un segundo, lo que incluye la lectura de archivo de diccionario (MBA 2012).
Salida:
[ "FAM", "TINA" "TUX", "FAE", "ELI", "ELM", "ELB", "TWA", "TWA", "Saw", "AMI", "SWA"," SWA", "AME", "MAR", "coser", "AES", "AWL", "AWE", "MAR", "AWA", "MIX", "mil", "AST", "ASE" "MAX", "MAE", "ESTÓMAGO", "MEA", "AWE", "MES", "AWL", "mentira", "LIM", "AWA", "AES", "pero"," BLO", "es", "WAE", "WEA", "LEI", "Leo", "LDN", "LOX", "MEM", "aceite", "OLM", "WEA", "WAE" , "WAX", "WAF", "MILO", "Medio", "WAME", "TWAS", "TWAE", "EMIL", "WEAM", "Oime", "AXIL", "Oeste"," TWAE", "miembro", "WASE", "WAST", "BLEO", "tonto", "HERVIR", "TRONCO", "CAL", "SAWT", "LIMA", "mesa", "maullido" , "EJE", "FAME", "ASEM", "milla", "AMIL", "SEAX", "Separación", "semi", "nadaba", "AMBO", "AMLI", "axile"," AMBLE", "Swami", "AWEST", "AWEST", "LIMAX", "Limes", "LIMBU", "Limbo", "cuadro largo", "semble", "embolia", "Wamble", "FAMBLE" ]
Código:
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
})))
Así que quería añadir otra manera de resolver este PHP, ya que todo el mundo ama PHP. Hay un poco de refactorización me gustaría hacer, como el uso de un partido regexpression contra el archivo de diccionario, pero en este momento sólo estoy cargar todo el archivo de diccionario en una lista de palabras.
Lo hice usando una idea lista enlazada. Cada nodo tiene un valor de carácter, un valor de ubicación, y un puntero siguiente.
El valor ubicación es cómo descubrí si dos nodos están conectados.
1 2 3 4
11 12 13 14
21 22 23 24
31 32 33 34
Así, utilizando esa rejilla, sé dos nodos están conectados si la ubicación del primer nodo es igual a la segunda nodos ubicación +/- 1 para la misma fila, +/- 9, 10, 11 para la fila de arriba y abajo.
Yo uso recursividad para la búsqueda principal. Se necesita una palabra de la lista de palabras, busca todos los posibles puntos de partida, y luego encuentra de forma recursiva la próxima conexión posible, teniendo en cuenta que no puede ir a un lugar que ya está utilizando (por eso añado $ notInLoc).
De todos modos, sé que necesita un poco de refactorización, y me encantaría escuchar los pensamientos acerca de cómo hacerlo más limpio, pero produce los resultados correctos basado en el archivo de diccionario que estoy usando. Dependiendo del número de vocales y combinaciones en el tablero, se tarda aproximadamente 3 a 6 segundos. Sé que una vez que preg_match los resultados del diccionario, que reducirá significativamente.
<?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);
?>
Yo sé que soy muy tarde en la fiesta, pero he implementado, como un ejercicio de codificación, un solucionador de Boggle en varios lenguajes de programación (C ++, Java, Go, C #, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) y pensé que alguien podría estar interesado en ellos, por lo que dejan enlace aquí: https://github.com/AmokHuginnsson/boggle-solvers
Aquí está la solución El uso de palabras predefinidas en NLTK conjunto de herramientas NLTK tiene nltk.corpus paquete en el que tenemos palabras paquete llamado y contiene más de palabras en inglés 2Lakhs sólo tiene que utilizar todo en su programa.
Una vez que la creación de su matriz de convertirlo en una matriz de caracteres y llevar a cabo este código
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)
Salida:
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
espero que lo consigue.
Aquí está mi aplicación java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java
Trie acumulación tomó las 0 horas, 0 minutos, 1 segundo, 532 milisegundos
Palabra searching tomó las 0 horas, 0 minutos, 0 segundos, 92 milisegundos
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
Nota: He utilizado la matriz diccionario y carácter al principio de este hilo. El código se ejecuta en mi MacBookPro, a continuación encontrará información acerca de la máquina.
Nombre del modelo: MacBook Pro Trial
Identificador del modelo: MacBookPro8,1
Nombre del procesador: Intel Core i5
Velocidad del procesador: 2.3 GHz
Número de procesadores: 1 |
Número total de núcleos: 2
L2 Cache (por base): 256 KB
L3 Caché: 3 MB
Memoria: 4 GB
ROM de arranque Versión: MBP81.0047.B0E
SMC Version (sistema): 1.68f96
He resuelto esto también, con Java. Mi aplicación es de 269 líneas de largo y bastante fácil de usar. En primer lugar es necesario crear una nueva instancia de la clase boggler y luego llamar a la función de resolución con la red como un parámetro. Se tarda unos 100 ms para cargar el diccionario de 50 000 palabras en mi equipo y que encuentra las palabras en unos 10-20 ms. Las palabras encontradas se almacenan en 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;
}
}
He resuelto esto en c. Se tarda alrededor de 48 ms para funcionar en mi máquina (con alrededor del 98% del tiempo dedicado a cargar el diccionario de disco y crear el trie). El diccionario es / usr / share / dict / american-Inglés que tiene 62886 palabras.
He resuelto esto perfectamente y muy rápido. Lo puse en una aplicación para Android. Ver el video en el enlace de juego tienda para verlo en acción.
palabra Trucos es una aplicación que "grietas" cualquier juego de palabras estilo de la matriz. Esta aplicación fue construida para que me ayude a engañar al codificador de la palabra. Puede ser utilizado para la búsqueda de palabras, Ruzzle, palabras, buscador de palabra, palabra grieta, boggle, y más!
Se puede ver aquí https://play.google.com/store/apps/details ? id = com.harris.wordcracker
ver la aplicación en acción en el vídeo https://www.youtube.com/watch?v=DL2974WmNAI
