Chaque modalité produit une liste de mots possibles et les options écrites.

Question

Dernièrement, j'ai été jouer à un jeu sur mon iPhone appelé Scramble. Certains d'entre vous connaissent ce jeu Boggle. Essentiellement, lorsque le jeu commence, vous obtenez une matrice de lettres comme suit:

F X I E
A M L O
E W B X
A S T U

Le but du jeu est de trouver autant de mots que vous le pouvez, qui peut être formé par une chaîne de lettres ensemble. Vous pouvez démarrer avec une lettre, et toutes les lettres qui l'entourent sont jeu juste, et puis une fois que vous passez à la lettre suivante, toutes les lettres qui l'entourent cette lettre est un jeu équitable, à l'exception de toute déjà utilisé des lettres. Ainsi, dans la grille ci-dessus, par exemple, je pourrais venir avec les mots - LOB, TUX, SEA, FAME, etc. Mots doit être d'au moins 3 caractères, et pas plus de NxN personnages, ce qui serait de 16 dans ce jeu, mais peut varier dans certaines implémentations. Alors que ce jeu est amusant et addictif, je suis apparemment pas très bon et j'ai voulu tricher un peu en faire un programme qui me donnerait la meilleure possible des mots (plus le mot est long, plus les points que vous obtenez).

Je suis, malheureusement, pas très bon avec des algorithmes ou de leur efficacité et ainsi de suite. Ma première tentative utilise un dictionnaire comme celui-ci (~2.3 MO) et fait une recherche linéaire d'essayer de faire correspondre les combinaisons avec les entrées d'un dictionnaire. Cela prend un très long temps de trouver les mots possibles, et puisque vous obtenez seulement 2 minutes par tour, il n'est tout simplement pas suffisant.

Je suis curieux de voir si tout Stackoverflowers peuvent venir avec des solutions plus efficaces. Je suis surtout à la recherche de solutions à l'aide de la Big 3 Ps: Python, PHP, Perl, bien que quoi que ce soit avec Java ou C++ est trop cool, car la vitesse est essentielle.

LES SOLUTIONS ACTUELLES:

• Adam Rosenfield, Python, ~20s
• Jean Fouhy, Python, ~3s
• Kent Fredric, Perl, ~1s
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET (lien direct), ~1s
• Paolo Bergantino, PHP (lien direct), ~5s (~2s localement)

BOUNTY:

Je suis l'ajout d'une prime à cette question que ma façon de dire merci à toutes les personnes qui se sont mobilisés avec leurs programmes. Malheureusement je ne peux donner à la accepté de répondre à l'un de vous, donc je vais mesurer qui a la plus forte boggle solveur de 7 jours à partir de maintenant et le prix du gagnant de la bounty.

Bounty attribué. Merci à tous ceux qui ont participé.

Answer 1

Ma réponse fonctionne comme les autres ici, mais je vais poster, car il semble un peu plus rapide que les autres Python solutions, de la création du dictionnaire plus rapide. (J'ai vérifié cette contre Jean Fouhy de la solution). Après l'installation, le temps de résoudre est dans le bruit.

grid = "fxie amlo ewbx astu".split()
nrows, ncols = len(grid), len(grid[0])

# A dictionary word that could be a solution must use only the grid's
# letters and have length >= 3. (With a case-insensitive match.)
import re
alphabet = ''.join(set(''.join(grid)))
bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match

words = set(word.rstrip('\n') for word in open('words') if bogglable(word))
prefixes = set(word[:i] for word in words
               for i in range(2, len(word)+1))

def solve():
    for y, row in enumerate(grid):
        for x, letter in enumerate(row):
            for result in extending(letter, ((x, y),)):
                yield result

def extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield result

def neighbors((x, y)):
    for nx in range(max(0, x-1), min(x+2, ncols)):
        for ny in range(max(0, y-1), min(y+2, nrows)):
            yield (nx, ny)

Exemple d'utilisation:

# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))

Edit: Filtrer les mots de moins de 3 lettres.

Edit 2: j'ai été curieux de savoir pourquoi Kent Fredric Perl solution a été plus rapide; il s'avère que l'utilisation régulière correspondant à une expression au lieu d'un jeu de caractères. Faire de même en Python sur double la vitesse.

Answer 2

La solution la plus rapide que vous allez obtenir impliquera probablement stocker votre dictionnaire dans un trie. Ensuite, créez une file d'attente de triplets (x, y, s), où chaque élément dans la file d'attente correspond à un préfixe s d'un mot qui peut être orthographié dans la grille, se terminant à la position (x, y). Initialiser la file d'attente avec N x N éléments (où N est la taille de votre grille), un élément pour chaque carré de la grille. Ensuite, l'algorithme procède comme suit:

Alors que la file d'attente n'est pas vide:
 Dequeue un triple (x, y, s)
 Pour chaque carré de (x', y') par la lettre c à proximité (x, y):
 Si s+c est un mot, une sortie s+c
 Si s+c est un préfixe d'un mot, d'insérer (x', y', s+c) dans la file d'attente

Si vous stockez votre dictionnaire dans un trie, les essais, si s+c est un mot ou un préfixe d'un mot peut être fait en temps constant (à condition de garder certains de métadonnées supplémentaires dans chaque file d'attente donnée, comme un pointeur vers le nœud courant dans le trie), de sorte que le temps d'exécution de cet algorithme est O(nombre de mots qui peut être orthographié).

