[algorithm] 문자 행렬에서 가능한 단어 목록을 찾는 방법 [Boggle Solver]

최근에 나는 iPhone에서 Scramble이라는 게임을 해왔다. 여러분 중 일부는이 게임을 Boggle로 알고있을 것입니다. 기본적으로 게임이 시작되면 다음과 같은 문자 행렬이 나타납니다.

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

이 게임의 목표는 글자를 묶어 형성 할 수있는 단어를 최대한 많이 찾는 것입니다. 모든 글자로 시작할 수 있으며, 그 주위의 모든 글자는 공정한 게임이며, 다음 글자로 넘어 가면 해당 글자를 둘러싼 모든 글자는 이전에 사용한 글자를 제외한 모든 글자 입니다. 그래서 위의 표에서, 예를 들면, 나는 단어를 가지고 올 수있는 LOB, TUX, SEA, FAME, 등의 단어는이 경기에서 16 것이다 그러나 일부 구현에 변화 할 수있는, 더 이상되는 N × N의 문자보다 적어도 3 개 문자 및 없어야합니다 . 이 게임은 재미 있고 중독성이 있지만 나는 그다지 능숙하지 않으며 가능한 최고의 단어 (더 길수록 더 많은 포인트를 얻음)를주는 프로그램을 만들어 약간의 속임수를 쓰고 싶었습니다.

_{(출처 : boggled.org )}

안타깝게도 알고리즘이나 효율성 등은별로 좋지 않습니다. 첫 번째 시도는이 사전 (~ 2.3MB)과 같은 사전을 사용하며 사전 항목과의 조합을 일치시키려는 선형 검색을 수행합니다. 이것은 매우 걸립니다 가능한 단어를 찾기 위해 오랜 시간을, 그리고 당신은 라운드 당 2 분 얻을 수 있기 때문에, 단순히 적합하지 않습니다.

어떤 Stackoverflowers가 더 효율적인 솔루션을 만들 수 있는지 알고 싶습니다. 나는 속도가 필수적이기 때문에 Java 또는 C ++가있는 것도 멋지지만 Big 3 Ps : Python, PHP 및 Perl을 사용하는 솔루션을 주로 찾고 있습니다.

현재 솔루션 :

Adam Rosenfield, Python, ~ 20 초
존 푸이, 파이썬, ~ 3
켄트 프레드릭, 펄, ~ 1
다리우스 베이컨, Python, ~ 1
rvarcher, VB.NET (라이브 링크) , ~ 1
Paolo Bergantino, PHP (라이브 링크) , ~ 5 초 (~ 2 초 로컬)

답변

내 대답은 여기의 다른 답변처럼 작동하지만 사전을 더 빨리 설정하는 것에서 다른 Python 솔루션보다 조금 더 빠르기 때문에 게시하겠습니다. (이를 John Fouhy의 솔루션과 비교하여 확인했습니다.) 설정 후, 해결해야 할 시간이 소음으로 줄었습니다.

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

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

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

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

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

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

샘플 사용법 :

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

편집 : 3 자 미만의 단어를 필터링합니다.

편집 2 : Kent Fredric의 Perl 솔루션이 더 빠른 이유가 궁금합니다. 문자 집합 대신 정규식 일치를 사용하는 것으로 나타났습니다. 파이썬에서 똑같이하면 속도가 두 배가됩니다.

답변

가장 빠른 해결책은 사전을 trie 에 저장하는 것입니다 . 이어서, (삼중의 큐 생성 X , Y를 , 이야 ) 여기서, 큐에 대응하는 프리픽스 각 소자 의 위치 (종료 그리드 철자 할 수있는 단어의 X , Y가 ). 초기화와 큐 N은 X N (여기서, 요소 N그리드의 각 사각형에 대해 하나씩, 은 그리드의 크기 임)로 . 그런 다음 알고리즘은 다음과 같이 진행됩니다.

큐가 비어 있지 않은 동안 :
  트리플을 빼기 (x, y, s)
  문자 x가 (x, y)에 인접한 각 정사각형 (x ', y')의 경우 :
    s + c가 단어이면 s + c를 출력하십시오.
    s + c가 단어의 접두사 인 경우 (x ', y', s + c)를 대기열에 삽입하십시오.

