文字グリッドでは構築できない単語を一致させるために、おそらくほとんどの時間を費やすことになると思います。したがって、私が最初に行うことは、そのステップをスピードアップすることです。
このために、グリッドを可能な「動き」のテーブルとして再表現し、見ている文字遷移によってインデックスを付けます。
まず、アルファベット全体から各文字に数字を割り当てます (A=0、B=1、C=2、... など)。
この例を見てみましょう：
h b c d
e e g h
l l k l
m o f p
そして今のところ、私たちが持っている文字のアルファベットを使用しましょう (通常は、毎回同じアルファベット全体を使用したいでしょう):
b | c | d | e | f | g | h | k | l | m | o | p
---+---+---+---+---+---+---+---+---+---+----+----
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
次に、特定の文字遷移が利用可能かどうかを示す 2D ブール配列を作成します。
| 0 1 2 3 4 5 6 7 8 9 10 11 <- from letter
| b c d e f g h k l m o p
-----+--------------------------------------
0 b | T T T T
1 c | T T T T T
2 d | T T T
3 e | T T T T T T T
4 f | T T T T
5 g | T T T T T T T
6 h | T T T T T T T
7 k | T T T T T T T
8 l | T T T T T T T T T
9 m | T T
10 o | T T T T
11 p | T T T
^
to letter
次に、単語リストを調べて、単語をトランジションに変換します。
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
次に、テーブルでそれらを検索して、これらの遷移が許可されているかどうかを確認します。
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
それらがすべて許可されている場合、この単語が見つかる可能性があります。
たとえば、「ヘルメット」という単語は、4 番目のトランジション (m から e: helMEt) で除外できます。これは、テーブルのエントリが false であるためです。
最初の (h から a への) 遷移は許可されていないため (テーブルには存在しません)、ハムスターという単語は除外できます。
さて、おそらく削除しなかった残りの単語については、現在行っている方法で、またはここの他の回答のいくつかで提案されているように、実際にグリッドでそれらを見つけてみてください. これは、グリッド内の同一文字間のジャンプに起因する誤検知を回避するためです。たとえば、「ヘルプ」という単語はテーブルでは許可されていますが、グリッドでは許可されていません。
このアイデアに関するさらなるパフォーマンス改善のヒント:
2D 配列を使用する代わりに、1D 配列を使用して、2 番目の文字のインデックスを自分で計算するだけです。したがって、上記のような 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 つだけです: hel、ell、llo。ちなみに、このテーブルを作成するのは非常に簡単です。グリッドには 400 の可能な 3 文字の動きしかないからです。
テーブルに含める必要があるグリッド内の動きのインデックスを事前に計算します。上記の例では、次のエントリを「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-D 配列で表し、テーブルを 3. で事前に計算します。この配列にインデックスを含めます。
このアプローチを使用すると、辞書が事前に計算され、既にメモリにロードされている場合、コードを非常に高速に実行できると確信しています。
ところで: ゲームを構築している場合、もう 1 つの良い方法は、これらの種類のものをバックグラウンドですぐに実行することです。ユーザーがまだアプリのタイトル画面を見て、指を所定の位置に置いて [再生] を押している間に、最初のゲームの生成と解決を開始します。次に、ユーザーが前のゲームをプレイするときに、次のゲームを生成して解決します。これにより、コードを実行するための多くの時間を得ることができます。
(私はこの問題が好きなので、実際にどのように機能するかを確認するために、数日中に私の提案を 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 Tournament Scrabble Word Listを使用しました。このファイルは 1.85MB なので、少し短くなっています。そして、buildDictionary関数は 3 文字未満のすべての単語を除外します。
このパフォーマンスに関するいくつかの観察事項を次に示します。
これは、報告されている Victor Nicollet の OCaml 実装のパフォーマンスよりも約 10 倍遅いです。これは、異なるアルゴリズム、彼が使用した短い辞書、彼のコードがコンパイルされ、私のコードが Java 仮想マシンで実行されるという事実、または私たちのコンピューターのパフォーマンス (私のコンピューターは Intel Q6600 @ 2.4MHz で WinXP を実行している) によって引き起こされているかどうかにかかわらず、知らない。しかし、元の質問の最後に引用されている他の実装の結果よりもはるかに高速です。したがって、このアルゴリズムがトライ辞書よりも優れているかどうかは、現時点ではわかりません。
で使用されているテーブル メソッドはcheckWordTriplets()、実際の回答に対して非常に優れた近似値を生成します。渡された 3 ～ 5 単語のうち 1 つだけがcheckWords()テストに失敗します (上記の候補の数と実際の単語の数を参照してください)。
上に表示されていないもの: このcheckWordTriplets()関数は約 3.65 ミリ秒かかるため、検索プロセスで完全に支配的です。このcheckWords()関数は、残りの 0.05 ～ 0.20 ミリ秒のほとんどを占めています。
関数の実行時間はcheckWordTriplets()ディクショナリのサイズに直線的に依存し、ボードのサイズには実質的に依存しません!
の実行時間はcheckWords()、ボードのサイズと によって除外されない単語の数によって異なりますcheckWordTriplets()。
上記のcheckWords()実装は、私が思いついた最もばかげた最初のバージョンです。基本的に最適化されていません。しかし、checkWordTriplets()それはアプリケーションの全体的なパフォーマンスとは無関係なので、私は気にしませんでした。しかし、ボードのサイズが大きくなると、この機能はますます遅くなり、最終的には問題になり始めます。次に、それも最適化する必要があります。
このコードの優れた点の 1 つは、その柔軟性です。
- ボード サイズは簡単に変更できます。10 行目と に渡される文字列配列を更新し
initializeBoard()ます。
- より大きな/異なるアルファベットをサポートでき、パフォーマンスのオーバーヘッドなしで「Qu」を 1 文字として処理することができます。これを行うには、9 行目と、文字が数字に変換されるいくつかの場所を更新する必要があります (現在は、ASCII 値から 65 を引くだけです)。
わかりましたが、今ではこの投稿は十分に長いと思います。どんな質問にも確実にお答えできますが、それはコメントに移しましょう。