[Edit] Voici une implémentation en Python que je viens de codé:

#!/usr/bin/python

class TrieNode:
    def __init__(self, parent, value):
        self.parent = parent
        self.children = [None] * 26
        self.isWord = False
        if parent is not None:
            parent.children[ord(value) - 97] = self

def MakeTrie(dictfile):
    dict = open(dictfile)
    root = TrieNode(None, '')
    for word in dict:
        curNode = root
        for letter in word.lower():
            if 97 <= ord(letter) < 123:
                nextNode = curNode.children[ord(letter) - 97]
                if nextNode is None:
                    nextNode = TrieNode(curNode, letter)
                curNode = nextNode
        curNode.isWord = True
    return root

def BoggleWords(grid, dict):
    rows = len(grid)
    cols = len(grid[0])
    queue = []
    words = []
    for y in range(cols):
        for x in range(rows):
            c = grid[y][x]
            node = dict.children[ord(c) - 97]
            if node is not None:
                queue.append((x, y, c, node))
    while queue:
        x, y, s, node = queue[0]
        del queue[0]
        for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)):
            x2, y2 = x + dx, y + dy
            if 0 <= x2 < cols and 0 <= y2 < rows:
                s2 = s + grid[y2][x2]
                node2 = node.children[ord(grid[y2][x2]) - 97]
                if node2 is not None:
                    if node2.isWord:
                        words.append(s2)
                    queue.append((x2, y2, s2, node2))

    return words

Exemple d'utilisation:

d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))

Sortie:

['fa', 'xi', 'ie', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', 'me', 'lo', 'li', 'oe', 'ox', 'em', 'ea', 'ea', 'es', 'wa', 'nous', 'wa', 'bo', 'bu','', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fées', 'imi', 'eli', 'ormes', 'elb', 'ami', 'ama', 'ame', 'aes', 'awl', 'awa', 'crainte', 'awa', 'mix', 'mim', 'mil', 'mam', 'max', 'mae', 'gueule', 'new', 'mem', 'mes', 'métier', 'lox', 'lei', 'leo', 'mensonge', 'lim', 'huile', 'om', 'brebis', 'eme', 'cire', 'fat', 'wae', 'waw', 'centre', 'n', 'n', 'a', 'waw', 'wae', 'bob', 'blo', 'bub', 'mais', 'ast', 'ase', 'asa', 'awl', 'awa', 'crainte', 'awa', 'aes', 'swa', 'swa', 'coudre', 'mer', 'mer', 'vu', 'ville', 'la baignoire', 'tut', 'twa', 'twa', 'essai', 'tut', 'fama', 'fame', 'ixil', 'imam', 'amli', 'amil', 'ambon', 'aisselle', 'essieu', 'mimi', 'mima', 'mime', 'milo', 'mille', 'mewl', 'mese', 'mesa', 'lolo', 'lobo', 'lima', 'lime', 'membre', 'lile', 'oime', 'oleo', 'olio', 'hautbois', 'coquilles', 'emim', 'emil', 'est', 'facilité', 'wame", de "wawa", "wawa', 'weam', 'ouest', 'wese', 'étais', 'wase', "wawa", de "wawa", "bouillir", 'bolo', 'fût', 'bobo', 'blob', 'bleo', 'bubo', 'asem', 'stub', 'stut', 'nagé', 'semi', 'seme', 'couture', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', 'ilima', 'y', 'axile', 'ouest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax", de "limes", de "limbes", de "limbu', 'obole', 'emesa', 'embox', 'ouest', 'swami', 'famble', 'mimble', 'maxima', 'embolo', 'embole', 'wamble', 'semese', 'ensemble', 'sawbwa', 'sawbwa']

Note: Ce programme n'a pas de sortie 1-lettre des mots, ou un filtre par longueur de mot. C'est facile à ajouter, mais pas vraiment pertinente pour le problème. Il génère également quelques mots à plusieurs reprises si elles peuvent être orthographié de plusieurs façons. Si un mot peut être orthographié de différentes façons (dans le pire des cas: chaque lettre de la grille est la même (par exemple, "A") et un mot comme "aaaaaaaaaa" est dans le dictionnaire), alors le temps d'exécution obtiendrez horriblement exponentielle. Filtrer les doublons et le tri est facile à échéance après l'algorithme est terminé.

Answer 3

Pour un dictionnaire de l'accélération, il y a une transformation générale/processus que vous pouvez faire pour réduire considérablement le dictionnaire des comparaisons à l'avance.

Étant donné que la grille ne contient que 16 caractères, certains d'entre eux en double, vous pouvez considérablement réduire le nombre total de clés dans votre dictionnaire, simplement en filtrant les entrées qui ont inaccessible caractères.

Je pensais que c'était l'optimisation évidente, mais ne voyant personne ne l'a fait, je suis le mentionner.

Il me réduit à partir d'un dictionnaire de plus de 200 000 clés pour seulement 2 000 clés simplement lors de la saisie de passer. Ce à tout le moins réduit la surcharge de la mémoire, et qui ne manquera pas de carte à une augmentation de la vitesse quelque part que la mémoire n'est pas infiniment rapide.

Perl Mise En Œuvre

Mon application est un peu lourd parce que j'ai insisté sur l'importance d'être en mesure de connaître le chemin exact de tous les extraits de la chaîne, et pas seulement la validité qui y est.

J'ai également quelques adaptations qu'il serait théoriquement permettre une grille avec des trous pour la fonction, et les grilles de tailles différentes lignes ( en supposant que vous obtenez le droit d'entrée et il s'aligne en quelque sorte ).

Le début de filtre est de loin le plus important goulot d'étranglement dans mon application, comme suspect plus tôt, en commentant cette ligne gonfle de 1,5 s à 7,5 s.

Lors de l'exécution, il apparaît à penser que tous les chiffres sont ses propres mots, mais je suis assez sûr que c'est dû à la façon dont le fichier de dictionnaire des œuvres.

C'est un peu gonflé, mais au moins j'ai la réutilisation de l'Arbre::Trie sur le cpan

Certains de il a été inspiré en partie par les implémentations existantes, certains de ce que j'avais à l'esprit déjà.

Les Critiques constructives et les moyens qu'il pourrait être amélioré bienvenue ( /me note qu'il n'a jamais cherché CPAN pour un boggle solveur, mais ce n'était plus de plaisir à travailler )

mise à jour pour les nouveaux critères

#!/usr/bin/perl 

use strict;
use warnings;

{

  # this package manages a given path through the grid.
  # Its an array of matrix-nodes in-order with
  # Convenience functions for pretty-printing the paths
  # and for extending paths as new paths.

  # Usage:
  # my $p = Prefix->new(path=>[ $startnode ]);
  # my $c = $p->child( $extensionNode );
  # print $c->current_word ;

  package Prefix;
  use Moose;

  has path => (
      isa     => 'ArrayRef[MatrixNode]',
      is      => 'rw',
      default => sub { [] },
  );
  has current_word => (
      isa        => 'Str',
      is         => 'rw',
      lazy_build => 1,
  );

  # Create a clone of this object
  # with a longer path

  # $o->child( $successive-node-on-graph );

  sub child {
      my $self    = shift;
      my $newNode = shift;
      my $f       = Prefix->new();

      # Have to do this manually or other recorded paths get modified
      push @{ $f->{path} }, @{ $self->{path} }, $newNode;
      return $f;
  }

  # Traverses $o->path left-to-right to get the string it represents.

  sub _build_current_word {
      my $self = shift;
      return join q{}, map { $_->{value} } @{ $self->{path} };
  }

  # Returns  the rightmost node on this path

  sub tail {
      my $self = shift;
      return $self->{path}->[-1];
  }

  # pretty-format $o->path

  sub pp_path {
      my $self = shift;
      my @path =
        map { '[' . $_->{x_position} . ',' . $_->{y_position} . ']' }
        @{ $self->{path} };
      return "[" . join( ",", @path ) . "]";
  }

  # pretty-format $o
  sub pp {
      my $self = shift;
      return $self->current_word . ' => ' . $self->pp_path;
  }

  __PACKAGE__->meta->make_immutable;
}