사전을 trie에 저장하는 경우 s + c 가 단어인지 또는 단어의 접두사인지를 일정한 시간에 테스트 할 수 있습니다 (현재 노드에 대한 포인터와 같은 각 대기열 데이텀에 추가 메타 데이터를 제공하는 경우) 이 알고리즘의 실행 시간은 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

사용법 예 :

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

산출:

[ ‘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 ‘ , ‘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’, ‘ 송곳 ‘,’awa ‘,’awe ‘,’awa ‘,’aes ‘,’swa ‘,’swa ‘,’sew ‘,’sea ‘,’sea ‘,’saw ‘,’tux ‘,’tub ‘ ‘tut’, ‘twa’, ‘twa’, ‘tst’, ‘utu’, ‘fama’, ‘fame’, ‘ixil’, ‘imam’, ‘amli’, ‘amil’, ‘ambo’, ‘ 액슬 ‘,’차축 ‘,’mimi ‘,’mima ‘,’mime ‘,’milo ‘,’마일 ‘,’mewl ‘,’mese ‘,’mesa ‘,’lolo ‘,’lobo ‘,’lima ‘,’lime ‘,’limb ‘,’lile ‘,’oime ‘,’oleo ‘,’olio ‘ , ‘oboe’, ‘obol’, ’emim’, ’emil’, ‘east’, ‘ease’, ‘wame’, ‘wawa’, ‘wawa’, ‘weam’, ‘west’, ‘wese’, ‘ wast ‘,’wase ‘,’wawa ‘,’wawa ‘,’boil ‘,’bolo ‘,’bole ‘,’bobo ‘,’blob ‘,’bleo ‘,’bubo ‘,’asem ‘,’stub ‘ , ‘stut’, ‘swam’, ‘semi’, ‘seme’, ‘seam’, ‘seax’, ‘saasa’, ‘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 ‘ ]sawbwa ‘]sawbwa ‘]

참고 :이 프로그램은 1 글자 단어를 출력하거나 단어 길이별로 필터링하지 않습니다. 추가하기 쉽지만 실제로는 문제와 관련이 없습니다. 또한 여러 방법으로 철자가 가능한 경우 일부 단어를 여러 번 출력합니다. 주어진 단어가 여러 가지 방식으로 철자 될 수있는 경우 (가장 나쁜 경우 : 그리드의 모든 문자가 동일하고 (예 : ‘A’) 사전에 ‘aaaaaaaaaa’와 같은 단어가있는 경우) 실행 시간이 엄청나게 지수 적으로 증가합니다. . 중복을 필터링하고 정렬하는 것은 알고리즘이 완료된 후의 사소한 일입니다.

답변

사전 속도 향상을 위해 사전 비교를 크게 줄이기 위해 수행 할 수있는 일반적인 변환 / 프로세스가 있습니다.

위 표에 16 자만 포함되어 있고 일부 문자는 중복되므로 달성 할 수없는 문자가있는 항목을 필터링하여 사전의 총 키 수를 크게 줄일 수 있습니다.

나는 이것이 명백한 최적화라고 생각했지만 아무도 그것을하지 않았다는 것을 언급했다.

입력 패스 중에 단순히 200,000 키 사전에서 2,000 키로 줄였습니다. 이것은 최소한 메모리 오버 헤드를 줄이며, 메모리가 무한히 빠르지 않기 때문에 어딘가에 속도 증가에 매핑됩니다.

펄 구현

내 구현은 유효성이 아니라 추출 된 모든 문자열의 정확한 경로를 알 수 있도록 중요하기 때문에 약간 무겁습니다.

또한 이론적으로 구멍이있는 그리드와 다른 크기의 선이있는 그리드를 허용하는 몇 가지 적응 방법이 있습니다 (입력을 올바르게하고 어떻게 든 정렬한다고 가정).

초기 필터는 애플리케이션에서 가장 큰 병목 현상이며, 이전에 의심 한 바에 따르면이 라인은 1.5 초에서 7.5 초로 늘어납니다.

