Cum de a găsi lista de cuvinte posibile dintr-o matrice de litere [Boggle Solver] (Programare, Algoritm, Puzzle, Boggle)

În ultima vreme am jucat un joc pe iPhone-ul meu numit Scramble. Unii dintre voi poate cunoașteți acest joc ca fiind Boggle. În esență, atunci când jocul începe, primești o matrice de litere, cam așa:

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

Scopul jocului este de a găsi cât mai multe cuvinte care pot fi formate prin înlănțuirea literelor. Puteți începe cu orice literă, iar toate literele care o înconjoară sunt un joc corect, iar apoi, odată ce treceți la următoarea literă, toate literele care o înconjoară sunt un joc corect, cu excepția literelor folosite anterior.. Astfel, în grila de mai sus, de exemplu, aș putea obține cuvintele LOB, , TUX, , SEA, , FAME, , etc. Cuvintele trebuie să aibă cel puțin 3 caractere și nu mai mult de NxN caractere, ceea ce ar fi 16 în acest joc, dar poate varia în unele implementări. Deși acest joc este distractiv și creează dependență, se pare că nu sunt foarte bun la el și am vrut să trișez puțin făcând un program care să-mi ofere cele mai bune cuvinte posibile (cu cât cuvântul este mai lung, cu atât mai multe puncte primești).


