Я думаю, что вы, вероятно, потратите большую часть своего времени, пытаясь сопоставить слова, которые невозможно построить с помощью вашей буквенной сетки. Итак, первое, что я хотел бы сделать, это попытаться ускорить этот шаг, и это поможет вам пройти большую часть пути.
Для этого я бы повторно выразил сетку в виде таблицы возможных «ходов», которые вы индексируете по просматриваемой букве-переходу.
Начните с присвоения каждой букве числа из всего вашего алфавита (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
Затем вы создаете двумерный логический массив, который сообщает, доступен ли вам определенный переход букв:
| 0 1 2 3 4 5 6 7 8 9 10 11 <- from letter
| b c d e f g h k l m o p
-----+--------------------------------------
0 b | T T T T
1 c | T T T T T
2 d | T T T
3 e | T T T T T T T
4 f | T T T T
5 g | T T T T T T T
6 h | T T T T T T T
7 k | T T T T T T T
8 l | T T T T T T T T T
9 m | T T
10 o | T T T T
11 p | T T T
^
to letter
Теперь просмотрите ваш список слов и преобразуйте слова в переходы:
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
Затем проверьте, разрешены ли эти переходы, посмотрев их в своей таблице:
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
Если все они разрешены, есть вероятность, что это слово может быть найдено.
Например, слово «шлем» может быть исключено при 4-м переходе (от m до e: helMEt), поскольку эта запись в вашей таблице ложна.
И слово хомяк можно исключить, так как первый (h к a) переход недопустим (даже не существует в вашей таблице).
Теперь, возможно, для очень немногих оставшихся слов, которые вы не исключили, попробуйте найти их в сетке так, как вы это делаете сейчас, или как предложено в некоторых других ответах здесь. Это сделано для того, чтобы избежать ложных срабатываний, возникающих в результате скачков между одинаковыми буквами в вашей сетке. Например, слово «помощь» разрешено таблицей, но не сеткой.
Несколько советов по улучшению производительности по этой идее:
Вместо использования двумерного массива, используйте одномерный массив и просто рассчитайте индекс второй буквы самостоятельно. Таким образом, вместо массива 12x12, как описано выше, создайте одномерный массив длиной 144. Если затем вы всегда используете один и тот же алфавит (т.е. массив 26x26 = 676x1 для стандартного английского алфавита), даже если не все буквы отображаются в вашей сетке Вы можете предварительно вычислить индексы в этом одномерном массиве, который необходимо проверить, чтобы соответствовать словам из словаря. Например, индексы для «привет» в приведенном выше примере будут
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
Расширить идею до трехмерной таблицы (выраженной в виде одномерного массива), то есть всех допустимых 3-буквенных комбинаций. Таким образом, вы можете сразу исключить еще больше слов и сократить количество поисков в массиве для каждого слова на 1: для «привет» вам нужно только 3 поиска в массивах: hel, ell, llo. Между прочим, будет очень быстро построить эту таблицу, поскольку в вашей сетке есть только 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 записями и предварительно рассчитайте таблицу в 3. содержат индексы в этом массиве.
Я уверен, что если вы воспользуетесь этим подходом, вы сможете заставить свой код работать безумно быстро, если у вас есть предварительно вычисленный словарь и уже загруженный в память.
Кстати: еще одна приятная вещь, если вы создаете игру, - запускать подобные вещи немедленно в фоновом режиме. Начните генерировать и решать первую игру, пока пользователь все еще смотрит на титульный экран в вашем приложении и вводит палец в положение, чтобы нажать «Play». Затем создайте и решите следующую игру, когда пользователь играет в предыдущую. Это должно дать вам много времени для запуска вашего кода.
(Мне нравится эта проблема, поэтому я, вероятно, в ближайшие дни буду испытывать желание реализовать свое предложение на Java, чтобы посмотреть, как оно на самом деле будет работать ... Я опубликую здесь код, как только это сделаю.)
UPDATE:
Хорошо, у меня было немного времени сегодня, и я реализовал эту идею в 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,85 МБ, поэтому он немного короче. А функция buildDictionary выбрасывает все слова, содержащие не более 3 букв.
Вот пара замечаний о производительности этого:
Это примерно в 10 раз медленнее, чем заявленная производительность реализации OCaml Виктора Николье. Причиной этого является другой алгоритм, более короткий словарь, который он использовал, тот факт, что его код скомпилирован, а мой работает на виртуальной машине Java, или производительность наших компьютеров (у меня Intel Q6600 @ 2,4 МГц с WinXP), Я не знаю. Но это намного быстрее, чем результаты для других реализаций, указанных в конце исходного вопроса. Итак, превосходит ли этот алгоритм словарь Trie или нет, на данный момент я не знаю.
Метод таблицы, используемый в checkWordTriplets(), дает очень хорошее приближение к фактическим ответам. Только 1 из 3-5 пропущенных слов не пройдёт тест checkWords() (см. количество кандидатов против количество фактических слов выше).
Что-то, чего вы не видите выше: функция checkWordTriplets() занимает около 3,65 мс и поэтому полностью доминирует в процессе поиска. Функция checkWords() занимает в значительной степени оставшиеся 0,05-0,20 мс.
Время выполнения функции checkWordTriplets() линейно зависит от размера словаря и практически независимо от размера доски!
Время выполнения checkWords() зависит от размера доски и количества слов, не исключенных checkWordTriplets().
Реализация checkWords(), описанная выше, является самой глупой первой версией, которую я придумал. Это в основном не оптимизировано вообще. Но по сравнению с checkWordTriplets() это не имеет значения для общей производительности приложения, поэтому я не беспокоился об этом. Но , если размер платы увеличивается, эта функция будет становиться все медленнее и медленнее и в конечном итоге начнет иметь значение. Тогда его тоже нужно оптимизировать.
Одна приятная вещь в этом коде - его гибкость:
- Вы можете легко изменить размер платы: строка обновления 10 и массив строк будут переданы в
initializeBoard().
- Он может поддерживать большие / разные алфавиты и может обрабатывать такие вещи, как «Qu» как одна буква без каких-либо потерь производительности. Для этого необходимо обновить строку 9 и пару мест, где символы преобразуются в числа (в настоящее время просто вычитая 65 из значения ASCII)
Хорошо, но я думаю, что этот пост уже достаточно длинный. Я определенно могу ответить на любые ваши вопросы, но давайте перейдем к комментариям.