실행되면 모든 단일 자릿수가 유효한 단어에 있다고 생각하는 것처럼 보이지만 사전 파일의 작동 방식으로 인한 것 같습니다.

조금 부풀었지만 적어도 나는 cpan에서 Tree :: Trie 를 재사용합니다.

일부는 기존 구현에서 부분적으로 영감을 얻었으며 일부는 이미 염두에 두었습니다.

건설적인 비판과는 환영을 개선 할 수있는 방법 (/ 나 그가 결코 노트 머뭇 거리는 솔버에 대한 CPAN을 검색하지 않습니다 , 그러나 이것은 해결하기 위해 더 많은 재미)

새로운 기준으로 업데이트

#!/usr/bin/perl 

use strict;
use warnings;

{

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

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

  package Prefix;
  use Moose;

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

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

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

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

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

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

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

  # Returns  the rightmost node on this path

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

  # pretty-format $o->path

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

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

  __PACKAGE__->meta->make_immutable;
}

{

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

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

  package MatrixNode;
  use Moose;

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

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

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

  # Convenience method to derive a path starting at this node

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

}

{

  package Matrix;
  use Moose;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  __PACKAGE__->meta->make_immutable;
}

use Tree::Trie;

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

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

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

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

  # Inject all grid nodes into the processing queue.

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

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

      # put the dictionary into "exact match" mode.

      $d->deepsearch('exact');

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

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

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

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

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

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

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

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

# Here is where the real work starts.

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

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

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

비교를위한 아치 / 실행 정보 :

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

해당 정규식 최적화에 대한 더 많은 방해

내가 사용하는 정규식 최적화는 다중 해결 사전에는 쓸모가 없으며 다중 해결에는 사전 트리밍이 아닌 전체 사전이 필요합니다.

그러나 그것은 일회성 해결을 위해 정말 빠릅니다. (Perl 정규식은 C에 있습니다! :))

다음은 다양한 코드 추가 사항입니다.

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

           필터링되지 않은 필터링 된 필터
필터링되지 않음 8.16--94 %
필터링 된 0.464 1658 %-

_{ps : 8.16 * 200 = 27 분}

답변

문제를 두 부분으로 나눌 수 있습니다.

그리드에서 가능한 문자열을 열거하는 일종의 검색 알고리즘.
문자열이 유효한 단어인지 테스트하는 방법입니다.

이상적으로 (2)는 문자열이 유효한 단어의 접두사인지 테스트하는 방법을 포함해야합니다. 이렇게하면 검색 내용을 정리하고 전체 시간을 절약 할 수 있습니다.

Adam Rosenfield의 Trie는 (2)에 대한 솔루션입니다. 우아하고 아마도 알고리즘 전문가가 선호하는 것이지만 현대 언어와 현대 컴퓨터를 사용하면 조금 더 거칠 수 있습니다. 또한 Kent가 제안한 것처럼 그리드에 문자가없는 단어를 삭제하여 사전 크기를 줄일 수 있습니다. 다음은 파이썬입니다.

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

와; 일정한 시간 접두사 테스트. 연결 한 사전을로드하는 데 몇 초가 걸리지 만 몇 가지만 🙂 (알림 words <= prefixes)

이제 (1) 부분에서는 그래프로 생각하는 경향이 있습니다. 따라서 다음과 같은 사전을 만들겠습니다.

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

즉 graph[(x, y)], 위치에서 도달 할 수있는 좌표 세트입니다 (x, y). 또한 None모든 것에 연결될 더미 노드 를 추가 할 것입니다.

가능한 위치가 8 개이며 경계 검사를 수행해야하기 때문에 약간 어색합니다. 이에 따라 서투른 파이썬 코드가 있습니다.

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

이 코드는 또한 (x,y)해당 문자에 대한 사전 매핑 을 작성 합니다. 이를 통해 위치 목록을 단어로 바꿀 수 있습니다.

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

마지막으로 깊이 우선 검색을 수행합니다. 기본 절차는 다음과 같습니다.

검색은 특정 노드에 도착합니다.
지금까지의 경로가 단어의 일부가 될 수 있는지 확인하십시오. 그렇지 않은 경우이 분기를 더 이상 탐색하지 마십시오.
지금까지의 경로가 단어인지 확인하십시오. 그렇다면 결과 목록에 추가하십시오.
지금까지 경로의 일부가 아닌 모든 어린이를 탐색하십시오.