{

  # Basic package for tracking node data
  # without having to look on the grid.
  # I could have just used an array or a hash, but that got ugly.

# Once the matrix is up and running it doesn't really care so much about rows/columns,
# Its just a sea of points and each point has adjacent points.
# Relative positioning is only really useful to map it back to userspace

  package MatrixNode;
  use Moose;

  has x_position => ( isa => 'Int', is => 'rw', required => 1 );
  has y_position => ( isa => 'Int', is => 'rw', required => 1 );
  has value      => ( isa => 'Str', is => 'rw', required => 1 );
  has siblings   => (
      isa     => 'ArrayRef[MatrixNode]',
      is      => 'rw',
      default => sub { [] }
  );

# Its not implicitly uni-directional joins. It would be more effient in therory
# to make the link go both ways at the same time, but thats too hard to program around.
# and besides, this isn't slow enough to bother caring about.

  sub add_sibling {
      my $self    = shift;
      my $sibling = shift;
      push @{ $self->siblings }, $sibling;
  }

  # Convenience method to derive a path starting at this node

  sub to_path {
      my $self = shift;
      return Prefix->new( path => [$self] );
  }
  __PACKAGE__->meta->make_immutable;

}

{

  package Matrix;
  use Moose;

  has rows => (
      isa     => 'ArrayRef',
      is      => 'rw',
      default => sub { [] },
  );

  has regex => (
      isa        => 'Regexp',
      is         => 'rw',
      lazy_build => 1,
  );

  has cells => (
      isa        => 'ArrayRef',
      is         => 'rw',
      lazy_build => 1,
  );

  sub add_row {
      my $self = shift;
      push @{ $self->rows }, [@_];
  }

  # Most of these functions from here down are just builder functions,
  # or utilities to help build things.
  # Some just broken out to make it easier for me to process.
  # All thats really useful is add_row
  # The rest will generally be computed, stored, and ready to go
  # from ->cells by the time either ->cells or ->regex are called.

  # traverse all cells and make a regex that covers them.
  sub _build_regex {
      my $self  = shift;
      my $chars = q{};
      for my $cell ( @{ $self->cells } ) {
          $chars .= $cell->value();
      }
      $chars = "[^$chars]";
      return qr/$chars/i;
  }

  # convert a plain cell ( ie: [x][y] = 0 )
  # to an intelligent cell ie: [x][y] = object( x, y )
  # we only really keep them in this format temporarily
  # so we can go through and tie in neighbouring information.
  # after the neigbouring is done, the grid should be considered inoperative.

  sub _convert {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my $v    = $self->_read( $x, $y );
      my $n    = MatrixNode->new(
          x_position => $x,
          y_position => $y,
          value      => $v,
      );
      $self->_write( $x, $y, $n );
      return $n;
  }

# go through the rows/collums presently available and freeze them into objects.

  sub _build_cells {
      my $self = shift;
      my @out  = ();
      my @rows = @{ $self->{rows} };
      for my $x ( 0 .. $#rows ) {
          next unless defined $self->{rows}->[$x];
          my @col = @{ $self->{rows}->[$x] };
          for my $y ( 0 .. $#col ) {
              next unless defined $self->{rows}->[$x]->[$y];
              push @out, $self->_convert( $x, $y );
          }
      }
      for my $c (@out) {
          for my $n ( $self->_neighbours( $c->x_position, $c->y_position ) ) {
              $c->add_sibling( $self->{rows}->[ $n->[0] ]->[ $n->[1] ] );
          }
      }
      return \@out;
  }

  # given x,y , return array of points that refer to valid neighbours.
  sub _neighbours {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my @out  = ();
      for my $sx ( -1, 0, 1 ) {
          next if $sx + $x < 0;
          next if not defined $self->{rows}->[ $sx + $x ];
          for my $sy ( -1, 0, 1 ) {
              next if $sx == 0 && $sy == 0;
              next if $sy + $y < 0;
              next if not defined $self->{rows}->[ $sx + $x ]->[ $sy + $y ];
              push @out, [ $sx + $x, $sy + $y ];
          }
      }
      return @out;
  }

  sub _has_row {
      my $self = shift;
      my $x    = shift;
      return defined $self->{rows}->[$x];
  }

  sub _has_cell {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      return defined $self->{rows}->[$x]->[$y];
  }

  sub _read {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      return $self->{rows}->[$x]->[$y];
  }

  sub _write {
      my $self = shift;
      my $x    = shift;
      my $y    = shift;
      my $v    = shift;
      $self->{rows}->[$x]->[$y] = $v;
      return $v;
  }

  __PACKAGE__->meta->make_immutable;
}