(sursă: (sursă: boggled.org)

Din păcate, nu mă pricep foarte bine la algoritmi sau la eficiența lor și așa mai departe. Prima mea încercare folosește un dicționar cum ar fi acesta (~2.3MB) și face o căutare liniară încercând să potrivească combinațiile cu intrările din dicționar. Acest lucru durează o foarte mult timp pentru a găsi cuvintele posibile și, având în vedere că aveți la dispoziție doar 2 minute pe rundă, pur și simplu nu este adecvat.

Sunt interesat să văd dacă vreun Stackoverflower poate veni cu soluții mai eficiente. Caut în principal soluții care folosesc cei 3 mari P: Python, PHP și Perl, deși orice soluție cu Java sau C++ este de asemenea grozavă, deoarece viteza este esențială.

SOLUȚII ACTUALE:

  • Adam Rosenfield, Python, ~20s
  • John Fouhy, Python, ~3s
  • Kent Fredric, Perl, ~1s
  • Darius Bacon, Python, ~1s
  • rvarcher, VB.NET (link live), , ~1s
  • Paolo Bergantino, PHP (link live), ~5s (~2s local)

Comentarii

    18

  • solicitare de caracteristici MOAR PUZZLES –  > Por Kent Fredric.
  • În ceea ce privește timpii: în soluția mea, practic tot timpul este petrecut pentru a construi trie. Odată ce trie este construit, poate fi reutilizat de mai multe ori. Dacă se rezolvă un singur puzzle, ar fi mai eficient să se utilizeze o structură de date mai simplă (cum ar fi un set de toate cuvintele și toate prefixoanele). –  > Por Adam Rosenfield.
  • De asemenea, soluția lui Adam are un dicționar mai mare, fapt evidențiat de numărul de cuvinte mai lungi pe care le folosește soluția sa. Toate ar trebui să fie testate pe baza unui dicționar comun. –  > Por Rich Bradshaw.
  • Cred că nimeni nu joacă prea mult Boggle? „Qu” este o singură „literă” și nu sunt sigur că multe dintre soluții au reținut acest mic detaliu. Se pare că unele dintre ele ți-ar permite să folosești „u” independent, printre alte probleme. –  > Por Qsario.
  • Am avut recent această întrebare la un interviu și m-am blocat frumos în detalii. Am tratat-o ca pe o problemă de graf, ceea ce este bine, dar soluțiile de aici folosesc mult mai puțin spațiu. Acum îmi codific propria soluție. Felicitări tuturor celor care au contribuit! –  > Por Peter Friend.
35 răspunsuri
Darius Bacon

Răspunsul meu funcționează ca și celelalte de aici, dar îl postez pentru că pare un pic mai rapid decât celelalte soluții Python, de la configurarea mai rapidă a dicționarului. (Am verificat acest lucru în comparație cu soluția lui John Fouhy.) După configurare, timpul de rezolvare este mai jos în zgomot.

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('
') 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)

Exemplu de utilizare:

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

Editați: Filtrează cuvintele cu o lungime mai mică de 3 litere.

Editare 2: Am fost curios de ce soluția Perl a lui Kent Fredric a fost mai rapidă; se pare că folosește potrivirea expresiilor regulate în loc de un set de caractere. Făcând același lucru în Python aproximativ dublează viteza.

Comentarii

  • Programul îmi dă doar 1 cuvânt. De ce? –  > Por Paolo Bergantino.
  • Nu am vrut să mă înec în output. Vedeți comentariul de la sfârșitul paginii. –  > Por Darius Bacon.
  • Sau obțineți toate cuvintele fără căi: print ‘ ‘.join(sorted(set(set(word for (word, path) in solve()))) –  > Por Darius Bacon.
  • O mare parte din timp se petrece doar analizând dicționarul. L-am pre-parazitat într-un fișier „wordlines.py” care este doar o listă în care fiecare cuvânt este un element. Deoarece este un fișier .py, acesta va fi transformat într-un fișier .pyc. Așa că am făcut un import al acestuia în loc de read().splitlines(). Cu asta, pe calculatorul meu, rezolv problema în aproximativ o zecime de secundă. –  > Por Sean Reifschneider.
  • @shellscape, este un cod Python 2. Python 3 a renunțat la capacitatea de a deconstrui argumente, cum ar fi def neighbors((x, y)) (fără rost, din câte văd eu). De asemenea, este nevoie de paranteze în jurul argumentului pentru a print. –  > Por Darius Bacon.
Adam Rosenfield

Cea mai rapidă soluție pe care o veți obține va implica, probabil, stocarea dicționarului într-un fișier trie. Apoi, creați o coadă de triplete (x, , y, , s), unde fiecare element din coada de așteptare corespunde unui prefix s al unui cuvânt care poate fi ortografiat în grilă, care se termină în locația (x, , y). Se inițializează coada cu N x N elemente (unde N este dimensiunea grilei), câte un element pentru fiecare pătrat din grilă. Apoi, algoritmul se desfășoară după cum urmează:

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

Dacă stocați dicționarul într-o trie, testați dacă s+c este un cuvânt sau un prefix al unui cuvânt se poate face în timp constant (cu condiția să păstrați și unele metadate suplimentare în fiecare dată din coada de așteptare, cum ar fi un pointer la nodul curent din trie), astfel încât timpul de execuție al acestui algoritm este O(numărul de cuvinte care pot fi silabisite).

[Editare] Iată o implementare în Python pe care tocmai am codat-o:

#!/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

Exemplu de utilizare:

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

Ieșire:

[‘fa’, ‘fa’, ‘xi’, ‘ie’, ‘io’, ‘el’, ‘am’, ‘ax’, ‘ae’, ‘aw’, ‘mi’, ‘ma’, ‘me’, ‘lo’, ‘li’, ‘oe’, ‘ox’, ‘em’, ‘ea’, ‘ea’, ‘es’, ‘wa’, ‘we’, ‘wa’, ‘bo’, ‘bu’, ‘as’, ‘aw’, ‘ae’, ‘st’, ‘se’, „sa”, „tu”, „ut”, „fam”, „fae”, „imi”, „eli”, „elm”, „elb”, „ami”, „ama”, „ame”, „aes”, „awl”, „awa”, „awe”, „awa”, „mix”, „mim”, „mil”, „mil”, „mam”, „max”, „mae”, „maw”, „mew”, „mem”, „mes”, „lob”, „lox”, „lei”, „leo”, „lie”, „lim”, „oil”, „olm”, „ewe”, „eme”, „wax”, „waf”, „wae”, „waw”, „wem”, „wea”, „wea”, „was”, „waw”, „wae”, „bob”, „blo”, „bub”, „but”, „ast”, „ase”, „asa”, „awl”, „awa”, „awe”, „awa”, „aes”, „swa”, „swa”, „sew”, „sea”, „sea”, „saw”, „tux”, „tub”, „tut”, „twa”, „twa”, „twa”, „tst”, „utu”, „fama”, „fame”, „ixil”, „imam”, „amli”, „amil”, „ambo”, „axil”, „axle”, „mimi”, „mima”, „mime”, „milo”, „mile”, „mewl”, „mese”, „mesa”, „mesa”, „lolo”, „lobo”, „lima”, „lime”, „limb”, „lile”, „lile”, „oime”, „oleo”, „olio”, „oboe”, „obol”, „emim”, „emil”, „east”, „ease”, „wame”, „wawa”, „wawa”, „weam”, „west”, „wese”, „wast”, „wase”, „wase”, „wawa”, „wawa”, „boil”, „bolo”, „bole”, „bobo”, „blob”, „bleo”, „bubo”, „asem”, „stub”, ‘stut’, ‘swam’, ‘semi’, ‘seme’, ‘seam’, ‘seax’, ‘sasa’, ‘sawt’, ‘tutu’, ‘tuts’, ‘twae’, ‘twas’, ‘twae’, ‘ilima’, ‘amble’, ‘axile’, ‘awest’, ‘mamie’, ‘mambo’, ‘maxim’, ‘mease’, ‘mesem’, ‘limax’, ‘limes’, ‘limbo’, ‘limbu’, ‘obole’, ‘emesa’, ‘embox’, ‘awest’, ‘swami’, ‘famble’, ‘mimble’, ‘maxima’, ‘embolo’, ‘embole’, ‘wamble’, ‘semese’, ‘semble’, ‘sawbwa’, ‘sawbwa’].

Note: Acest program nu produce cuvinte de 1 literă și nici nu filtrează în funcție de lungimea cuvântului. Acest lucru este ușor de adăugat, dar nu este cu adevărat relevant pentru problemă. De asemenea, scoate unele cuvinte de mai multe ori dacă pot fi ortografiate în mai multe moduri. Dacă un anumit cuvânt poate fi scris în mai multe moduri diferite (în cel mai rău caz: fiecare literă din grilă este aceeași (de exemplu, „A”) și un cuvânt precum „aaaaaaaaaa” se află în dicționarul dvs.), atunci timpul de execuție va deveni îngrozitor de exponențial. Filtrarea duplicatelor și sortarea sunt banale de realizat după terminarea algoritmului.

Comentarii

  • Ooo. Mă bucur că cineva s-a apucat de treabă. Deși funcționează, nu „ține minte” litera pe care a folosit-o deja și vine cu cuvinte care ar necesita folosirea de două ori a aceleiași litere, ceea ce nu este permis. Cum sunt un idiot, cum aș putea să rezolv asta? –  > Por Paolo Bergantino.
  • Adevărat, nu-și amintește ce litere au fost vizitate, dar acest lucru nu a fost specificat în specificațiile dumneavoastră =). Pentru a remedia acest lucru, ar trebui să adăugați la fiecare dată din coadă o listă cu toate locațiile vizitate și apoi să verificați această listă înainte de a adăuga următorul caracter. –  > Por Adam Rosenfield.
  • Nu, în interiorul BoggleWords(). În loc să stocați un cvadruplet (x, y, s, n), ați stoca un quintuplet (x, y, s, n, l), unde l este lista de (x, y) vizitate până acum. Apoi se verifică fiecare (x2, y2) în funcție de l și se acceptă numai dacă nu se află în l. Apoi se adaugă la noul l. –  > Por Adam Rosenfield.
  • Și eu am făcut asta când m-am săturat să joc Scramble. Cred că soluția recursivă (DFS în loc de BFS) este mai sexy, deoarece poți păstra doar un set de celule active (astfel încât să nu vizitezi aceeași celulă de două ori). Mult mai ordonat decât să păstrezi o grămadă de liste. –  > Por Justin Scheiner.
  • Nu ar trebui să se ajungă la o buclă infinită? Adică, să zicem for (x,y), , un posibil urmăritor este (x+1,y+1). Apoi (x+1,y+1) este introdus în coada de așteptare. Cu toate acestea, (x,y) va fi de asemenea un urmăritor pentru (x+1,y+1), , astfel încât nu va duce la o nesfârșită revenire între ele? –  > Por SexyBeast.

Pentru o accelerare a dicționarului, există o transformare/proces general pe care îl puteți face pentru a reduce foarte mult comparațiile din dicționar înainte de timp.

Având în vedere că grila de mai sus conține doar 16 caractere, unele dintre ele duplicate, puteți reduce foarte mult numărul total de chei din dicționar prin simpla filtrare a intrărilor care au caractere imposibil de atins.

Am crezut că aceasta este o optimizare evidentă, dar văzând că nimeni nu a făcut-o, o menționez.

M-a redus de la un dicționar de 200.000 de chei la doar 2.000 de chei, pur și simplu în timpul trecerii de intrare. Acest lucru reduce cel puțin cheltuielile de memorie, iar acest lucru se va reflecta cu siguranță într-o creștere a vitezei undeva, deoarece memoria nu este infinit de rapidă.

Implementarea Perl

Implementarea mea este un pic mai grea pentru că am acordat importanță faptului că trebuie să pot cunoaște calea exactă a fiecărui șir extras, nu doar validitatea acestuia.

Am, de asemenea, câteva adaptări care, teoretic, ar permite ca o grilă cu găuri să funcționeze și grile cu linii de dimensiuni diferite (presupunând că introduceți datele corect și că acestea se aliniază cumva).

Filtrul timpuriu este de departe cel mai semnificativ semnificativ în aplicația mea, așa cum am bănuit mai devreme, comentând acea linie, aceasta se umflă de la 1,5s la 7,5s.

La execuție, pare să creadă că toate cifrele unice sunt cuvinte valide, dar sunt destul de sigur că acest lucru se datorează modului în care funcționează fișierul dicționar.

Este un pic umflat, dar cel puțin reutilizez Tree::Trie de la cpan

O parte din ea a fost inspirată parțial de implementările existente, iar o parte o aveam deja în minte.

Criticile constructive și modalitățile în care ar putea fi îmbunătățit sunt binevenite ( /me notează el niciodată a căutat în CPAN un rezolvator boggle, , dar acest lucru a fost mai distractiv de rezolvat )

actualizat pentru noi criterii

#!/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 ",
", map { $_->pp } @{
  traverseGraph( $d, $m, 3, $c ) ;
};

Informații despre arhivă/execuție pentru comparație:

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% ==============================

Mai multe Mumblings pe care optimizarea Regex

Optimizarea regex pe care o folosesc eu este inutilă pentru dicționarele cu mai multe rezolvări, iar pentru mai multe rezolvări veți dori un dicționar complet, nu unul pretăiat.

Totuși, acestea fiind spuse, pentru rezolvări unice, este foarte rapidă. ( regex Perl sunt în C! 🙂 )

Iată câteva adăugiri de cod variate:

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

Comentarii

  • Știu că nu reușesc în clubul de optimizare, dar am avut probleme de viteză înainte de a ajunge la munca reală a codului, iar reducerea timpului de introducere de la 2s la 1,2s înseamnă mult pentru mine. –  > Por Kent Fredric.
  • /me a notat ciudat că acum a durat mai puțin timp pentru a regexa și a sări peste intrări decât a fost nevoie pentru a adăuga chei la un hash. –  > Por Kent Fredric.
  • Frumos, o implementare Perl! Mă duc să o execut acum. –  > Por Paolo Bergantino.
  • Blerg, am dificultăți în instalarea Tree::Trie pe serverul meu web. 🙁 – –  > Por Paolo Bergantino.
  • Cum ai generat ultimul raport (informații despre arhivă/execuție)? Pare a fi util. –  > Por jmanning2k.
John Fouhy

Ați putea împărți problema în două părți:

  1. Un fel de algoritm de căutare care va enumera șirurile posibile din grilă.
  2. O modalitate de a testa dacă un șir este un cuvânt valid.

În mod ideal, (2) ar trebui să includă, de asemenea, o modalitate de a testa dacă un șir de caractere este un prefix al unui cuvânt valid – acest lucru vă va permite să vă curățați căutarea și să economisiți o grămadă de timp.

Trie al lui Adam Rosenfield este o soluție pentru (2). Este elegantă și, probabil, ceea ce ar prefera specialistul dumneavoastră în algoritmi, dar cu limbajele moderne și computerele moderne, putem fi un pic mai leneși. De asemenea, așa cum sugerează Kent, putem reduce dimensiunea dicționarului nostru prin eliminarea cuvintelor care au litere care nu sunt prezente în grilă. Iată ceva 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; testarea prefixelor în timp constant. Încărcarea dicționarului pe care l-ai legat durează câteva secunde, dar numai câteva 🙂 (observați că words <= prefixes)

Acum, pentru partea (1), sunt înclinat să gândesc în termeni de grafice. Așa că voi construi un dicționar care să arate cam așa:

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

adică. graph[(x, y)] este setul de coordonate la care se poate ajunge din poziția (x, y). De asemenea, voi adăuga un nod fictiv None care se va conecta la tot.

Construirea este puțin cam greoaie, deoarece există 8 poziții posibile și trebuie să faci verificarea limitelor. Iată un cod python corespunzător:

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))