파이썬 :

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)

다음과 같이 코드를 실행하십시오.

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)

및 검사 res에 대한 답변을 볼 수 있습니다. 다음은 예를 들어 크기별로 정렬 된 단어 목록입니다.

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

코드는 사전을로드하는 데 (문자 그대로) 몇 초가 걸리지 만 나머지는 내 컴퓨터에서 즉시 나타납니다.

답변

Java에서의 나의 시도. 파일을 읽고 trie를 빌드하는 데 약 2 초가 걸리고 퍼즐을 풀려면 약 50ms가 걸립니다. 질문에 링크 된 사전을 사용했습니다 (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

소스 코드는 6 개의 클래스로 구성됩니다. 아래에 게시 할 것입니다 (이것이 StackOverflow에서 올바른 방법이 아닌 경우 알려주십시오).

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. 상수

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

답변

아마 당신은 아마 당신의 편지 그리드에 의해 만들어 질 수없는 단어와 일치 시키려고 대부분의 시간을 소비 할 것이라고 생각합니다. 그래서, 내가 할 첫 번째 일은 그 단계의 속도를 높이려고 노력하는 것입니다.

이를 위해, 나는 당신이보고있는 문자 변환에 의해 색인 할 수있는 가능한 “이동”의 표로 그리드를 다시 표현할 것이다.

알파벳 전체에서 각 문자에 숫자를 지정하여 시작하십시오 (A = 0, B = 1, C = 2 등).

이 예제를 보자 :

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

그리고 지금은 우리가 가진 문자의 알파벳을 사용하십시오 (보통 매번 동일한 알파벳을 사용하고 싶을 것입니다).

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

그런 다음 특정 문자 전환이 가능한지 알려주는 2D 부울 배열을 만듭니다.

     |  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

이제 단어 목록을 살펴보고 단어를 전환으로 변환하십시오.

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

그런 다음 표에서 전환을 찾아 이러한 전환이 허용되는지 확인하십시오.

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

모두 허용되면이 단어를 찾을 가능성이 있습니다.

예를 들어, 테이블의 항목이 거짓이므로 “헬멧”이라는 단어는 4 번째 전환 (m에서 e : helMEt)으로 제외 할 수 있습니다.

그리고 첫 번째 (h에서 a로) 전이가 허용되지 않기 때문에 (햄스터) 단어는 배제 할 수 있습니다 (테이블에 존재하지 않음).

지금, 당신이 제거하지 않은 아마도 거의 남지 않은 단어들에 대해, 당신이 지금하고있는 방식이나 다른 답변들에서 제안 된 것과 같이 그리드에서 실제로 단어들을 찾아보십시오. 이것은 그리드의 동일한 문자 사이에서 점프하여 발생하는 오 탐지를 피하기위한 것입니다. 예를 들어, “help”라는 단어는 표에서 허용되지만 표에서는 허용되지 않습니다.

이 아이디어에 대한 추가 성능 개선 팁 :

2D 배열을 사용하는 대신 1D 배열을 사용하고 두 번째 문자의 색인을 직접 계산하십시오. 따라서 위와 같은 12×12 배열 대신 길이가 144 인 1D 배열을 만드십시오. 그리드에 모든 문자가 표시되지 않더라도 항상 같은 알파벳 (표준 영어 알파벳의 경우 26×26 = 676×1 배열)을 사용하십시오 , 사전 단어와 일치하도록 테스트해야하는이 1D 배열로 색인을 사전 계산할 수 있습니다. 예를 들어, 위 예에서 ‘hello’의 색인은 다음과 같습니다.
```
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
```
아이디어를 3D 테이블 (1D 배열로 표현), 즉 허용되는 모든 3 글자 조합으로 확장하십시오. 이렇게하면 더 많은 단어를 즉시 제거 할 수 있으며 각 단어에 대한 배열 조회 수를 1 씩 줄입니다. ‘hello’의 경우 hel, ell, llo의 3 가지 배열 조회 만 필요합니다. 그런데이 표를 작성하는 것은 매우 빠를 것입니다. 그리드에 가능한 3 글자 이동은 400 개뿐입니다.

표에 포함해야하는 격자의 움직임 인덱스를 미리 계산하십시오. 위 예제의 경우 다음 항목을 ‘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]
.
:

또한 16 개의 항목이있는 1 차원 배열로 게임 그리드를 나타내고 3에 미리 계산 된 테이블이 있어야합니다.이 배열에 대한 인덱스를 포함합니다.

이 접근 방식을 사용하면 사전을 사전 계산하고 메모리에 이미로드 한 경우 코드가 미친 듯이 빠르게 실행될 수 있습니다.

BTW : 또 다른 좋은 방법은 게임을 제작하는 경우 이러한 종류의 작업을 백그라운드에서 즉시 실행하는 것입니다. 사용자가 앱의 타이틀 화면을보고있는 상태에서 손가락을 제자리에 놓고 “Play”를 누르는 동안 첫 번째 게임을 생성하고 해결하십시오. 그런 다음 사용자가 이전 게임을 플레이 할 때 다음 게임을 생성하고 해결하십시오. 코드를 실행하는 데 많은 시간이 필요합니다.

(이 문제가 마음에 듭니다. 아마 다음 날 언젠가 Java에서 내 제안을 구현하여 실제로 어떻게 작동하는지 확인하고 싶을 것입니다 … 일단 한 번 코드를 게시 할 것입니다.)

최신 정보:

좋아, 오늘 시간이 있었고 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();
  }
}

결과는 다음과 같습니다.

원래 질문 (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

원래 질문 (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

다음 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

그것은 이것을 준다 :

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

이를 위해 원래 질문의 링크가 더 이상 작동하지 않기 때문에 TWL06 토너먼트 글자 맞추기 단어 목록을 사용했습니다 . 이 파일은 1.85MB이므로 조금 더 짧습니다. 그리고buildDictionary 함수는 3 자 미만의 모든 단어를 버립니다.

이것의 성능에 대한 몇 가지 관찰은 다음과 같습니다.

Victor Nicollet의 OCaml 구현에 대해보고 된 성능보다 약 10 배 느립니다. 이것은 다른 알고리즘, 그가 사용한 짧은 사전, 코드가 컴파일되어 Java 가상 머신에서 실행된다는 사실 또는 우리 컴퓨터의 성능 (WinXP를 실행하는 Intel Q6600 @ 2.4MHz)에 의해 발생합니다. 모르겠어요 그러나 원래 질문의 끝에 인용 된 다른 구현의 결과보다 훨씬 빠릅니다. 따라서이 알고리즘이 트라이 사전보다 우월한 지 여부는 알지 못합니다.
사용 된 테이블 방법 checkWordTriplets()은 실제 답변과 매우 유사합니다. 단 1 3-5 단어가 실패합니다 통과 checkWords()테스트 (참조 후보의 수 대 실제 단어의 수 위).
위에서 볼 수없는 것 :이 checkWordTriplets()함수는 약 3.65ms가 걸리므로 검색 프로세스에서 완전히 지배적입니다. 이 checkWords()함수는 나머지 0.05-0.20 ms를 거의 차지합니다.
checkWordTriplets()함수 의 실행 시간은 사전 크기에 선형 적으로 의존하며 보드 크기 와 거의 독립적입니다!
의 실행 시간은 checkWords()보드 크기와에 의해 배제되지 않은 단어 수 에 따라 다릅니다 checkWordTriplets().
checkWords()위 의 구현은 내가 생각해 낸 가장 멍청한 첫 번째 버전입니다. 기본적으로 전혀 최적화되지 않았습니다. 그러나 checkWordTriplets()응용 프로그램의 전체 성능과 관련이 없으므로 그것에 대해 걱정하지 않았습니다. 그러나 보드 크기가 커지면이 기능은 점점 느려지고 결국 문제가 시작됩니다. 그런 다음 최적화해야합니다.
이 코드의 장점 중 하나는 유연성입니다.
- 보드 크기를 쉽게 변경할 수 있습니다 : 업데이트 라인 10 및 String 배열이로 전달되었습니다 initializeBoard().
- 더 크고 다른 알파벳을 지원할 수 있으며 성능 오버 헤드없이 ‘Qu’를 하나의 문자로 처리하는 것과 같은 것을 처리 할 수 있습니다. 이렇게하려면 9 행과 문자가 숫자로 변환되는 두 곳을 업데이트해야합니다 (현재 ASCII 값에서 65를 빼서)

좋아, 그러나 지금 까지이 게시물은 충분히 길다라고 생각합니다. 나는 당신이 가질 수있는 질문에 분명히 대답 할 수 있지만 의견으로 옮깁니다.

답변

놀랍게도, 아무도 이것의 PHP 버전을 시도하지 않았습니다.

이것은 John Fouhy의 Python 솔루션의 작동하는 PHP 버전입니다.

나는 다른 사람들의 대답에서 몇 가지 조언을 얻었지만, 이것은 대부분 John에서 복사 한 것입니다.

$boggle = "fxie
           amlo
           ewbx
           astu";

$alphabet = str_split(str_replace(array("\n", " ", "\r"), "", strtolower($boggle)));
$rows = array_map('trim', explode("\n", $boggle));
$dictionary = file("C:/dict.txt");
$prefixes = array(''=>'');
$words = array();
$regex = '/[' . implode('', $alphabet) . ']{3,}$/S';
foreach($dictionary as $k=>$value) {
    $value = trim(strtolower($value));
    $length = strlen($value);
    if(preg_match($regex, $value)) {
        for($x = 0; $x < $length; $x++) {
            $letter = substr($value, 0, $x+1);
            if($letter == $value) {
                $words[$value] = 1;
            } else {
                $prefixes[$letter] = 1;
            }
        }
    }
}

$graph = array();
$chardict = array();
$positions = array();
$c = count($rows);
for($i = 0; $i < $c; $i++) {
    $l = strlen($rows[$i]);
    for($j = 0; $j < $l; $j++) {
        $chardict[$i.','.$j] = $rows[$i][$j];
        $children = array();
        $pos = array(-1,0,1);
        foreach($pos as $z) {
            $xCoord = $z + $i;
            if($xCoord < 0 || $xCoord >= count($rows)) {
                continue;
            }
            $len = strlen($rows[0]);
            foreach($pos as $w) {
                $yCoord = $j + $w;
                if(($yCoord < 0 || $yCoord >= $len) || ($z == 0 && $w == 0)) {
                    continue;
                }
                $children[] = array($xCoord, $yCoord);
            }
        }
        $graph['None'][] = array($i, $j);
        $graph[$i.','.$j] = $children;
    }
}

function to_word($chardict, $prefix) {
    $word = array();
    foreach($prefix as $v) {
        $word[] = $chardict[$v[0].','.$v[1]];
    }
    return implode("", $word);
}

function find_words($graph, $chardict, $position, $prefix, $prefixes, &$results, $words) {
    $word = to_word($chardict, $prefix);
    if(!isset($prefixes[$word])) return false;

    if(isset($words[$word])) {
        $results[] = $word;
    }

    foreach($graph[$position] as $child) {
        if(!in_array($child, $prefix)) {
            $newprefix = $prefix;
            $newprefix[] = $child;
            find_words($graph, $chardict, $child[0].','.$child[1], $newprefix, $prefixes, $results, $words);
        }
    }
}

$solution = array();
find_words($graph, $chardict, 'None', array(), $prefixes, $solution);
print_r($solution);

여기입니다 라이브 링크를 당신이 그것을 시도하려는 경우. 로컬 컴퓨터에서는 ~ 2 초가 걸리지 만 웹 서버에서는 ~ 5 초가 걸립니다. 두 경우 모두 매우 빠르지 않습니다. 그러나 여전히 끔찍하기 때문에 시간을 크게 줄일 수 있다고 상상할 수 있습니다. 이를 달성하는 방법에 대한 모든 조언을 부탁드립니다. PHP의 튜플 부족으로 인해 좌표가 이상 해졌고 도대체 무슨 일인지 이해할 수 없었습니다.

편집 : 몇 가지 수정으로 인해 로컬로 1 초 미만이 소요됩니다.