use Tree::Trie;

sub readDict {
  my $fn = shift;
  my $re = shift;
  my $d  = Tree::Trie->new();

  # Dictionary Loading
  open my $fh, '<', $fn;
  while ( my $line = <$fh> ) {
      chomp($line);

 # Commenting the next line makes it go from 1.5 seconds to 7.5 seconds. EPIC.
      next if $line =~ $re;    # Early Filter
      $d->add( uc($line) );
  }
  return $d;
}

sub traverseGraph {
  my $d     = shift;
  my $m     = shift;
  my $min   = shift;
  my $max   = shift;
  my @words = ();

  # Inject all grid nodes into the processing queue.

  my @queue =
    grep { $d->lookup( $_->current_word ) }
    map  { $_->to_path } @{ $m->cells };

  while (@queue) {
      my $item = shift @queue;

      # put the dictionary into "exact match" mode.

      $d->deepsearch('exact');

      my $cword = $item->current_word;
      my $l     = length($cword);

      if ( $l >= $min && $d->lookup($cword) ) {
          push @words,
            $item;    # push current path into "words" if it exactly matches.
      }
      next if $l > $max;

      # put the dictionary into "is-a-prefix" mode.
      $d->deepsearch('boolean');

    siblingloop: foreach my $sibling ( @{ $item->tail->siblings } ) {
          foreach my $visited ( @{ $item->{path} } ) {
              next siblingloop if $sibling == $visited;
          }

          # given path y , iterate for all its end points
          my $subpath = $item->child($sibling);

          # create a new path for each end-point
          if ( $d->lookup( $subpath->current_word ) ) {

             # if the new path is a prefix, add it to the bottom of the queue.
              push @queue, $subpath;
          }
      }
  }
  return \@words;
}

sub setup_predetermined { 
  my $m = shift; 
  my $gameNo = shift;
  if( $gameNo == 0 ){
      $m->add_row(qw( F X I E ));
      $m->add_row(qw( A M L O ));
      $m->add_row(qw( E W B X ));
      $m->add_row(qw( A S T U ));
      return $m;
  }
  if( $gameNo == 1 ){
      $m->add_row(qw( D G H I ));
      $m->add_row(qw( K L P S ));
      $m->add_row(qw( Y E U T ));
      $m->add_row(qw( E O R N ));
      return $m;
  }
}
sub setup_random { 
  my $m = shift; 
  my $seed = shift;
  srand $seed;
  my @letters = 'A' .. 'Z' ; 
  for( 1 .. 4 ){ 
      my @r = ();
      for( 1 .. 4 ){
          push @r , $letters[int(rand(25))];
      }
      $m->add_row( @r );
  }
}

# Here is where the real work starts.

my $m = Matrix->new();
setup_predetermined( $m, 0 );
#setup_random( $m, 5 );

my $d = readDict( 'dict.txt', $m->regex );
my $c = scalar @{ $m->cells };    # get the max, as per spec

print join ",\n", map { $_->pp } @{
  traverseGraph( $d, $m, 3, $c ) ;
};

Arch/exécution d'infos pour la comparaison:

model name      : Intel(R) Core(TM)2 Duo CPU     T9300  @ 2.50GHz
cache size      : 6144 KB
Memory usage summary: heap total: 77057577, heap peak: 11446200, stack peak: 26448
       total calls   total memory   failed calls
 malloc|     947212       68763684              0
realloc|      11191        1045641              0  (nomove:9063, dec:4731, free:0)
 calloc|     121001        7248252              0
   free|     973159       65854762

Histogram for block sizes:
  0-15         392633  36% ==================================================
 16-31          43530   4% =====
 32-47          50048   4% ======
 48-63          70701   6% =========
 64-79          18831   1% ==
 80-95          19271   1% ==
 96-111        238398  22% ==============================