Acest cod construiește, de asemenea, un dicționar de corespondență (x,y) pentru caracterul corespunzător. Acest lucru îmi permite să transform o listă de poziții într-un cuvânt:

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

În cele din urmă, facem o căutare în profunzime. Procedura de bază este următoarea:

  1. Căutarea ajunge la un anumit nod.
  2. Se verifică dacă traseul de până acum ar putea face parte dintr-un cuvânt. Dacă nu, nu se mai explorează această ramură.
  3. Se verifică dacă drumul parcurs până acum este un cuvânt. Dacă da, se adaugă la lista de rezultate.
  4. Explorați toți copiii care nu fac parte din calea de până acum.

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)

Rulați codul ca:

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)

și inspectează res pentru a vedea răspunsurile. Iată o listă de cuvinte găsite pentru exemplul dvs., ordonate în funcție de mărime:

 ['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']

Codul are nevoie (literalmente) de câteva secunde pentru a încărca dicționarul, dar restul este instantaneu pe mașina mea.

Comentarii

  • Foarte frumos! Foarte rapid, de asemenea. O să aștept să văd dacă mai vine cineva, dar răspunsul tău pare bun până acum. –  > Por Paolo Bergantino.
  • Nu înțeleg de ce „embole” este singurul tău cuvânt din 6 litere, eu am 10 cuvinte diferite pentru asta. Se pare că interziceți vizitarea aceluiași nod de două ori și, așa cum a declarat OP, este un joc corect. –  > Por Kent Fredric.
  • ok, este posibil să aibă în continuare un bug, deoarece elimină „FAMBLE”, „WAMBLE” și „SEMBLE”, care nu au caractere comune. –  > Por Kent Fredric.
  • Bine reperat! Bug-ul a fost la crearea setului de prefixe: Trebuia să folosesc range(len(w)+1) în loc de range(len(w)). Am susținut că words <= prefixes dar se pare că nu am testat asta :-/ –  > Por John Fouhy.
  • Acest lucru m-a ajutat să învăț cum funcționează un DFS și cum să implementez unul. Nu eram sigur de vreo modalitate de a-mi arăta aprecierea pentru acest lucru altfel decât printr-un comentariu. Mulțumesc! –  > Por Graham Smith.

Încercarea mea în Java. Este nevoie de aproximativ 2 s pentru a citi fișierul și a construi trie și de aproximativ 50 ms pentru a rezolva puzzle-ul. Am folosit dicționarul legat în întrebare (are câteva cuvinte despre care nu știam că există în limba engleză, cum ar fi 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

Codul sursă este format din 6 clase. Le voi posta mai jos (dacă nu este o practică corectă pe StackOverflow, vă rog să-mi spuneți).

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

Comentarii

  • Am comparat rezultatul meu cu ieșirile altor StackOverflower și se pare că din ieșirile lui Adam, John și rvarcher lipseau câteva cuvinte. De exemplu, „Mwa” este în dicționar (da!), dar nu este returnat în ieșirile de la Adam, John și rvarcher. Acesta este returnat de două ori în link-ul PHP al lui Paolo. –  > Por gineer.
  • Am încercat aceasta prin copy paste. Scrie „Reading…” și „Finish reading…”, dar nu apare nimic după aceea. Nu se afișează nici un meci. –  > Por MikkoP.

Cred că probabil îți vei petrece cea mai mare parte a timpului încercând să potrivești cuvinte care nu pot fi construite de grila de litere. Așa că, primul lucru pe care l-aș face ar fi să încerc să accelerez această etapă și asta ar trebui să te ajute în mare parte.

Pentru aceasta, aș reexprima grila ca un tabel de posibile „mișcări” pe care le-ai indexa în funcție de tranziția literei la care te uiți.

Începeți prin a atribui fiecărei litere un număr din întregul alfabet (A=0, B=1, C=2, … și așa mai departe).

Să luăm acest exemplu:

h b c d
e e g h
l l k l
m o f p

Și deocamdată, să folosim alfabetul literelor pe care le avem (în mod normal, probabil că ați dori să folosiți același alfabet întreg de fiecare dată):

 b | c | d | e | f | g | h | k | l | m |  o |  p
---+---+---+---+---+---+---+---+---+---+----+----
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11

Apoi faceți un array boolean 2D care să vă spună dacă aveți o anumită tranziție de litere disponibilă:

     |  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

Acum treceți prin lista de cuvinte și convertiți cuvintele în tranziții:

hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10

Apoi verificați dacă aceste tranziții sunt permise, căutându-le în tabel:

[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T

Dacă toate sunt permise, există o șansă ca acest cuvânt să fie găsit.

De exemplu, cuvântul „cască” poate fi exclus la cea de-a patra tranziție (m în e: helMEt), deoarece această intrare din tabelul dvs. este falsă.

Și cuvântul hamster poate fi exclus, deoarece prima tranziție (h la a) nu este permisă (nici măcar nu există în tabelul dvs.).

Acum, pentru probabil foarte puținele cuvinte rămase pe care nu le-ați eliminat, încercați să le găsiți în grilă, așa cum faceți acum sau așa cum se sugerează în alte răspunsuri de aici. Acest lucru este pentru a evita falsurile pozitive care rezultă din salturi între litere identice în grila dvs. De exemplu, cuvântul „help” este permis de tabel, dar nu și de grilă.

Câteva sfaturi suplimentare de îmbunătățire a performanței pe această idee:

  1. În loc să folosiți o matrice 2D, utilizați o matrice 1D și calculați pur și simplu indexul celei de-a doua litere. Astfel, în loc de o matrice 12×12 ca mai sus, faceți o matrice 1D de lungime 144. Dacă apoi utilizați întotdeauna același alfabet (de exemplu, o matrice 26×26 = 676×1 pentru alfabetul englez standard), chiar dacă nu toate literele apar în grila dvs., puteți calcula în prealabil indicii din această matrice 1D pe care trebuie să îi testați pentru a se potrivi cu cuvintele din dicționar. De exemplu, indicii pentru „hello” din exemplul de mai sus ar fi

    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
    
  2. Extindeți ideea la un tabel 3D (exprimat ca o matrice 1D), adică toate combinațiile de 3 litere permise. În acest fel, puteți elimina imediat și mai multe cuvinte și reduceți numărul de căutări în matrice pentru fiecare cuvânt cu 1: pentru „hello”, aveți nevoie doar de 3 căutări în matrice: hel, ell, llo. Apropo, va fi foarte rapid să construiți acest tabel, deoarece în grila dvs. există doar 400 de combinații posibile de 3 litere.

  3. Calculați în prealabil indicii mișcărilor din grila dvs. pe care trebuie să le includeți în tabel. Pentru exemplul de mai sus, trebuie să setați următoarele intrări la „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]
    .
    :
    
  4. Reprezentați, de asemenea, grila dvs. de joc într-o matrice 1-D cu 16 intrări și faceți ca tabelul precalculat în 3. să conțină indicii în această matrice.

Sunt sigur că, dacă folosiți această abordare, puteți face ca codul dvs. să ruleze nebunește de repede, dacă aveți dicționarul precalculat și deja încărcat în memorie.

BTW: Un alt lucru frumos de făcut, dacă construiți un joc, este să rulați acest tip de lucruri imediat în fundal. Începeți să generați și să rezolvați primul joc în timp ce utilizatorul încă se uită la ecranul de titlu al aplicației dvs. și își pune degetul în poziția de a apăsa „Play”. Apoi, generați și rezolvați următorul joc în timp ce utilizatorul îl joacă pe cel precedent. Acest lucru ar trebui să vă ofere mult timp pentru a vă rula codul.

(Îmi place această problemă, așa că probabil voi fi tentat să implementez propunerea mea în Java cândva în zilele următoare pentru a vedea cum ar funcționa de fapt… Voi posta codul aici după ce o voi face).

UPDATE:

Ok, am avut ceva timp astăzi și am implementat această idee în 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();
  }
}

