문자 행렬에서 가능한 단어 목록을 찾는 방법 [Boggle Solver]
https://stackoverflow.com/questions/746082
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
최근에 저는 iPhone에서 Scramble이라는 게임을 하고 있습니다.여러분 중 일부는 이 게임을 Boggle로 알고 계실 것입니다.기본적으로 게임이 시작되면 다음과 같은 문자 행렬이 표시됩니다.
F X I E
A M L O
E W B X
A S T U
게임의 목표는 글자를 연결하여 만들 수 있는 단어를 최대한 많이 찾는 것입니다.어떤 문자로든 시작할 수 있으며 그 주위의 모든 문자는 공정한 게임입니다. 그리고 다음 문자로 넘어가면 해당 문자를 둘러싼 모든 문자가 공정한 게임입니다. 이전에 사용한 문자를 제외하고.예를 들어 위의 그리드에서 다음 단어를 생각해 낼 수 있습니다. LOB, TUX, SEA, FAME, 등.단어는 3자 이상이어야 하며 NxN자 이하여야 합니다. 이 게임에서는 16자이지만 일부 구현에서는 다를 수 있습니다.이 게임은 재미있고 중독성이 있지만, 저는 별로 능숙하지 않은 것 같기 때문에 가능한 최고의 단어를 제공하는 프로그램을 만들어 약간의 속임수를 쓰고 싶었습니다(단어가 길수록 더 많은 포인트를 얻습니다).
(원천: boggled.org)
불행하게도 나는 알고리즘이나 효율성 등을 잘 다루지 못합니다.첫 번째 시도에서는 사전을 사용합니다. 이것과 같은 (~2.3MB) 사전 항목과의 조합을 일치시키려는 선형 검색을 수행합니다.이것은 매우 가능한 단어를 찾는 데 오랜 시간이 걸리고 라운드당 2분밖에 주어지지 않기 때문에 충분하지 않습니다.
Stackoverflowers가 더 효율적인 솔루션을 찾을 수 있는지 알아보고 싶습니다.저는 주로 Big 3 P를 사용하는 솔루션을 찾고 있습니다.Python, PHP, Perl 등 Java나 C++를 사용하는 것도 좋지만 속도가 필수이기 때문에 좋습니다.
현재 솔루션:
해결책
내 대답은 여기 다른 사람들처럼 작동하지만 사전을 더 빨리 설정하는 것보다 다른 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 : 켄트 프레드릭의 Perl 솔루션이 더 빠른 이유가 궁금했습니다. 캐릭터 세트 대신 일반 표현 일치를 사용하는 것이 밝혀졌습니다. 파이썬에서 속도를 두 배로 늘리는 것에 대해 동일하게하는 것은 속도를 두 배로 늘립니다.
다른 팁
가장 빠른 솔루션은 아마도 사전을 트리. 그런 다음 트리플렛 대기열을 만듭니다.엑스, 와이, 에스), 큐의 각 요소가 접두사에 해당합니다. 에스 그리드에서 철자를받을 수있는 단어의 위치로 끝납니다.엑스, 와이). 대기열을 초기화하십시오 N 엑스 N 요소 (여기서 N 그리드의 각 정사각형마다 하나의 요소 인 그리드의 크기)입니다. 그런 다음 알고리즘은 다음과 같이 진행됩니다.
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
사전을 트리에 저장하는 경우 에스+씨 단어의 단어 또는 접두사는 일정한 시간에 수행 할 수 있습니다 (트리의 현재 노드에 대한 포인터와 같은 각 대기열 기준에 추가 메타 데이터를 유지하면이 알고리즘의 실행 시간은 O입니다. (철자가 될 수있는 단어 수).
편집하다 방금 코딩 한 Python의 구현은 다음과 같습니다.
#!/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 ','wa ','wa ','bo ','bu ' , 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', '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 ','waw ','waw ','wem ','wea ','wea ','we ' , 'waw', 'wae', 'bob', 'bob', 'blo', 'bub', 'bub', 'ast', 'ase', 'asa', 'awl', 'awa', 'awe', ' awa ','aes ','swa ','swa ','sew ','sea ','sea ','saw ','saw ','tux ','tub ','tut ','twa ','twa ' , 'tst', 'utu', 'fama', 'fame', 'ixil', 'imam', 'amli', 'amil', 'ambo', 'axil', 'axle', 'mimi', ' Mima ','Mime ','Milo ','Mile ','Mewl ','Mese ','Mesa ','Lolo ','Lobo ','Lima ','Lime ','Limb ','Lile ' , 'Oime', 'Oleo', 'Olio', 'Oboe', 'Obol', 'Emim', 'Emil', 'East', 'Eass', 'wawa', 'wawa', 'wawa', ' Weam ','West ','wese ','wast ','wase ' , 'wawa', 'wawa', 'book', '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'
참고 :이 프로그램은 1 글자 단어를 출력하거나 단어 길이로 필터를 전혀 출력하지 않습니다. 추가하기 쉽지만 실제로 문제와 관련이 없습니다. 또한 여러 가지 방법으로 철자를받을 수 있다면 일부 단어를 여러 번 출력합니다. 주어진 단어가 여러 가지 방식으로 철자를받을 수 있다면 (최악의 경우 : 그리드의 모든 문자는 동일하고 (예 : 'a') 'aaaaaaaaaaa'와 같은 단어가 사전에 있습니다). . 중복을 필터링하고 정렬은 알고리즘이 완료된 후에는 사소한 일입니다.
사전 속도를 높이려면 사전 비교를 미리 줄이기 위해 할 수있는 일반적인 변환/프로세스가 하나 있습니다.
위의 그리드에는 16 자만 포함되며 일부는 복제 된 문자가 포함되어 있으므로, 달성 할 수없는 문자가있는 항목을 필터링하여 사전의 총 키 수를 크게 줄일 수 있습니다.
나는 이것이 명백한 최적화라고 생각했지만 아무도 그것을 언급하지 않았다.
입력 패스 중에 간단히 20 만 키 사전에서 단지 2,000 키로 줄였습니다. 이것은 최소한 메모리 오버 헤드를 줄이고 메모리가 무한히 빠르지 않기 때문에 속도 증가에 매핑해야합니다.
Perl 구현
내 구현은 유효성뿐만 아니라 추출 된 모든 문자열의 정확한 경로를 알 수 있다는 점을 중요하게 생각하기 때문에 약간 무겁습니다.
또한 이론적으로 구멍이있는 그리드가 작동하도록 허용하는 몇 가지 적응이 있고 크기가 다른 라인을 가진 그리드가 있습니다 (입력을 올바르게 얻고 어떻게 든 일치한다고 가정합니다).
초기 필터는 가장 중요합니다 중요한 내 응용 프로그램의 병목 현상은 앞에서 의심되는 것처럼 라인이 1.5s에서 7.5s로 부풀어 오른다고 언급했다.
실행 후 모든 단일 자리가 자신의 유효한 단어에 있다고 생각하는 것처럼 보이지만 사전 파일의 작동 방식 때문입니다.
약간 부풀어 오르지 만 적어도 재사용 나무 :: 트리 CPAN에서
그 중 일부는 기존 구현에서 부분적으로 영감을 받았으며, 일부는 이미 염두에 두었습니다.
건설적인 비판과 그것이 개선 될 수있는 방법을 환영 할 수 있습니다 ( /나 메모 그는 결코 Boggle 솔버를 위해 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% ==============================
그 성과 최적화에 대한 더 많은 사람들
내가 사용하는 Regex 최적화는 다중 발산 사전에 쓸모가 없으며, 다중 발작의 경우 사전 트리밍이 아닌 전체 사전을 원할 것입니다.
그러나 일회성 해결이 실제로 빠릅니다. (Perl Regex는 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');
}
});
}
s/iter unfiltered filtered unfiltered 8.16 -- -94% filtered 0.464 1658% --
추신 : 8.16 * 200 = 27 분.
문제를 두 조각으로 나눌 수 있습니다.
- 그리드에서 가능한 문자열을 열거하는 일종의 검색 알고리즘.
- 문자열이 유효한 단어인지 테스트하는 방법.
이상적으로는 (2) 문자열이 유효한 단어의 접두사인지 테스트하는 방법을 포함해야합니다.이를 통해 검색을 정리하고 전체 시간을 절약 할 수 있습니다.
Adam Rosenfield의 트리는 (2)에 대한 해결책입니다. 우아하고 아마도 당신의 알고리즘 전문가가 선호하는 것일 것입니다. 그러나 현대 언어와 현대 컴퓨터를 사용하면 우리는 약간 더 게으를 수 있습니다. 또한 켄트가 제안한 바와 같이, 우리는 그리드에 문자가없는 단어를 버려서 사전 크기를 줄일 수 있습니다. 파이썬은 다음과 같습니다.
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']
코드는 사전을로드하는 데 몇 초가 걸리지 만 나머지는 내 컴퓨터에 즉시 있습니다.
자바에서의 나의 시도. 파일을 읽고 트리를 만들려면 약 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.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;
}
}
나는 아마도 당신의 문자 격자로 구성할 수 없는 단어를 일치시키려고 노력하는 데 대부분의 시간을 보낼 것이라고 생각합니다.그래서 제가 가장 먼저 할 일은 그 단계의 속도를 높이려고 노력하는 것입니다. 그렇게 하면 대부분의 목표에 도달할 수 있을 것입니다.
이를 위해 나는 보고 있는 문자 전환으로 색인을 생성하는 가능한 "이동" 테이블로 그리드를 다시 표현하겠습니다.
각 문자에 전체 알파벳의 숫자를 할당하는 것부터 시작하세요(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
모두 허용한다면 이 단어가 나올 가능성도 있습니다.
예를 들어 "helmet"이라는 단어는 네 번째 전환(m에서 e로)에서 제외될 수 있습니다.helMEt), 테이블의 해당 항목이 거짓이기 때문입니다.
그리고 hamster라는 단어는 배제될 수 있습니다. 첫 번째(h에서 a로) 전환이 허용되지 않기 때문입니다(테이블에 존재하지도 않습니다).
이제 제거하지 않은 남은 단어 중 극소수에 대해 지금 수행하는 방식이나 여기의 다른 답변에서 제안한 대로 실제로 그리드에서 해당 단어를 찾아보십시오.이는 그리드에서 동일한 문자 사이의 점프로 인해 발생하는 잘못된 긍정을 방지하기 위한 것입니다.예를 들어 "help"라는 단어는 테이블에서는 허용되지만 그리드에서는 허용되지 않습니다.
이 아이디어에 대한 추가 성능 개선 팁은 다음과 같습니다.
2D 배열을 사용하는 대신 1D 배열을 사용하고 두 번째 문자의 인덱스를 직접 계산하면 됩니다.따라서 위와 같은 12x12 배열 대신 길이가 144인 1D 배열을 만듭니다.그런 다음 항상 동일한 알파벳을 사용하는 경우(예:표준 영어 알파벳의 경우 26x26 = 676x1 배열), 모든 문자가 그리드에 표시되지 않더라도 사전 단어와 일치하는지 테스트해야 하는 이 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'의 경우 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개로 미리 계산합니다.이 배열에 대한 인덱스를 포함합니다.
이 접근 방식을 사용하면 사전이 미리 계산되어 있고 이미 메모리에 로드되어 있는 경우 코드가 미친 듯이 빠르게 실행될 수 있다고 확신합니다.
지금:게임을 만드는 경우 또 다른 좋은 점은 이러한 종류의 작업을 백그라운드에서 즉시 실행하는 것입니다.사용자가 앱의 제목 화면을 보면서 손가락을 위치에 놓고 "재생"을 누르는 동안 첫 번째 게임을 생성하고 해결하기 시작하세요.그런 다음 사용자가 이전 게임을 플레이하면서 다음 게임을 생성하고 해결합니다.그러면 코드를 실행하는 데 많은 시간이 걸릴 것입니다.
(나는 이 문제를 좋아하므로 실제로 어떻게 작동하는지 확인하기 위해 다음 날 언젠가 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
다음 5x5 그리드의 경우:
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입니다)인지, 모르겠습니다.그러나 원래 질문 끝에 인용된 다른 구현의 결과보다 훨씬 빠릅니다.따라서 이 알고리즘이 trie 사전보다 우수한지 여부는 현재로서는 알 수 없습니다.
에서 사용되는 테이블 방법
checkWordTriplets()실제 답변에 대한 매우 좋은 근사치를 산출합니다.3~5개의 단어 중 1개만 통과하면 실패합니다.checkWords()테스트(참조 후보자 수 대 실제 단어 수 위에).위에서 볼 수 없는 것:그만큼
checkWordTriplets()기능은 약 3.65ms가 걸리므로 검색 프로세스에서 완전히 지배적입니다.그만큼checkWords()기능은 나머지 0.05-0.20ms를 거의 차지합니다.실행 시간
checkWordTriplets()함수는 사전 크기에 선형적으로 의존하며 사실상 보드 크기에 관계없이!실행 시간
checkWords()보드 크기와 배제되지 않는 단어 수에 따라 다릅니다.checkWordTriplets().그만큼
checkWords()위의 구현은 내가 생각해낸 가장 멍청한 첫 번째 버전입니다.기본적으로 전혀 최적화되어 있지 않습니다.그러나 비교하면checkWordTriplets()애플리케이션의 전체 성능과는 관련이 없으므로 걱정하지 않았습니다. 하지만, 보드 크기가 커지면 이 기능은 점점 느려지고 결국 중요해지기 시작합니다.그렇다면 최적화도 필요합니다.이 코드의 좋은 점 중 하나는 유연성입니다.
- 보드 크기를 쉽게 변경할 수 있습니다.10행과 전달된 문자열 배열을 업데이트합니다.
initializeBoard(). - 더 크거나 다른 알파벳을 지원할 수 있으며 성능 오버헤드 없이 'Qu'를 하나의 문자로 처리하는 것과 같은 작업을 처리할 수 있습니다.이렇게 하려면 9행과 문자가 숫자로 변환되는 두 곳을 업데이트해야 합니다(현재는 단순히 ASCII 값에서 65를 빼면 됩니다).
- 보드 크기를 쉽게 변경할 수 있습니다.10행과 전달된 문자열 배열을 업데이트합니다.
좋아, 하지만 지금쯤이면 이 게시물이 너무 길어질 것 같아.여러분이 갖고 있는 모든 질문에 확실히 답해드릴 수 있지만, 그 내용은 댓글로 옮겨보겠습니다.
놀랍게도 아무도 이것의 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);
여기에 있습니다 라이브 링크 당신이 그것을 시도하고 싶다면. 로컬 컴퓨터에서 ~ 2s가 걸리지 만 웹 서버에서 ~ 5s가 필요합니다. 두 경우 모두 빠르지 않습니다. 그럼에도 불구하고, 그것은 매우 끔찍한 일이므로 시간이 크게 줄어들 수 있다고 상상할 수 있습니다. 달성하는 방법에 대한 지침은 감사 할 것입니다. PHP의 튜플 부족은 좌표를 이상하게 만들었고 도대체 무슨 일이 일어나고 있는지 이해할 수 없다는 것은 전혀 도움이되지 않았습니다.
편집하다: 몇 가지 수정으로 로컬에서 1 초 미만이 걸립니다.
VB에 관심이 없습니까? :) 나는 저항 할 수 없었다. 나는 여기에 제시된 많은 솔루션과 다르게 이것을 해결했습니다.
내 시간은 다음과 같습니다.
- 사전과 단어 접두사를 해시 가능에 넣습니다 : .5 ~ 1 초.
- 단어 찾기 : 평균 10 밀리 초 미만.
편집 : 웹 호스트 서버의 사전로드 시간은 내 홈 컴퓨터보다 약 1 ~ 1.5 초 더 길게 실행됩니다.
서버의 부하로 시간이 얼마나 나빠질 지 모르겠습니다.
.NET의 웹 페이지로 솔루션을 작성했습니다. myvrad.com/boggle
원래 질문에 참조 된 사전을 사용하고 있습니다.
글자는 한 마디로 재사용되지 않습니다. 3 자 이상의 단어 만 발견됩니다.
나는 트리 대신 모든 독특한 단어 접두사와 단어의 해시 가능을 사용하고 있습니다. 나는 Trie 's에 대해 몰랐기 때문에 거기에서 무언가를 배웠습니다. 완전한 단어 외에 단어의 접두사 목록을 작성한다는 아이디어는 마침내 내 시간을 존경할만한 숫자로 내렸다.
자세한 내용은 코드 주석을 읽으십시오.
코드는 다음과 같습니다.
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
문제 진술을 보자 마자 "트리"를 생각했습니다. 그러나 다른 여러 포스터가 그 접근법을 사용하는 것으로 보았을 때, 나는 다른 접근법을 다른 방법으로 찾았습니다. 아아, 트리 접근법이 더 잘 수행됩니다. 나는 내 컴퓨터에서 Kent의 Perl 솔루션을 실행했는데 0.31 내 사전 파일을 사용하도록 적응 한 후 실행하는 데 초. 내 자신의 Perl 구현이 필요합니다 0.54 실행하는 초.
이것은 내 접근 방식이었습니다.
법적 전환을 모델링하기 위해 전환 해시를 만듭니다.
16^3 가능한 3 글자 조합을 모두 반복하십시오.
- 루프에서 불법 전환을 제외하고 동일한 광장으로의 반복 방문. 모든 법적 3 글자 시퀀스를 형성하고 해시에 보관하십시오.
그런 다음 사전의 모든 단어를 루프하십시오.
- 너무 길거나 짧은 단어를 제외하십시오
- 각 단어의 3 글자 창을 각 단어에서 밀어 넣고 2 단계에서 3 글자 콤보 중 하나인지 확인하십시오. 실패한 단어를 제외하십시오. 이것은 대부분의 비 일치를 제거합니다.
- 아직 제거되지 않은 경우 재귀 알고리즘을 사용하여 퍼즐을 통해 경로를 만들어 단어를 형성 할 수 있는지 확인하십시오. (이 부분은 느리지 만 드물게 불립니다.)
내가 찾은 단어를 인쇄하십시오.
3 글자와 4 글자 시퀀스를 시도했지만 4 글자 시퀀스는 프로그램의 속도를 늦췄습니다.
내 코드에서는 사전에/usr/share/dict/words를 사용합니다. 그것은 Mac OS X 및 많은 UNIX 시스템에 기본으로 제공됩니다. 원하는 경우 다른 파일을 사용할 수 있습니다. 다른 퍼즐을 깨뜨리려면 변수 @puzzle을 변경하십시오. 이것은 더 큰 행렬에 쉽게 적응하기 쉽습니다. %전환 해시 및 %법률 변환 해시를 변경하면됩니다.
이 솔루션의 강점은 코드가 짧고 데이터 구조가 간단하다는 것입니다.
다음은 PERL 코드입니다 (너무 많은 글로벌 변수를 사용합니다).
#!/usr/bin/perl
use Time::HiRes qw{ time };
sub readFile($);
sub findAllPrefixes($);
sub isWordTraceable($);
sub findWordsInPuzzle(@);
my $startTime = time;
# Puzzle to solve
my @puzzle = (
F, X, I, E,
A, M, L, O,
E, W, B, X,
A, S, T, U
);
my $minimumWordLength = 3;
my $maximumPrefixLength = 3; # I tried four and it slowed down.
# Slurp the word list.
my $wordlistFile = "/usr/share/dict/words";
my @words = split(/\n/, uc(readFile($wordlistFile)));
print "Words loaded from word list: " . scalar @words . "\n";
print "Word file load time: " . (time - $startTime) . "\n";
my $postLoad = time;
# Define the legal transitions from one letter position to another.
# Positions are numbered 0-15.
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
my %transitions = (
-1 => [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
0 => [1,4,5],
1 => [0,2,4,5,6],
2 => [1,3,5,6,7],
3 => [2,6,7],
4 => [0,1,5,8,9],
5 => [0,1,2,4,6,8,9,10],
6 => [1,2,3,5,7,9,10,11],
7 => [2,3,6,10,11],
8 => [4,5,9,12,13],
9 => [4,5,6,8,10,12,13,14],
10 => [5,6,7,9,11,13,14,15],
11 => [6,7,10,14,15],
12 => [8,9,13],
13 => [8,9,10,12,14],
14 => [9,10,11,13,15],
15 => [10,11,14]
);
# Convert the transition matrix into a hash for easy access.
my %legalTransitions = ();
foreach my $start (keys %transitions) {
my $legalRef = $transitions{$start};
foreach my $stop (@$legalRef) {
my $index = ($start + 1) * (scalar @puzzle) + ($stop + 1);
$legalTransitions{$index} = 1;
}
}
my %prefixesInPuzzle = findAllPrefixes($maximumPrefixLength);
print "Find prefixes time: " . (time - $postLoad) . "\n";
my $postPrefix = time;
my @wordsFoundInPuzzle = findWordsInPuzzle(@words);
print "Find words in puzzle time: " . (time - $postPrefix) . "\n";
print "Unique prefixes found: " . (scalar keys %prefixesInPuzzle) . "\n";
print "Words found (" . (scalar @wordsFoundInPuzzle) . ") :\n " . join("\n ", @wordsFoundInPuzzle) . "\n";
print "Total Elapsed time: " . (time - $startTime) . "\n";
###########################################
sub readFile($) {
my ($filename) = @_;
my $contents;
if (-e $filename) {
# This is magic: it opens and reads a file into a scalar in one line of code.
# See http://www.perl.com/pub/a/2003/11/21/slurp.html
$contents = do { local( @ARGV, $/ ) = $filename ; <> } ;
}
else {
$contents = '';
}
return $contents;
}
# Is it legal to move from the first position to the second? They must be adjacent.
sub isLegalTransition($$) {
my ($pos1,$pos2) = @_;
my $index = ($pos1 + 1) * (scalar @puzzle) + ($pos2 + 1);
return $legalTransitions{$index};
}
# Find all prefixes where $minimumWordLength <= length <= $maxPrefixLength
#
# $maxPrefixLength ... Maximum length of prefix we will store. Three gives best performance.
sub findAllPrefixes($) {
my ($maxPrefixLength) = @_;
my %prefixes = ();
my $puzzleSize = scalar @puzzle;
# Every possible N-letter combination of the letters in the puzzle
# can be represented as an integer, though many of those combinations
# involve illegal transitions, duplicated letters, etc.
# Iterate through all those possibilities and eliminate the illegal ones.
my $maxIndex = $puzzleSize ** $maxPrefixLength;
for (my $i = 0; $i < $maxIndex; $i++) {
my @path;
my $remainder = $i;
my $prevPosition = -1;
my $prefix = '';
my %usedPositions = ();
for (my $prefixLength = 1; $prefixLength <= $maxPrefixLength; $prefixLength++) {
my $position = $remainder % $puzzleSize;
# Is this a valid step?
# a. Is the transition legal (to an adjacent square)?
if (! isLegalTransition($prevPosition, $position)) {
last;
}
# b. Have we repeated a square?
if ($usedPositions{$position}) {
last;
}
else {
$usedPositions{$position} = 1;
}
# Record this prefix if length >= $minimumWordLength.
$prefix .= $puzzle[$position];
if ($prefixLength >= $minimumWordLength) {
$prefixes{$prefix} = 1;
}
push @path, $position;
$remainder -= $position;
$remainder /= $puzzleSize;
$prevPosition = $position;
} # end inner for
} # end outer for
return %prefixes;
}
# Loop through all words in dictionary, looking for ones that are in the puzzle.
sub findWordsInPuzzle(@) {
my @allWords = @_;
my @wordsFound = ();
my $puzzleSize = scalar @puzzle;
WORD: foreach my $word (@allWords) {
my $wordLength = length($word);
if ($wordLength > $puzzleSize || $wordLength < $minimumWordLength) {
# Reject word as too short or too long.
}
elsif ($wordLength <= $maximumPrefixLength ) {
# Word should be in the prefix hash.
if ($prefixesInPuzzle{$word}) {
push @wordsFound, $word;
}
}
else {
# Scan through the word using a window of length $maximumPrefixLength, looking for any strings not in our prefix list.
# If any are found that are not in the list, this word is not possible.
# If no non-matches are found, we have more work to do.
my $limit = $wordLength - $maximumPrefixLength + 1;
for (my $startIndex = 0; $startIndex < $limit; $startIndex ++) {
if (! $prefixesInPuzzle{substr($word, $startIndex, $maximumPrefixLength)}) {
next WORD;
}
}
if (isWordTraceable($word)) {
# Additional test necessary: see if we can form this word by following legal transitions
push @wordsFound, $word;
}
}
}
return @wordsFound;
}
# Is it possible to trace out the word using only legal transitions?
sub isWordTraceable($) {
my $word = shift;
return traverse([split(//, $word)], [-1]); # Start at special square -1, which may transition to any square in the puzzle.
}
# Recursively look for a path through the puzzle that matches the word.
sub traverse($$) {
my ($lettersRef, $pathRef) = @_;
my $index = scalar @$pathRef - 1;
my $position = $pathRef->[$index];
my $letter = $lettersRef->[$index];
my $branchesRef = $transitions{$position};
BRANCH: foreach my $branch (@$branchesRef) {
if ($puzzle[$branch] eq $letter) {
# Have we used this position yet?
foreach my $usedBranch (@$pathRef) {
if ($usedBranch == $branch) {
next BRANCH;
}
}
if (scalar @$lettersRef == $index + 1) {
return 1; # End of word and success.
}
push @$pathRef, $branch;
if (traverse($lettersRef, $pathRef)) {
return 1; # Recursive success.
}
else {
pop @$pathRef;
}
}
}
return 0; # No path found. Failed.
}
나는 내가 슈퍼 늦었다는 것을 알고 있지만 얼마 전에 이것들 중 하나를 만들었습니다. PHP - 재미를 위해 ...
http://www.lostsockdesign.com.au/sandbox/boggle/index.php?letters=fxieamloewbxastu75 단어 (133 점)를 발견했습니다 0.90108 초
F.........X..I..............E...............
A......................................M..............................L............................O...............................
E....................W............................B..........................X
A..................S..................................................T.................U....
프로그램이 실제로 수행하는 일에 대한 정보를 제공합니다. 각 문자는 각자의 패턴을 통해보기 시작하는 곳입니다. 그것이 시도한 길을 보여줍니다. 더 '.' 더 검색 한 것이 더 있습니다.
코드를 원한다면 알려주세요 ... PHP와 HTML의 끔찍한 혼합으로 하루의 빛을 보지 못했기 때문에 여기에 게시하지 않습니다.
나는 3 개월 동안 10 개의 최고의 포인트 밀도가 높은 5x5 boggle 보드 문제에 대한 솔루션을 사용했습니다.
문제는 이제 5 개의 웹 페이지에 전체 공개로 해결되고 배치되었습니다. 질문으로 저에게 연락하십시오.
보드 분석 알고리즘은 명시 적 스택을 사용하여 의사가 직접 아동 정보를 갖춘 지시 된 acyclic Word 그래프와 타임 스탬프 추적 메커니즘을 통해 보드 사각형을 통과시킵니다. 이것은 세계에서 가장 진보 된 사전 데이터 구조 일 수 있습니다.
이 계획은 쿼드 코어에서 초당 약 10,000 개의 매우 좋은 보드를 평가합니다. (9500+ 포인트)
부모 웹 페이지 :
deepsearch.c- http://www.pathcom.com/~vadco/deep.html
구성 요소 웹 페이지 :
최적의 스코어 보드 - http://www.pathcom.com/~vadco/binary.html
고급 사전 구조 - http://www.pathcom.com/~vadco/adtdawg.html
보드 분석 알고리즘 - http://www.pathcom.com/~vadco/guns.html
병렬 배치 처리 - http://www.pathcom.com/~vadco/parallel.html
-이 포괄적 인 작업은 최선을 요구하는 사람에게만 관심을 가질 것입니다.
검색 알고리즘이 검색이 계속됨에 따라 단어 목록을 지속적으로 줄입니까?
예를 들어, 위의 검색에는 단어가 시작할 수있는 13 개의 글자 만 있습니다 (효과적으로 시작 문자의 절반으로 줄어 듭니다).
더 많은 문자 순열을 추가하면 사용 가능한 단어 세트가 더 줄어들어 검색이 줄어 듭니다.
나는 거기서 시작할 것이다.
나는 완전한 솔루션에 대해 더 많은 생각을해야했지만 편리한 최적화로서, 나는 그것이 모든 것을 기준으로 Digrams and Trigram (2 및 3 글자 조합)의 주파수 테이블을 사전 컴퓨팅 할 가치가 있는지 궁금합니다. 사전의 단어를 사용하여 검색의 우선 순위를 정하는 데 사용하십시오. 나는 단어의 시작 문자와 함께 갈 것입니다. 따라서 사전이 "인도", "물", "극단"및 "특별한"이라는 단어가 포함되어 있다면 미리 컴퓨터 테이블이 다음과 같습니다.
'IN': 1
'WA': 1
'EX': 2
그런 다음 공통성의 순서 대로이 Digrams를 검색하십시오 (첫 번째 Ex, wa/in)
먼저 C# 언어 디자이너 중 한 명이 관련 문제를 해결하는 방법을 읽으십시오.http://blogs.msdn.com/ericlippert/archive/2009/02/04/a-nasality-t ancilefan-for-the-sultana-analyst.aspx.
그와 마찬가지로, 당신은 사전으로 시작할 수 있으며, 알파벳순으로 정렬 된 문자 배열에서 사전을 만들어 그 글자에서 철자를 할 수있는 단어 목록까지 사전을 만들 수 있습니다.
다음으로 보드에서 가능한 단어를 만들고 찾아보십시오. 나는 그것이 당신을 꽤 멀리 데려 갈 것이라고 생각하지만, 속도를 높일 수있는 더 많은 트릭이 있습니다.
나는 단어에 따라 글자 나무를 만드는 것이 좋습니다. 나무는 다음과 같은 문자 structs로 구성됩니다.
letter: char
isWord: boolean
그런 다음 각 깊이가 새 문자를 추가 할 때 나무를 쌓습니다. 다시 말해, 첫 번째 레벨에는 알파벳이있을 것입니다. 그런 다음 각 나무에서 모든 단어를 철자 할 때까지 또 다른 26 개의 항목이 또 다른 26 개 항목이있을 것입니다. 이 구문 분석 된 나무에 매달리면 모든 가능한 답변을 더 빨리 찾아 볼 수 있습니다.
이 구문 분석 된 나무를 사용하면 솔루션을 매우 빠르게 찾을 수 있습니다. 의사 코드는 다음과 같습니다.
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.
이것은 약간의 역동적 인 프로그래밍으로 인해 발생할 수 있습니다. 예를 들어, 샘플에서 두 개의 'A는'E '와'w '옆에 있으며 (그 시점에서) 동일합니다. 나는 이것에 대한 코드를 실제로 철자 할 시간이 충분하지 않지만 아이디어를 수집 할 수 있다고 생각합니다.
또한 "Boggle Solver"에 대한 Google이라면 다른 솔루션을 찾을 수 있다고 확신합니다.
재미를 위해, 나는 Bash에서 하나를 구현했습니다. 매우 빠르지는 않지만 합리적입니다.
아주 웃긴. 나는 같은 게임으로 인해 며칠 전에 거의 같은 질문을 게시했습니다! 그러나 Google을 검색했기 때문에 나는하지 않았습니다 Boggle Solver Python 그리고 내가 원할 수있는 모든 답변을 얻었습니다.
이 질문에 대한 시간이 왔다 갔다는 것을 알고 있지만 솔버를 직접 작업하고 인터넷 검색 중에 이 문제를 우연히 발견했기 때문에 다른 질문과 조금 다른 것 같아서 내 참조를 게시해야 한다고 생각했습니다.
나는 게임 보드에 플랫 배열을 사용하고 보드의 각 문자에서 재귀적 검색을 수행하고 유효한 이웃에서 유효한 이웃으로 이동하며 현재 문자 목록이 인덱스의 유효한 접두사인 경우 검색을 확장하기로 결정했습니다.현재 단어의 개념을 순회하는 동안 단어를 구성하는 문자가 아닌 보드에 색인 목록이 표시됩니다.색인을 확인할 때 색인이 문자로 변환되어 확인이 완료됩니다.
인덱스는 trie와 약간 비슷하지만 인덱스에 대한 Pythonic 쿼리를 허용하는 무차별 사전입니다.목록에 'cat'과 'cater'라는 단어가 있으면 사전에서 다음과 같은 결과를 얻을 수 있습니다.
d = { 'c': ['cat','cater'],
'ca': ['cat','cater'],
'cat': ['cat','cater'],
'cate': ['cater'],
'cater': ['cater'],
}
따라서 current_word가 'ca'이면 유효한 접두사임을 알 수 있습니다. 'ca' in d True를 반환하므로 보드 순회를 계속합니다.그리고 current_word가 'cat'이면 유효한 접두사이므로 유효한 단어임을 알 수 있습니다. 'cat' in d['cat'] True도 반환합니다.
그렇게 느껴지면 너무 느리지 않은 읽기 쉬운 코드가 허용됩니다.다른 모든 사람들과 마찬가지로 이 시스템의 비용은 인덱스를 읽고 구축하는 것입니다.보드를 해결하는 것은 꽤 많은 소음입니다.
코드는 다음 위치에 있습니다. http://gist.github.com/268079.나는 많은 마법이나 모호함을 사용하여 문제를 복잡하게 만들지 않고 문제를 이해하고 싶었기 때문에 명시적인 유효성 검사를 많이 사용하여 의도적으로 수직적이고 순진합니다.
C ++로 솔버를 썼습니다. 맞춤형 트리 구조를 구현했습니다. 나는 그것이 트리로 간주 될 수 있는지 확신하지 못하지만 비슷합니다. 각 노드에는 알파벳의 각 문자 당 26 개의 분기가 있습니다. 나는 Boggle 보드의 가지를 내 사전의 가지와 평행하게 통과합니다. 사전에 분기가 존재하지 않으면 Boggle 보드에서 검색을 중단합니다. 보드의 모든 글자를 ints로 변환합니다. 따라서 'a'= 0. 배열이므로 조회는 항상 O (1)입니다. 각 노드는 단어를 완성한 경우 저장하고 어린이에 몇 단어가 존재하는지. 단어가 동일한 단어를 반복적으로 검색하는 것으로 밝혀지면서 나무는 가지 치기입니다. 나는 가지 치기도 O (1)이라고 생각합니다.
CPU : Pentium SU2700 1.3GHz
RAM : 3GB
1 초에 178,590 단어의 사전을로드합니다.
4 초 안에 100x100 boggle (boggle.txt)을 해결합니다. ~ 44,000 단어가 발견되었습니다.
4x4 boggle을 해결하는 것은 너무 빠르며 의미있는 벤치 마크를 제공 할 수 없습니다. :)
N 행과 M 열이있는 Boggle 보드가 주어지면 다음을 가정 해 봅시다.
- n*m은 가능한 단어의 수보다 상당히 큽니다.
- n*m은 가장 긴 가능한 단어보다 실질적으로 큽니다.
이러한 가정 하에서이 솔루션의 복잡성은 O (n*m)입니다.
이 예제 보드의 달리기 시간을 여러면에서 비교하는 것은 요점을 놓치지 만 완전성을 위해이 솔루션은 현대 MacBook Pro에서 <0.2s로 완료됩니다.
이 솔루션은 코퍼스의 각 단어에 대한 가능한 모든 경로를 찾을 것입니다.
#!/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}"
이 솔루션은 또한 주어진 보드에서 검색 방향을 제공합니다.
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
산출:
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 → → ↑ ↘ →
암호:
from collections import defaultdict
from nltk.corpus import words
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
english_words = words.words()
# If you wan to remove stop words
# stop_words = set(stopwords.words('english'))
# english_words = [w for w in english_words if w not in stop_words]
boggle = [
['c', 'n', 't', 's', 's'],
['d', 'a', 't', 'i', 'n'],
['o', 'o', 'm', 'e', 'l'],
['s', 'i', 'k', 'n', 'd'],
['p', 'i', 'c', 'l', 'e']
]
# Instead of X and Y co-ordinates
# better to use Row and column
lenc = len(boggle[0])
lenr = len(boggle)
# Initialize trie datastructure
trie_node = {'valid': False, 'next': {}}
# lets get the delta to find all the nighbors
neighbors_delta = [
(-1,-1, "↖"),
(-1, 0, "↑"),
(-1, 1, "↗"),
(0, -1, "←"),
(0, 1, "→"),
(1, -1, "↙"),
(1, 0, "↓"),
(1, 1, "↘"),
]
def gen_trie(word, node):
"""udpates the trie datastructure using the given word"""
if not word:
return
if word[0] not in node:
node[word[0]] = {'valid': len(word) == 1, 'next': {}}
# recursively build trie
gen_trie(word[1:], node[word[0]])
def build_trie(words, trie):
"""Builds trie data structure from the list of words given"""
for word in words:
gen_trie(word, trie)
return trie
def get_neighbors(r, c):
"""Returns the neighbors for a given co-ordinates"""
n = []
for neigh in neighbors_delta:
new_r = r + neigh[0]
new_c = c + neigh[1]
if (new_r >= lenr) or (new_c >= lenc) or (new_r < 0) or (new_c < 0):
continue
n.append((new_r, new_c, neigh[2]))
return n
def dfs(r, c, visited, trie, now_word, direction):
"""Scan the graph using DFS"""
if (r, c) in visited:
return
letter = boggle[r][c]
visited.append((r, c))
if letter in trie:
now_word += letter
if trie[letter]['valid']:
print('Found "{}" {}'.format(now_word, direction))
neighbors = get_neighbors(r, c)
for n in neighbors:
dfs(n[0], n[1], visited[::], trie[letter], now_word, direction + " " + n[2])
def main(trie_node):
"""Initiate the search for words in boggle"""
trie_node = build_trie(english_words, trie_node)
# print the board
print("Given board")
for i in range(lenr):print (boggle[i])
print ('\n')
for r in range(lenr):
for c in range(lenc):
letter = boggle[r][c]
dfs(r, c, [], trie_node, '', 'directions from ({},{})({}) go '.format(r, c, letter))
if __name__ == '__main__':
main(trie_node)
나는 가지고있다 OCAML에서 솔루션을 구현했습니다. 사전을 트리로 사전 컴파일하고 2 글자 시퀀스 주파수를 사용하여 단어로는 절대 나타낼 수없는 가장자리를 제거하여 프로세싱 속도를 높일 수 있습니다.
예제 보드를 0.35ms (트리를 메모리에로드하는 것과 관련된 추가 6ms 시작 시간)를 해결합니다.
발견 된 솔루션 :
["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"]
node.js JavaScript 솔루션. 사전 파일 (MBA 2012)을 포함하여 1 초 이내에 100 개의 고유 단어를 모두 계산합니다.
산출:
"Fam", "Tux", "Tub", "Fae", "Eli", "Elm", "Elb", "Twa", "Twa", "Saw", "Ami", "Swa", " Swa ","Ame ","Sea ","Seen ","Aes ","Awl ","Awe ","Sea ","Awa ","Mix ","Mil ","Ast ","Ase " , "max", "mae", "maw", "mew", "awe", "mes", "awl", "lie", "lim", "awa", "aes", "but", ",", ",", ",", " blo ","way ","wae ","wea ","lei ","leo ","lob ","lox ","wem ","오일 ","Olm ","wea ","wae " , "Wax", "Waf", "Milo", "East", "Wame", "Twas", "Twae", "Emil", "Weam", "Oime", "Axil", "West", " twae ","사지 ","wase ","wast ","bleo ","stub ","book ","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 ","Sembox ","Dembole ","Wamble ","Famble " ]
암호:
var fs = require('fs')
var Node = function(value, row, col) {
this.value = value
this.row = row
this.col = col
}
var Path = function() {
this.nodes = []
}
Path.prototype.push = function(node) {
this.nodes.push(node)
return this
}
Path.prototype.contains = function(node) {
for (var i = 0, ii = this.nodes.length; i < ii; i++) {
if (this.nodes[i] === node) {
return true
}
}
return false
}
Path.prototype.clone = function() {
var path = new Path()
path.nodes = this.nodes.slice(0)
return path
}
Path.prototype.to_word = function() {
var word = ''
for (var i = 0, ii = this.nodes.length; i < ii; ++i) {
word += this.nodes[i].value
}
return word
}
var Board = function(nodes, dict) {
// Expects n x m array.
this.nodes = nodes
this.words = []
this.row_count = nodes.length
this.col_count = nodes[0].length
this.dict = dict
}
Board.from_raw = function(board, dict) {
var ROW_COUNT = board.length
, COL_COUNT = board[0].length
var nodes = []
// Replace board with Nodes
for (var i = 0, ii = ROW_COUNT; i < ii; ++i) {
nodes.push([])
for (var j = 0, jj = COL_COUNT; j < jj; ++j) {
nodes[i].push(new Node(board[i][j], i, j))
}
}
return new Board(nodes, dict)
}
Board.prototype.toString = function() {
return JSON.stringify(this.nodes)
}
Board.prototype.update_potential_words = function(dict) {
for (var i = 0, ii = this.row_count; i < ii; ++i) {
for (var j = 0, jj = this.col_count; j < jj; ++j) {
var node = this.nodes[i][j]
, path = new Path()
path.push(node)
this.dfs_search(path)
}
}
}
Board.prototype.on_board = function(row, col) {
return 0 <= row && row < this.row_count && 0 <= col && col < this.col_count
}
Board.prototype.get_unsearched_neighbours = function(path) {
var last_node = path.nodes[path.nodes.length - 1]
var offsets = [
[-1, -1], [-1, 0], [-1, +1]
, [ 0, -1], [ 0, +1]
, [+1, -1], [+1, 0], [+1, +1]
]
var neighbours = []
for (var i = 0, ii = offsets.length; i < ii; ++i) {
var offset = offsets[i]
if (this.on_board(last_node.row + offset[0], last_node.col + offset[1])) {
var potential_node = this.nodes[last_node.row + offset[0]][last_node.col + offset[1]]
if (!path.contains(potential_node)) {
// Create a new path if on board and we haven't visited this node yet.
neighbours.push(potential_node)
}
}
}
return neighbours
}
Board.prototype.dfs_search = function(path) {
var path_word = path.to_word()
if (this.dict.contains_exact(path_word) && path_word.length >= 3) {
this.words.push(path_word)
}
var neighbours = this.get_unsearched_neighbours(path)
for (var i = 0, ii = neighbours.length; i < ii; ++i) {
var neighbour = neighbours[i]
var new_path = path.clone()
new_path.push(neighbour)
if (this.dict.contains_prefix(new_path.to_word())) {
this.dfs_search(new_path)
}
}
}
var Dict = function() {
this.dict_array = []
var dict_data = fs.readFileSync('./web2', 'utf8')
var dict_array = dict_data.split('\n')
for (var i = 0, ii = dict_array.length; i < ii; ++i) {
dict_array[i] = dict_array[i].toUpperCase()
}
this.dict_array = dict_array.sort()
}
Dict.prototype.contains_prefix = function(prefix) {
// Binary search
return this.search_prefix(prefix, 0, this.dict_array.length)
}
Dict.prototype.contains_exact = function(exact) {
// Binary search
return this.search_exact(exact, 0, this.dict_array.length)
}
Dict.prototype.search_prefix = function(prefix, start, end) {
if (start >= end) {
// If no more place to search, return no matter what.
return this.dict_array[start].indexOf(prefix) > -1
}
var middle = Math.floor((start + end)/2)
if (this.dict_array[middle].indexOf(prefix) > -1) {
// If we prefix exists, return true.
return true
} else {
// Recurse
if (prefix <= this.dict_array[middle]) {
return this.search_prefix(prefix, start, middle - 1)
} else {
return this.search_prefix(prefix, middle + 1, end)
}
}
}
Dict.prototype.search_exact = function(exact, start, end) {
if (start >= end) {
// If no more place to search, return no matter what.
return this.dict_array[start] === exact
}
var middle = Math.floor((start + end)/2)
if (this.dict_array[middle] === exact) {
// If we prefix exists, return true.
return true
} else {
// Recurse
if (exact <= this.dict_array[middle]) {
return this.search_exact(exact, start, middle - 1)
} else {
return this.search_exact(exact, middle + 1, end)
}
}
}
var board = [
['F', 'X', 'I', 'E']
, ['A', 'M', 'L', 'O']
, ['E', 'W', 'B', 'X']
, ['A', 'S', 'T', 'U']
]
var dict = new Dict()
var b = Board.from_raw(board, dict)
b.update_potential_words()
console.log(JSON.stringify(b.words.sort(function(a, b) {
return a.length - b.length
})))
그래서 나는 모든 사람들이 PHP를 좋아하기 때문에 이것을 해결하는 또 다른 PHP 방법을 추가하고 싶었습니다. 사전 파일에 대한 regexpression match를 사용하는 것과 같이 약간의 리팩토링이 필요하지만 지금은 전체 사전 파일을 워드리스트에로드하고 있습니다.
나는 링크 된 목록 아이디어를 사용하여 이것을했다. 각 노드에는 문자 값, 위치 값 및 다음 포인터가 있습니다.
위치 값은 두 노드가 연결되어 있는지 알게 된 방법입니다.
1 2 3 4
11 12 13 14
21 22 23 24
31 32 33 34
따라서 해당 그리드를 사용하면 첫 번째 노드의 위치가 동일한 행의 두 번째 노드 위치 +/- 1 인 경우 두 개의 노드가 연결되어 있음을 알고 있습니다. 위와 아래 행의 행의 경우 +/- 9, 10, 11.
나는 메인 검색에 재귀를 사용합니다. 그것은 단어 목록에서 단어를 제거하고 가능한 모든 출발점을 찾은 다음 이미 사용중인 위치로 이동할 수 없다는 점을 명심하고 다음 가능한 연결을 재귀 적으로 찾습니다 ($ notinloc을 추가하는 이유).
어쨌든, 나는 그것이 리팩토링이 필요하다는 것을 알고 있으며, 그것을 깨끗하게 만드는 방법에 대한 생각을 듣고 싶지만, 내가 사용하는 사전 파일을 기반으로 올바른 결과를 생성합니다. 보드의 모음과 조합의 수에 따라 약 3-6 초가 소요됩니다. 나는 사전 결과를 preg_match하면 크게 감소 할 것임을 알고 있습니다.
<?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);
?>
나는 파티에 늦었다는 것을 알고 있지만 코딩 연습으로 여러 프로그래밍 언어 (C ++, Java, Go, C#, Python, Ruby, JavaScript, Julia, Lua, PHP, Perl)의 Boggle 솔버를 구현했습니다. 누군가가 그것에 관심이 있다고 생각 했으므로 여기에 링크를 남깁니다.https://github.com/amokhuginnsson/boggle-solvers
다음은 nltk 툴킷에서 사전 정의 된 단어를 사용하는 솔루션입니다. nltk nltk.corpus 패키지는 단어라는 패키지가 있으며 2 락 이상의 영어 단어가 포함되어 있다는 것입니다.
매트릭스를 만들면 문자 배열로 변환 하고이 코드를 수행하십시오.
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)
산출:
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
나는 당신이 그것을 얻기를 바랍니다.
내 Java 구현은 다음과 같습니다. https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/bogglesolver.java
트리 빌드는 0 시간, 0 분, 1 초, 532 밀리 초가 걸렸습니다.
단어 검색은 0 시간, 0 분, 0 초, 92 밀리 초가 걸렸습니다.
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
메모:이 스레드의 시작 부분에서 사전과 문자 매트릭스를 사용했습니다. 코드는 내 MacBookPro에서 실행되었으며 아래는 기계에 대한 정보입니다.
모델 이름 : MacBook Pro
모델 식별자 : MacBookPro8,1
프로세서 이름 : 인텔 코어 i5
프로세서 속도 : 2.3GHz
프로세서 수 : 1
총 코어 수 : 2
L2 캐시 (코어 당) : 256 KB
L3 캐시 : 3MB
메모리 : 4GB
부트 ROM 버전 : MBP81.0047.B0E
SMC 버전 (시스템) : 1.68F96
나는 Java와 함께 이것을 해결했다. 내 구현은 길이가 269 줄이며 사용하기 쉽습니다. 먼저 Boggler 클래스의 새 인스턴스를 작성한 다음 그리드를 매개 변수로 Solve 기능을 호출해야합니다. 내 컴퓨터에 5 만 단어의 사전을로드하는 데 약 100ms가 걸리며 약 10-20ms에서 단어를 찾습니다. 발견 된 단어는 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;
}
}
나는 이것을 c. 내 컴퓨터에서 실행하는 데 약 48ms가 걸립니다 (디스크에서 사전을로드하고 트리를 생성하는 데 소요되는 시간의 약 98%가 필요합니다). 사전은/usr/share/dict/atamerichlish이며 62886 단어가 있습니다.
나는 이것을 완벽하고 매우 빠르게 해결했습니다. 나는 그것을 Android 앱에 넣었습니다. Play Store 링크에서 비디오를보고 실제로 확인하십시오.
Word Cheats는 모든 매트릭스 스타일의 단어 게임을 "균열"하는 앱입니다. 이 앱은 Word Scrambler를 속이는 데 도움이되도록 만들어졌습니다. 단어 검색, 루즐, 단어, 단어 찾기, 단어 균열, boggle 등에 사용할 수 있습니다!
여기에서 볼 수 있습니다https://play.google.com/store/apps/details?id=com.harris.wordcracker
비디오에서 작동하는 앱을보십시오https://www.youtube.com/watch?v=dl2974wmnai
제휴하지 않습니다 StackOverflow