112-127          3007  <1% 
128-143        236727  21% ==============================

Plus Mumblings sur cette Regex Optimisation

La regex optimisation que j'utilise est inutile pour le multi-résoudre les dictionnaires, et pour le multi-résoudre, vous aurez besoin d'un dictionnaire complet, pas un pré-paré.

Cependant, qui dit, pour un hors résout, c'est vraiment rapide. ( Expression rationnelle Perl sont en C! :) )

Voici certaines des variables du code des ajouts:

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 non filtré filtré
non filtrée 8.16 -- -94%
filtré 0.464 1658% --

_{ps: 8.16 * 200 = 27 minutes.}

Answer 4

Vous pourriez diviser le problème en deux parties:

1. Une sorte d'algorithme de recherche qui va énumérer possible des chaînes dans la grille.
2. Une façon de tester si une chaîne est un mot valide.

Idéalement, (2) devrait également inclure un moyen de tester si une chaîne est un préfixe d'un mot valide – ce qui vous permettra de nettoyer votre recherche et d'enregistrer tout un tas de temps.

Adam Rosenfield de Trie est une solution de (2). Il est élégant et probablement ce que votre algorithmes spécialiste préférez, mais avec les langues modernes et les ordinateurs modernes, nous pouvons être un peu plus. Aussi, comme Kent suggère, nous pouvons réduire notre dictionnaire de la taille en supprimant les mots qui ont des lettres n'est pas présent dans la grille. Voici quelques python:

def make_lookups(grid, fn='dict.txt'):
    # Make set of valid characters.
    chars = set()
    for word in grid:
        chars.update(word)

    words = set(x.strip() for x in open(fn) if set(x.strip()) <= chars)
    prefixes = set()
    for w in words:
        for i in range(len(w)+1):
            prefixes.add(w[:i])

    return words, prefixes

Wow; constante de temps préfixe de test. Il faut quelques secondes pour charger le dictionnaire est lié, mais seulement un couple :-) ( words <= prefixes)

Maintenant, pour la partie (1), je suis enclin à penser en termes de graphes. Donc je vais construire un dictionnaire qui ressemble à quelque chose comme ceci:

graph = { (x, y):set([(x0,y0), (x1,y1), (x2,y2)]), }

c'est à dire graph[(x, y)] est l'ensemble des coordonnées que l'on peut atteindre à partir de la position (x, y). Je vais également ajouter un mannequin nœud None ce qui va se connecter à tout.

D'un bâtiment, il est un peu maladroit, parce qu'il y a 8 positions possibles et que vous avez à faire la vérification des limites. Voici quelques-conséquence-maladroit code python:

def make_graph(grid):
    root = None
    graph = { root:set() }
    chardict = { root:'' }

    for i, row in enumerate(grid):
        for j, char in enumerate(row):
            chardict[(i, j)] = char
            node = (i, j)
            children = set()
            graph[node] = children
            graph[root].add(node)
            add_children(node, children, grid)

    return graph, chardict

def add_children(node, children, grid):
    x0, y0 = node
    for i in [-1,0,1]:
        x = x0 + i
        if not (0 <= x < len(grid)):
            continue
        for j in [-1,0,1]:
            y = y0 + j
            if not (0 <= y < len(grid[0])) or (i == j == 0):
                continue

            children.add((x,y))

Ce code a également construit un dictionnaire de mappage (x,y) pour le caractère correspondant. Cela me permet de transformer une liste de positions en un mot:

def to_word(chardict, pos_list):
    return ''.join(chardict[x] for x in pos_list)

Enfin, nous procédons à une profondeur d'abord de recherche. La procédure de base est:

1. La recherche arrive à un nœud particulier.
2. Vérifier si le chemin d'accès jusqu'à présent pourrait être une partie d'un mot. Si non, ne pas explorer cette branche.
3. Vérifier si le chemin d'accès jusqu'à présent est un mot. Si oui, l'ajouter à la liste des résultats.
4. Explorer tous les enfants ne fait pas partie du chemin jusqu'à présent.

Python:

def find_words(graph, chardict, position, prefix, results, words, prefixes):
    """ Arguments:
      graph :: mapping (x,y) to set of reachable positions
      chardict :: mapping (x,y) to character
      position :: current position (x,y) -- equals prefix[-1]
      prefix :: list of positions in current string
      results :: set of words found
      words :: set of valid words in the dictionary
      prefixes :: set of valid words or prefixes thereof
    """
    word = to_word(chardict, prefix)

    if word not in prefixes:
        return

    if word in words:
        results.add(word)

    for child in graph[position]:
        if child not in prefix:
            find_words(graph, chardict, child, prefix+[child], results, words, prefixes)

Exécutez le code comme:

grid = ['fxie', 'amlo', 'ewbx', 'astu']
g, c = make_graph(grid)
w, p = make_lookups(grid)
res = set()
find_words(g, c, None, [], res, w, p)

et inspecter res pour voir les réponses. Voici une liste des mots trouvés pour votre exemple, triés par taille:

 ['a', 'b', 'e', 'f', 'i', 'l', 'm', 'o', 's', 't',
 'u', 'w', 'x', 'ae', 'am', 'as', 'aw', 'ax', 'bo',
 'bu', 'ea', 'el', 'em', 'es', 'fa', 'ie', 'io', 'li',
 'lo', 'ma', 'me', 'mi', 'oe', 'ox', 'sa', 'se', 'st',
 'tu', 'ut', 'wa', 'we', 'xi', 'aes', 'ame', 'ami',
 'ase', 'ast', 'awa', 'awe', 'awl', 'blo', 'but', 'elb',
 'elm', 'fae', 'fam', 'lei', 'lie', 'lim', 'lob', 'lox',
 'mae', 'maw', 'mew', 'mil', 'mix', 'oil', 'olm', 'saw',
 'sea', 'sew', 'swa', 'tub', 'tux', 'twa', 'wae', 'was',
 'wax', 'wem', 'ambo', 'amil', 'amli', 'asem', 'axil',
 'axle', 'bleo', 'boil', 'bole', 'east', 'fame', 'limb',
 'lime', 'mesa', 'mewl', 'mile', 'milo', 'oime', 'sawt',
 'seam', 'seax', 'semi', 'stub', 'swam', 'twae', 'twas',
 'wame', 'wase', 'wast', 'weam', 'west', 'amble', 'awest',
 'axile', 'embox', 'limbo', 'limes', 'swami', 'embole',
 'famble', 'semble', 'wamble']

Le code prend (littéralement) un couple de secondes pour charger le dictionnaire, mais le reste est à l'instant sur ma machine.

Answer 5

Ma tentative en Java. Il faut environ 2 s pour lire le fichier et de construire trie, et autour de 50 ms pour résoudre le puzzle. J'ai utilisé le dictionnaire liée à la question (il a quelques mots que je ne connaissais pas exister en anglais telles que les fae, ima)

0 [main] INFO gineer.bogglesolver.util.Util  - Reading the dictionary
2234 [main] INFO gineer.bogglesolver.util.Util  - Finish reading the dictionary
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAM
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAME
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAMBLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: FAE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: IMA
2234 [main] INFO gineer.bogglesolver.Solver  - Found: ELI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: ELM
2234 [main] INFO gineer.bogglesolver.Solver  - Found: ELB
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXIL
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXILE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AXLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMIL
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMLI
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AME
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMBLE
2234 [main] INFO gineer.bogglesolver.Solver  - Found: AMBO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MIX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MILE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MILO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MAW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MEW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MEWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MESA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: MWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIME
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMBO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LIMBU
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LEI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LEO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LOB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: LOX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OIME
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: OLM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMBOLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EMBOX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: EAST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAF
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAME
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAMBLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAS
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WASE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: WAST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BLEO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BLO
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BOIL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BOLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: BUT
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AES
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWL
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AWEST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: ASE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: ASEM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: AST
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEAX
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEMI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEMBLE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SEA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWAM
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWAMI
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SAW
2250 [main] INFO gineer.bogglesolver.Solver  - Found: SAWT
2250 [main] INFO gineer.bogglesolver.Solver  - Found: STU
2250 [main] INFO gineer.bogglesolver.Solver  - Found: STUB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWA
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAE
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TWAS
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TUB
2250 [main] INFO gineer.bogglesolver.Solver  - Found: TUX

Le code Source est composée de 6 classes. Je vais les poster ci-dessous (si ce n'est pas le droit de pratique sur StackOverflow, s'il vous plaît dites-moi).

gineer.bogglesolver.Principal

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.Le solveur

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.Nœud

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.Constantes

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;
    }
}