Iată câteva rezultate:

Pentru grila din imaginea postată în întrebarea inițială (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

Pentru literele postate ca exemplu în întrebarea inițială (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

Pentru următoarea grilă de 5×5:

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 obține următorul rezultat:

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

Pentru aceasta am folosit TWL06 Tournament Scrabble Tournament Scrabble Word List, , deoarece linkul din întrebarea inițială nu mai funcționează. Acest fișier are 1,85 MB, deci este puțin mai scurt. Iar fișierul buildDictionary elimină toate cuvintele cu mai puțin de 3 litere.

Iată câteva observații cu privire la performanța acesteia:

  • Este de aproximativ 10 ori mai lent decât performanța raportată a implementării OCaml a lui Victor Nicollet. Nu știu dacă acest lucru este cauzat de algoritmul diferit, de dicționarul mai scurt pe care l-a folosit, de faptul că codul său este compilat, iar al meu rulează într-o mașină virtuală Java sau de performanța calculatoarelor noastre (al meu este un Intel Q6600 la 2,4 MHz care rulează WinXP). Dar este mult mai rapid decât rezultatele pentru celelalte implementări citate la sfârșitul întrebării inițiale. Așadar, dacă acest algoritm este superior dicționarului trie sau nu, nu știu în acest moment.

  • Metoda tabelară utilizată în checkWordTriplets() produce o aproximare foarte bună a răspunsurilor reale. Doar 1 din 3-5 cuvinte trecute prin ea nu va trece testul checkWords() test (a se vedea numărul de candidați vs. numărul de cuvinte reale de mai sus).

  • Ceva ce nu se poate vedea mai sus: checkWordTriplets() durează aproximativ 3,65 ms și, prin urmare, este pe deplin dominantă în procesul de căutare. checkWords() funcția ocupă aproape tot restul de 0,05-0,20 ms.

  • Timpul de execuție al funcției checkWordTriplets() funcție depinde liniar de dimensiunea dicționarului și este practic independent de dimensiunea plăcii!

  • Timpul de execuție al funcției checkWords() depinde de dimensiunea tabloului și de numărul de cuvinte care nu sunt excluse de către checkWordTriplets().

  • Aplicația checkWords() de mai sus este cea mai proastă primă versiune pe care am găsit-o. Practic, nu este deloc optimizată. Dar în comparație cu checkWordTriplets() este irelevantă pentru performanța totală a aplicației, așa că nu mi-am făcut griji în privința ei. Dar, , dacă dimensiunea plăcii devine mai mare, această funcție va deveni din ce în ce mai lentă și, în cele din urmă, va începe să conteze. Atunci, ar trebui să fie și ea optimizată.

  • Un lucru bun la acest cod este flexibilitatea sa:

    • Puteți schimba cu ușurință dimensiunea plăcii: Actualizați linia 10 și matricea String transmisă la initializeBoard().
    • Poate suporta alfabete mai mari/diferite și poate gestiona lucruri precum tratarea lui „Qu” ca o singură literă, fără niciun fel de supraperformanță. Pentru a face acest lucru, ar trebui să actualizați linia 9 și cele câteva locuri în care caracterele sunt convertite în numere (în prezent, pur și simplu prin scăderea a 65 din valoarea ASCII).

Bine, dar cred că până acum această postare a fost destul de lungă. Pot răspunde cu siguranță la orice întrebare pe care o aveți, dar haideți să mutăm asta în comentarii.

Comentarii

  • Frumos răspuns. Aș vrea să văd implementarea ta în Java. –  > Por MikkoP.
  • @MikkoP S-a făcut! 🙂 A durat aproximativ 3 ore și 220 de linii de cod. O modalitate bună de a trece o după-amiază. Anunțați-mă dacă aveți întrebări despre cum funcționează… 🙂 –  > Por Markus A..
  • Mulțumesc pentru postarea codului! L-am încercat cu propriul dicționar după ce am adăugat importurile lipsă. Primesc o excepție ArrayIndexOutOutOfBoundException pe linia ok = possibleTriplets[entry.triplets[t]];. hmm? –  > Por MikkoP.
  • @MikkoP Acest cod este scris în prezent pentru a presupune că dicționarul conține doar litere majuscule de la A la Z. Punctul nevralgic este în linia 34: entry.letters[i] = (byte) letter - 65; Se ia pur și simplu valoarea ASCII și se scade 65 („A”). Dacă în dicționarul dvs. aveți litere Umlaut sau litere minuscule, acest lucru va da valori mai mari de 31, care nu sunt planificate prin setarea dimensiunii alfabetului în linia 9. Pentru a suporta și alte litere, va trebui să extindeți această linie pentru a le plasa în intervalul permis de dimensiunea alfabetului. –  > Por Markus A..
  • @AlexanderN Probabil că înțelegeți corect logica. Am făcut o greșeală copiind grila de litere… Îmi pare rău… (fixat) –  > Por Markus A..
Paolo Bergantino

În mod surprinzător, nimeni nu a încercat o versiune PHP a acestui lucru.

Aceasta este o versiune PHP funcțională a soluției Python a lui John Fouhy.

Deși am luat câteva indicii din răspunsurile celorlalți, aceasta este copiată în mare parte de la John.

$boggle = "fxie
           amlo
           ewbx
           astu";

$alphabet = str_split(str_replace(array("
", " ", "r"), "", strtolower($boggle)));
$rows = array_map('trim', explode("
", $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);

Aici este un link live dacă doriți să o încercați. Deși durează ~2s în mașina mea locală, durează ~5s pe serverul meu web. În ambele cazuri, nu este foarte rapid. Totuși, totuși, este destul de hidos, așa că îmi imaginez că timpul poate fi redus semnificativ. Orice indicații despre cum se poate realiza acest lucru ar fi apreciate. Lipsa de tupluri din PHP a făcut ca coordonatele să fie ciudat de lucrat, iar incapacitatea mea de a înțelege ce naiba se întâmplă nu a ajutat deloc.

EDITARE: Câteva corecturi fac să dureze mai puțin de 1s la nivel local.

Comentarii

  • +1 @ „și incapacitatea mea de a înțelege ce naiba se întâmplă nu a ajutat deloc.” lol. Iubesc sinceritatea! –  > Por dna123.
  • Nu știu PHP, dar primul lucru pe care l-aș încerca ar fi să ridic ‘/[‘ . implode(”, $alphabet) . ‘]{3,}$/’ din buclă. Adică să setați o variabilă la acea valoare și să folosiți în schimb variabila în interiorul buclei. –  > Por Darius Bacon.
  • Sunt destul de sigur că PHP păstrează o memorie cache globală per-thread a expresiilor regulate compilate, dar voi încerca oricum. –  > Por Paolo Bergantino.
  • @Daniel: Se pare că este vorba de serverul meu web. Nu se întâmplă când rulează local. Shrug. Nu prea am chef să o vânez. –  > Por Paolo Bergantino.
  • Ce ar trebui să fie setat ca parametru 7. în funcția find_words în final? –  > Por MikkoP.
rvarcher

Nu sunteți interesat de VB? 🙂 Nu am putut rezista. Am rezolvat acest lucru în mod diferit față de multe dintre soluțiile prezentate aici.

Timpii mei sunt:

  • Încărcarea dicționarului și a prefixelor cuvintelor într-un hashtable: 0,5 până la 1 secundă.
  • Găsirea cuvintelor: în medie sub 10 milisecunde.

EDIT: Timpii de încărcare a dicționarului pe serverul gazdei web sunt cu aproximativ 1 până la 1,5 secunde mai mari decât pe computerul meu de acasă.

Nu știu cât de mult se vor deteriora timpii în cazul unei încărcări a serverului.

Am scris soluția mea ca o pagină web în .Net. myvrad.com/boggle

Folosesc dicționarul la care se face referire în întrebarea inițială.

Literele nu sunt refolosite într-un cuvânt. Sunt găsite doar cuvinte de 3 caractere sau mai lungi.

Folosesc un hashtable al tuturor prefixelor și cuvintelor unice de cuvinte în loc de un trie. Nu știam despre trie-uri, așa că am învățat ceva acolo. Ideea de a crea o listă de prefixe ale cuvintelor în plus față de cuvintele complete este ceea ce a făcut ca în cele din urmă timpii mei să scadă la un număr respectabil.

Citiți comentariile codului pentru detalii suplimentare.

Iată codul:

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

Comentarii

  • O să presupun aici că ați folosit sistemul a-p în loc de [x][y] pentru că acesta din urmă este destul de complex în VB? Mi-am petrecut o zi încercând să obțin o matrice dinamică cu 2 căi în acel moment, adică: array( array( array( 1, „hello”), 1, „hello” , array() ) , încă nu știu cum se face asta 😛 -.  > Por Kent Fredric.
  • În PHP și Perl array-urile cu 2 dim sunt distractive. Se poate face și în VB, dar nu l-aș numi un proces distractiv. Dim Arr(, ) As Integer = {{1,1},{0,0}}. Procesul A-P a apărut din faptul că m-am pus pe grilă și m-am întrebat: „Unde pot merge de aici?” Știu că este o soluție rigidă, dar funcționează aici. –  > Por rvarcher.
  • Ohh Îmi place VB.NET… Am încercat URL-ul dar nu a funcționat. A trebuit să reconstruiesc eu însumi codul tău ca Windows Forms și funcționează. Mulțumesc. –  > Por Ahmed Eissa.
Paul Chernoch

De îndată ce am văzut enunțul problemei, m-am gândit la „Trie”. Dar, văzând că mai multe alte postere au folosit această abordare, am căutat o altă abordare, doar pentru a fi diferit. Din păcate, abordarea Trie se comportă mai bine. Am rulat soluția Perl a lui Kent pe mașina mea și a durat 0.31 secunde pentru a rula, după ce am adaptat-o pentru a utiliza fișierul meu de dicționar. Propria mea implementare Perl a necesitat 0.54 secunde pentru a rula.

Aceasta a fost abordarea mea:

  1. Crearea unui hash de tranziție pentru a modela tranzițiile legale.

  2. Iterați prin toate cele 16^3 combinații posibile de trei litere.

    • În buclă, excludeți tranzițiile ilegale și repetați vizitele la același pătrat. Formați toate secvențele legale de 3 litere și stocați-le într-un hash.
  3. Apoi, parcurgeți în buclă toate cuvintele din dicționar.

    • Excludeți cuvintele care sunt prea lungi sau prea scurte.
    • Glisați o fereastră de 3 litere peste fiecare cuvânt și vedeți dacă se află printre combinațiile de 3 litere de la pasul 2. Excludeți cuvintele care nu reușesc. În acest fel se elimină majoritatea nepotrivirilor.
    • Dacă încă nu sunt eliminate, utilizați un algoritm recursiv pentru a vedea dacă cuvântul poate fi format prin parcurgerea unor trasee prin puzzle. (Această parte este lentă, dar este apelată rar).
  4. Tipăriți cuvintele găsite.

    Am încercat secvențe de 3 și 4 litere, dar secvențele de 4 litere au încetinit programul.

În codul meu, folosesc /usr/share/dict/words pentru dicționarul meu. Acesta vine standard pe MAC OS X și pe multe sisteme Unix. Puteți folosi un alt fișier dacă doriți. Pentru a sparge un alt puzzle, trebuie doar să schimbați variabila @puzzle. Acest lucru ar fi ușor de adaptat pentru matrici mai mari. Ar trebui doar să modificați hash-ul %transitions și hash-ul %legalTransitions.

Punctul forte al acestei soluții este faptul că codul este scurt, iar structurile de date simple.

Iată codul Perl (care utilizează prea multe variabile globale, știu):

#!/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(/
/, uc(readFile($wordlistFile)));
print "Words loaded from word list: " . scalar @words . "
";

print "Word file load time: " . (time - $startTime) . "
";
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) . "
";
my $postPrefix = time;

my @wordsFoundInPuzzle = findWordsInPuzzle(@words);

print "Find words in puzzle time: " . (time - $postPrefix) . "
";

print "Unique prefixes found: " . (scalar keys %prefixesInPuzzle) . "
";
print "Words found (" . (scalar @wordsFoundInPuzzle) . ") :
    " . join("
    ", @wordsFoundInPuzzle) . "
";

print "Total Elapsed time: " . (time - $startTime) . "
";

###########################################

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

Comentarii

  • S-a schimbat locația dicționarului? Am încercat să găsesc cuvintele din dicționar, deoarece am vrut să compar soluția mea cu toată lumea, dar nu l-am găsit pe link-ul dat la /usr/share/dict . Știu că este un thread destul de vechi, dar Ar fi minunat dacă mă puteți indica. Mulțumesc anticipat pentru ajutor. –  > Por Naman.
  • Nu am Mac-ul meu la îndemână în acest moment. Tot ce ai nevoie este un fișier cu cuvinte în limba engleză, unul la un rând, separate prin linii noi. Puteți găsi un astfel de fișier pe internet. Unul este aici: mieliestronk.com/corncob_lowercase.txt dar probabil că există liste cu mai multe cuvinte decât acesta. –  > Por Paul Chernoch.
  • Vă mulțumim mult pentru răspuns. Găsisem asta în fișierele Ubuntu. –  > Por Naman.

Știu că am întârziat foarte mult, dar am făcut unul dintre acestea cu ceva timp în urmă în PHP – doar pentru distracție prea…

http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastuAm găsit 75 de cuvinte (133 puncte) în 0.90108 secunde

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

Oferă câteva indicații despre ceea ce face programul de fapt – fiecare literă reprezintă locul de unde începe să caute printre modele, în timp ce fiecare „.” arată o cale pe care a încercat să o urmeze. Cu cât sunt mai multe „…”, cu atât a căutat mai mult.

Anunțați-mă dacă doriți codul… este un amestec oribil de PHP și HTML care nu trebuia să vadă lumina zilei, așa că nu îndrăznesc să îl postez aici 😛

Am petrecut 3 luni lucrând la o soluție la problema celor mai bune 10 puncte de densitate 5×5 Boggle.

Problema este acum rezolvată și expusă cu dezvăluiri complete pe 5 pagini web. Vă rog să mă contactați cu întrebări.

Algoritmul de analiză a planșei folosește o stivă explicită pentru a parcurge pseudo-recursiv pătratele planșei prin intermediul unui Graf de cuvinte aciclic direcționat cu informații despre copiii direcți și un mecanism de urmărire a ștampilei temporale. Este foarte posibil ca aceasta să fie cea mai avansată structură de date lexicale din lume.

Schema evaluează aproximativ 10 000 de planșe foarte bune pe secundă pe un quad core. (9500+ puncte)

Pagina web părintească:

DeepSearch.c – http://www.pathcom.com/~vadco/deep.html

Pagini web componente:

Tabloul de bord optim – http://www.pathcom.com/~vadco/binary.html

Structura avansată a lexiconului – http://www.pathcom.com/~vadco/adtdawg.html

Algoritmul de analiză a tabloului – http://www.pathcom.com/~vadco/guns.html

Procesarea paralelă a loturilor – http://www.pathcom.com/~vadco/parallel.html

-Acest ansamblu cuprinzător de lucrări va interesa doar o persoană care cere ce este mai bun.

Comentarii

  • Analiza dvs. este interesantă, dar rezultatele dvs. nu sunt, din punct de vedere tehnic, planșe Boggle. Jocul Boggle 5×5 include un zar care conține fețele BJKQXZ, implementarea dvs. exclude în mod explicit toate aceste litere și, prin urmare, poziția tabloului nu este de fapt posibilă într-un joc Boggle real. –  > Por MarkPflug.
jerebear

Algoritmul dvs. de căutare micșorează continuu lista de cuvinte pe măsură ce căutarea continuă?

De exemplu, în căutarea de mai sus, există doar 13 litere cu care pot începe cuvintele (reducând efectiv la jumătate numărul de litere de început).

Pe măsură ce adăugați mai multe permutări de litere, ar scădea și mai mult seturile de cuvinte disponibile, reducând căutarea necesară.

Eu aș începe de aici.

Smashery

Ar trebui să mă gândesc mai mult la o soluție completă, dar ca o optimizare la îndemână, mă întreb dacă nu ar merita să precalculați un tabel de frecvențe ale digramelor și trigramelor (combinații de 2 și 3 litere) pe baza tuturor cuvintelor din dicționarul dvs. și să folosiți acest tabel pentru a prioritiza căutarea. Eu aș alege literele de început ale cuvintelor. Astfel, dacă dicționarul dvs. ar conține cuvintele „India”, „Apă”, „Extrem” și „Extraordinar”, atunci tabelul precalculat ar putea fi:

'IN': 1
'WA': 1
'EX': 2

Apoi, căutați aceste digrame în ordinea comunității (mai întâi EX, apoi WA/IN).

RossFabricant

Mai întâi, citiți cum a rezolvat unul dintre proiectanții limbajului C# o problemă asemănătoare: http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-talisman-for-the-sultana-analyst.aspx.

La fel ca el, puteți începe cu un dicționar și canonizarea cuvintelor prin crearea unui dicționar dintr-o matrice de litere ordonate alfabetic la o listă de cuvinte care pot fi ortografiate din acele litere.

Apoi, începeți să creați cuvintele posibile din tablă și să le căutați. Bănuiesc că astfel veți ajunge destul de departe, dar cu siguranță există mai multe trucuri care ar putea accelera lucrurile.

Dan Lew

Vă sugerez să faceți un arbore de litere pe baza cuvintelor. Arborele ar fi compus din structurile unei litere, așa:

letter: char
isWord: boolean

Apoi construiți arborele, fiecare adâncime adăugând o nouă literă. Cu alte cuvinte, la primul nivel ar fi alfabetul; apoi, din fiecare arbore ar mai fi încă 26 de intrări, și așa mai departe, până când ai scris toate cuvintele. Țineți-vă bine de acest arbore analizat, iar toate răspunsurile posibile vor fi mai rapid de căutat.

Cu acest arbore analizat, puteți găsi foarte repede soluții. Iată pseudo-codul:

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.

Acest lucru ar putea fi accelerat cu puțină programare dinamică. De exemplu, în exemplul dvs., cei doi „A” sunt amândoi lângă un „E” și un „W”, care (din punctul în care s-au lovit) ar fi identice. Nu am suficient timp pentru a detalia cu adevărat codul pentru acest lucru, dar cred că puteți înțelege ideea.

De asemenea, sunt sigur că veți găsi și alte soluții dacă veți căuta pe Google „Boggle solver”.

Doar pentru distracție, am implementat unul în bash. Nu este super rapid, dar este rezonabil.

http://dev.xkyle.com/bashboggle/

physicsmichael

Hilar. Aproape că am postat aceeași întrebare acum câteva zile din cauza aceluiași joc blestemat! Nu am făcut-o însă pentru că doar am căutat pe google boggle solver python și am primit toate răspunsurile pe care le-aș putea dori.

Comentarii

  • Nu știam că numele popular al acestuia era „boggle”, dar am găsit ceva pe google, am fost curios să văd ce vor găsi oamenii pe SO. 🙂 –  > Por Paolo Bergantino.

Îmi dau seama că timpul acestei întrebări a venit și a dispărut, dar din moment ce lucram și eu la un rezolvator și am dat peste asta în timp ce căutam pe Google, m-am gândit că ar trebui să postez o referință la al meu, deoarece pare puțin diferit de unele dintre celelalte.

Am ales să folosesc o matrice plată pentru tabla de joc și să fac vânători recursive de la fiecare literă de pe tablă, trecând de la vecin valid la vecin valid, extinzând vânătoarea dacă lista curentă de litere are un prefix valid într-un index. În timpul traversării, noțiunea de cuvânt curent este o listă de indici în tablă, nu literele care alcătuiesc un cuvânt. La verificarea indexului, indexurile sunt traduse în litere și se face verificarea.

Indexul este un dicționar de forță brută care seamănă puțin cu un trie, dar care permite interogări pythonice ale indexului. Dacă cuvintele „cat” și „cater” se află în listă, veți obține acest lucru în dicționar:

   d = { 'c': ['cat','cater'],
     'ca': ['cat','cater'],
     'cat': ['cat','cater'],
     'cate': ['cater'],
     'cater': ['cater'],
   }

Deci, dacă cuvântul_curent este „ca”, știți că este un prefix valid, deoarece 'ca' in d returnează True (deci continuați parcurgerea tabloului). Iar dacă cuvântul_curent este „cat”, atunci știți că este un cuvânt valid, deoarece este un prefix valid și 'cat' in d['cat'] returnează și el True.

Dacă am simțit că acest lucru a permis obținerea unui cod lizibil care nu pare prea lent. La fel ca toată lumea, cheltuiala în acest sistem este citirea/construirea indexului. Rezolvarea tabloului este destul de mult zgomot.

Codul este la http://gist.github.com/268079. Este în mod intenționat vertical și naiv, cu o mulțime de verificări explicite ale validității, deoarece am vrut să înțeleg problema fără să o încurc cu o grămadă de magie sau obscuritate.

Mi-am scris rezolvatorul în C++. Am implementat o structură arborescentă personalizată. Nu sunt sigur că poate fi considerată o trie, dar este similară. Fiecare nod are 26 de ramuri, câte una pentru fiecare literă a alfabetului. Traversez ramurile tabloului boggle în paralel cu ramurile dicționarului meu. Dacă ramura nu există în dicționar, nu o mai caut pe tabla Boggle. Convertesc toate literele de pe tablă în ints. Așadar, „A” = 0. Deoarece este vorba doar de matrici, căutarea este întotdeauna O(1). Fiecare nod stochează dacă completează un cuvânt și câte cuvinte există în copiii săi. Arborele este curățat pe măsură ce sunt găsite cuvinte pentru a reduce căutarea repetată a acelorași cuvinte. Cred că și tăierea este de asemenea O(1).

CPU: Pentium SU2700 1.3GHz
RAM: 3gb

Încarcă un dicționar de 178.590 de cuvinte în < 1 secundă.
Rezolvă 100×100 Boggle (boggle.txt) în 4 secunde. ~44.000 de cuvinte găsite.
Rezolvarea unui Boggle 4×4 este prea rapidă pentru a oferi un punct de referință semnificativ. 🙂

Rezolvarea rapidă a Boggle GitHub Repo

Având în vedere o tablă Boggle cu N rânduri și M coloane, să presupunem următoarele:

  • N*M este substanțial mai mare decât numărul de cuvinte posibile.
  • N*M este substanțial mai mare decât cel mai lung cuvânt posibil

În aceste ipoteze, complexitatea acestei soluții este O(N*M).

Cred că compararea timpilor de execuție pentru acest singur exemplu de tablă în multe privințe nu are sens, dar, de dragul exhaustivității, această soluție se finalizează în <0,2s pe MacBook Pro-ul meu modern.

Această soluție va găsi toate căile posibile pentru fiecare cuvânt din 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}"

Această soluție oferă, de asemenea, direcția de căutare în tabla dată

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

Output:

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  → → ↑ ↘ →

Cod:

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 ('
')

    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)

Am implementat o soluție în OCaml. Aceasta precompilează un dicționar sub forma unei trie și utilizează frecvențe de secvențe de două litere pentru a elimina marginile care nu ar putea apărea niciodată într-un cuvânt pentru a accelera și mai mult procesarea.

Rezolvă placa dvs. de exemplu în 0,35 ms (cu un timp de pornire suplimentar de 6 ms, care este în mare parte legat de încărcarea trie în memorie).

Soluțiile găsite:

["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"]

Comentarii

  • Acest lucru este frumos, dar toate timpii postați aici implică orice timp de „pornire” pentru a încărca dicționarul în memorie, astfel încât compararea celor 0,35 cu celelalte timpuri este destul de departe de a fi exactă. De asemenea, folosiți un dicționar diferit? Îți lipsesc câteva cuvinte. În orice caz, +1 –  > Por Paolo Bergantino.
  • Timpul de pornire durează 6 ms, deci ai nevoie de 6,35 ms pentru o execuție completă. Folosesc aplicația mea locală /usr/share/dict dicționar local, iar unele dintre cuvinte lipsesc într-adevăr (cum ar fi EMBOLE). –  > Por Victor Nicollet.

O soluție JavaScript Node.JS. Calculează toate cele 100 de cuvinte unice în mai puțin de o secundă, ceea ce include citirea fișierului de dicționar (MBA 2012).

Ieșire:
[„FAM”,”TUX”,”TUB”,”FAE”,”ELI”,”ELM”,”ELB”,”TWA”,”TWA”,”SAW”,”AMI”,”SWA”,”SWA”,”AME”,”SEA”,”SEW”,”AES”,”AWL”,”AWE”,”SEA”,”AWA”,”MIX”,”MIL”,”AST”,”ASE”,”MAX”,”MAE”,”MAW”, „MEW”,”AWE”,”MES”,”AWL”,”LIE”,”LIM”,”AWA”,”AES”,”BUT”,”BLO”,”WAS”,”WAE”,”WEA”,”LEI”,”LEO”,”LOB”,”LOX”,”WEM”,”OIL”,”OLM”,”WEA”,”WAE”,”WAX”,”WAF”,”MILO”,”EAST”,”WAME”, „TWAS”, „TWAE”, „EMIL”, „WEAM”, „OIME”, „AXIL”, „WEST”, „TWAE”, „LIMB”, „WASE”, „WAST”, „BLEO”, „STUB”, „BOIL”, „BOLE”, „LIME”, „SAWT”, „LIMA”, „MESA”, „MEWL”, „AXLE”, „FAME”, „ASEM”, „MILE”, „AMIL”, „SEAX”, „SEAM”, „SEMI”, „SWAM”, „AMBO”, „AMLI”, „AXILE”, „AMBLE”, „SWAMI”, „AWEST”, „AWEST”, „LIMAX”, „LIMES”, „LIMBU”, „LIMBO”, „EMBOX”, „SEMBLE”, „EMBOLE”, „WAMBLE”, „FAMBLE”].

Cod:

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('
')

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

Deci am vrut să adaug o altă modalitate PHP de a rezolva acest lucru, deoarece toată lumea iubește PHP.Există o mică refactorizare pe care aș dori să o fac, cum ar fi utilizarea unei corespondențe de regexpresie cu fișierul de dicționar, dar în acest moment doar încarc întregul fișier de dicționar într-o listă de cuvinte.

Am făcut acest lucru folosind o idee de listă legată. Fiecare nod are o valoare de caracter, o valoare de locație și un pointer următor.

Valoarea locației este modul în care am aflat dacă două noduri sunt conectate.

1     2     3     4
11    12    13    14
21    22    23    24
31    32    33    34

Astfel, folosind această grilă, știu că două noduri sunt conectate dacă locația primului nod este egală cu locația celui de-al doilea nod +/- 1 pentru același rând, +/- 9, 10, 11 pentru rândul de deasupra și de dedesubt.

Folosesc recursivitatea pentru căutarea principală. Acesta ia un cuvânt din wordList, găsește toate punctele de plecare posibile și apoi găsește în mod recursiv următoarea conexiune posibilă, ținând cont de faptul că nu poate merge la o locație pe care o folosește deja (motiv pentru care adaug $notInLoc).

Oricum, știu că are nevoie de o anumită refactorizare și mi-ar plăcea să aud păreri despre cum să o fac mai curată, dar produce rezultatele corecte pe baza fișierului dicționar pe care îl folosesc. În funcție de numărul de vocale și de combinații de pe tablă, durează între 3 și 6 secunde. Știu că odată ce voi preg_match rezultatele dicționarului, acest lucru se va reduce semnificativ.

<?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);

    ?>

Știu că am ajuns foarte târziu la petrecere, dar am implementat, ca un exercițiu de codare, un rezolvator de boggle în mai multe limbaje de programare (C++, Java, Go, C#, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl) și m-am gândit că cineva ar putea fi interesat de acestea, așa că las linkul aici:https://github.com/AmokHuginnsson/boggle-solvers

Iată soluția Utilizarea cuvintelor predefinite în setul de instrumente NLTK NLTK are pachetul nltk.corpus în care avem un pachet numit words și care conține mai mult de 2Lakhs cuvinte englezești pe care le puteți folosi pur și simplu în programul dumneavoastră.

După ce ați creat matricea, convertiți-o într-o matrice de caractere și executați acest cod

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)

Output:

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

Sper că ați înțeles.

Iată implementarea mea în java: https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

Construirea Trie a durat 0 ore, 0 minute, 1 secundă, 532 milisecunde
Căutarea cuvintelor a durat 0 ore, 0 minute, 0 secunde, 92 milisecunde

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 

Notă:Am folosit dicționarul și matricea de caractere de la începutul acestui subiect. Codul a fost rulat pe MacBookPro al meu, mai jos sunt câteva informații despre mașină.

Numele modelului: MacBookPro: MacBook Pro
Identificatorul modelului: MacBookPro8,1
Numele procesorului: Intel Core i5
Viteza procesorului: 2.3 GHz
Numărul de procesoare: 1
Numărul total de nuclee: 2
Cache L2 (per nucleu): 256 KB
Cache L3: 3 MB
Memorie: 4 GB
Versiunea de boot ROM: MBP81.0047.B0E
Versiunea SMC (sistem): 1.68f96

Am rezolvat și eu această problemă, cu Java. Implementarea mea are 269 de linii și este destul de ușor de utilizat. Mai întâi trebuie să creați o nouă instanță a clasei Boggler și apoi să apelați funcția solve cu grila ca parametru. Pe calculatorul meu durează aproximativ 100 ms pentru a încărca dicționarul de 50 000 de cuvinte și găsește cuvintele în aproximativ 10-20 ms. Cuvintele găsite sunt stocate într-o 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;
    }
}

Am rezolvat acest lucru în c. Este nevoie de aproximativ 48 ms pentru a rula pe calculatorul meu (cu aproximativ 98% din timp petrecut pentru a încărca dicționarul de pe disc și a crea trie). Dicționarul este /usr/share/dict/american-english, care are 62886 de cuvinte.

Codul sursă

Am rezolvat acest lucru perfect și foarte rapid. L-am pus într-o aplicație android. Vedeți videoclipul la link-ul din play store pentru a o vedea în acțiune.

Word Cheats este o aplicație care „sparge” orice joc de cuvinte în stil matrix. Această aplicație a fost construităpentru a mă ajuta să trișez la word scrambler. Poate fi folosit pentru căutări de cuvinte, ruzzle, cuvinte, word finder, word crack, boggle și multe altele!

Acesta poate fi văzut aicihttps://play.google.com/store/apps/details?id=com.harris.wordcracker

Vedeți aplicația în acțiune în videohttps://www.youtube.com/watch?v=DL2974WmNAI

Am rezolvat această problemă în C#, folosind un algoritm DFA. Puteți verifica codul meu la

https://github.com/attilabicsko/wordshuffler/

În plus față de găsirea cuvintelor într-o matrice, algoritmul meu salvează căile reale ale cuvintelor, astfel încât, pentru proiectarea unui joc de căutare a cuvintelor, puteți verifica dacă există un cuvânt pe o cale reală.

Ce ziceți de o simplă sortare și de utilizarea căutare binară în dicționar?

Returnează întreaga listă în 0.35 sec și poate fi optimizată în continuare (de exemplu, prin eliminarea cuvintelor cu litere nefolosite etc.).

from bisect import bisect_left

f = open("dict.txt")
D.extend([line.strip() for line in f.readlines()])
D = sorted(D)

def neibs(M,x,y):
    n = len(M)
    for i in xrange(-1,2):
        for j in xrange(-1,2):
            if (i == 0 and j == 0) or (x + i < 0 or x + i >= n or y + j < 0 or y + j >= n):
                continue
            yield (x + i, y + j)

def findWords(M,D,x,y,prefix):
    prefix = prefix + M[x][y]

    # find word in dict by binary search
    found = bisect_left(D,prefix)

    # if found then yield
    if D[found] == prefix: 
        yield prefix

    # if what we found is not even a prefix then return
    # (there is no point in going further)
    if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
        return

    # recourse
    for neib in neibs(M,x,y):
        for word in findWords(M,D,neib[0], neib[1], prefix):
            yield word

def solve(M,D):
    # check each starting point
    for x in xrange(0,len(M)):
        for y in xrange(0,len(M)):
            for word in findWords(M,D,x,y,""):
                yield word

grid = "fxie amlo ewbx astu".split()
print [x for x in solve(grid,D)]

Comentarii

  • Am încercat acest lucru, dar. mai întâi trebuie să spui că D este o listă. … altfel generează o eroare. atunci primesc „if D[found] == prefix: IndexError: indexul listei este în afara intervalului”. S-ar putea să fac ceva greșit. Python 2.7+ –  > Por OWADVL.
    package ProblemSolving;

import java.util.HashSet;
import java.util.Set;

/**
 * Given a 2-dimensional array of characters and a
 * dictionary in which a word can be searched in O(1) time.
 * Need to print all the words from array which are present
 * in dictionary. Word can be formed in any direction but
 * has to end at any edge of array.
 * (Need not worry much about the dictionary)
 */
public class DictionaryWord {
    private static char[][] matrix = new char[][]{
            {'a', 'f', 'h', 'u', 'n'},
            {'e', 't', 'a', 'i', 'r'},
            {'a', 'e', 'g', 'g', 'o'},
            {'t', 'r', 'm', 'l', 'p'}
    };
    private static int dim_x = matrix.length;
    private static int dim_y = matrix[matrix.length -1].length;
    private static Set<String> wordSet = new HashSet<String>();

    public static void main(String[] args) {
        //dictionary
        wordSet.add("after");
        wordSet.add("hate");
        wordSet.add("hair");
        wordSet.add("air");
        wordSet.add("eat");
        wordSet.add("tea");

        for (int x = 0; x < dim_x; x++) {
            for (int y = 0; y < dim_y; y++) {
                checkAndPrint(matrix[x][y] + "");
                int[][] visitedMap = new int[dim_x][dim_y];
                visitedMap[x][y] = 1;
                recursion(matrix[x][y] + "", visitedMap, x, y);
            }
        }
    }

    private static void checkAndPrint(String word) {
        if (wordSet.contains(word)) {
            System.out.println(word);
        }
    }

    private static void recursion(String word, int[][] visitedMap, int x, int y) {
        for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
            for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
                if (visitedMap[i][j] == 1) {
                    continue;
                } else {
                    int[][] newVisitedMap = new int[dim_x][dim_y];
                    for (int p = 0; p < dim_x; p++) {
                        for (int q = 0; q < dim_y; q++) {
                           newVisitedMap[p][q] = visitedMap[p][q];
                        }
                    }
                    newVisitedMap[i][j] = 1;
                    checkAndPrint(word + matrix[i][j]);
                    recursion(word + matrix[i][j], newVisitedMap, i, j);
                }
            }
        }
    }

}

import java.util.HashSet;
import java.util.Set;

/**
 * @author Sujeet Kumar ([email protected]) It prints out all strings that can
 *         be formed by moving left, right, up, down, or diagonally and exist in
 *         a given dictionary , without repeating any cell. Assumes words are
 *         comprised of lower case letters. Currently prints words as many times
 *         as they appear, not just once. *
 */

public class BoggleGame 
{
  /* A sample 4X4 board/2D matrix */
  private static char[][] board = { { 's', 'a', 's', 'g' },
                                  { 'a', 'u', 't', 'h' }, 
                                  { 'r', 't', 'j', 'e' },
                                  { 'k', 'a', 'h', 'e' }
};

/* A sample dictionary which contains unique collection of words */
private static Set<String> dictionary = new HashSet<String>();

private static boolean[][] visited = new boolean[board.length][board[0].length];

public static void main(String[] arg) {
    dictionary.add("sujeet");
    dictionary.add("sarthak");
    findWords();

}

// show all words, starting from each possible starting place
private static void findWords() {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            StringBuffer buffer = new StringBuffer();
            dfs(i, j, buffer);
        }

    }

}

// run depth first search starting at cell (i, j)
private static void dfs(int i, int j, StringBuffer buffer) {
    /*
     * base case: just return in recursive call when index goes out of the
     * size of matrix dimension
     */
    if (i < 0 || j < 0 || i > board.length - 1 || j > board[i].length - 1) {
        return;
    }

    /*
     * base case: to return in recursive call when given cell is already
     * visited in a given string of word
     */
    if (visited[i][j] == true) { // can't visit a cell more than once
        return;
    }

    // not to allow a cell to reuse
    visited[i][j] = true;

    // combining cell character with other visited cells characters to form
    // word a potential word which may exist in dictionary
    buffer.append(board[i][j]);

    // found a word in dictionary. Print it.
    if (dictionary.contains(buffer.toString())) {
        System.out.println(buffer);
    }

    /*
     * consider all neighbors.For a given cell considering all adjacent
     * cells in horizontal, vertical and diagonal direction
     */
    for (int k = i - 1; k <= i + 1; k++) {
        for (int l = j - 1; l <= j + 1; l++) {
            dfs(k, l, buffer);

        }

    }
    buffer.deleteCharAt(buffer.length() - 1);
    visited[i][j] = false;
  }
}

Comentarii

  • Înconjurarea codului tău de niște explicații ți-ar îmbunătăți serios răspunsul. –  > Por zx485.

Aceasta este soluția pe care am găsit-o pentru rezolvarea problemei boggle. Cred că este cel mai „pitoresc” mod de a face lucrurile:

from itertools import combinations
from itertools import izip
from math import fabs

def isAllowedStep(current,step,length,doubleLength):
            # for step == length -1 not to be 0 => trivial solutions are not allowed
    return length > 1 and 
           current + step < doubleLength and current - step > 0 and 
           ( step == 1 or step == -1 or step <= length+1 or step >= length - 1)

def getPairwiseList(someList):
    iterableList = iter(someList)
    return izip(iterableList, iterableList)

def isCombinationAllowed(combination,length,doubleLength):

    for (first,second) in  getPairwiseList(combination):
        _, firstCoordinate = first
        _, secondCoordinate = second
        if not isAllowedStep(firstCoordinate, fabs(secondCoordinate-firstCoordinate),length,doubleLength):
            return False
    return True

def extractSolution(combinations):
    return ["".join([x[0] for x in combinationTuple]) for combinationTuple in combinations]


length = 4
text = tuple("".join("fxie amlo ewbx astu".split()))
textIndices = tuple(range(len(text)))
coordinates = zip(text,textIndices)

validCombinations = [combination for combination in combinations(coordinates,length) if isCombinationAllowed(combination,length,length*length)]
solution = extractSolution(validCombinations)

Această parte vă sfătuiesc cu drag să nu o folosiți pentru toate meciurile posibile. dar ar oferi de fapt o posibilitate de a verifica dacă cuvintele pe care le-ați generat constituie de fapt cuvinte valide:

import mechanize
def checkWord(word):
    url = "https://en.oxforddictionaries.com/search?filter=dictionary&query="+word
    br = mechanize.Browser()
    br.set_handle_robots(False)
    response = br.open(url)
    text = response.read()
    return "no exact matches"  not in text.lower()

print [valid for valid in solution[:10] if checkWord(valid)]