Какая доска Ruzzle содержит самые уникальные слова?
Для смартфонов есть эта игра под названием Ruzzle.
Это игра для поиска слов.
Быстрое объяснение:
Игровое поле представляет собой сетку букв 4х4.
Вы начинаете с любой клетки и пытаетесь написать слово, перетаскивая его вверх, вниз, влево, вправо или по диагонали.
Доска не переносится, и вы не можете повторно использовать буквы, которые вы уже выбрали.
В среднем мы с моим другом находим около 40 слов, и в конце раунда игра информирует вас о том, сколько возможных слов вы могли бы получить. Это число обычно около 250 — 350.
Нам интересно, какая доска выдаст наибольшее количество возможных слов.
Как мне найти оптимальную доску?
Я написал программу на C, которая принимает 16 символов и выводит все соответствующие слова.
Тестирование более 80 000 слов занимает около секунды.
Эта проблема:
Количество перестановок игрового поля составляет 26 ^ 16.
Это 43608742899428874059776 (43 секстиллиона).
Мне нужна какая-то эвристика.
Должен ли я пропустить все доски, которые имеют Z, Q, Икс, так далее потому что они должны иметь не так много слов? Я не хотел бы исключать письмо, не будучи уверенным.
Существует также 4 дубликата каждой доски, потому что поворот доски все равно даст те же результаты.
Но даже с этими ограничениями я не думаю, что у меня есть достаточно времени в моей жизни, чтобы найти ответ.
Может быть, создание доски не ответ.
Есть ли более быстрый способ найти ответ по списку слов?
Решение
tldr;
S E R O
P I T S
L A N E
S E R G
или любое из его отражений.
Эта доска содержит 1212 слов (и, как оказалось, вы можете исключить «z», «q» и «x»).
Перво-наперво, оказывается, вы используете неправильный словарь. После того, как я не получил точное совпадение с количеством слов в Ruzzle, я посмотрел на него, кажется, что Ruzzle использует словарь под названием TWL06, который содержит около 180 000 слов. Не спрашивайте меня, что это означает, но это свободно доступно в текстовом формате.
Я также написал код, чтобы найти все возможные слова, заданные доской из 16 символов, следующим образом. Он строит словарь в древовидную структуру, а затем просто рекурсивно обходит, в то время как есть слова, которые нужно найти. Он печатает их в порядке длины. Уникальность поддерживается структурой множества STL.
#include <cstdlib>
#include <ctime>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;
struct TreeDict {
bool existing;
map<char, TreeDict> sub;
TreeDict() {
existing = false;
}
TreeDict& operator=(TreeDict &a) {
existing = a.existing;
sub = a.sub;
return *this;
}
void insert(string s) {
if(s.size() == 0) {
existing = true;
return;
}
sub[s[0]].insert(s.substr(1));
}
bool exists(string s = "") {
if(s.size() == 0)
return existing;
if(sub.find(s[0]) == sub.end())
return false;
return sub[s[0]].exists(s.substr(1));
}
TreeDict* operator[](char alpha) {
if(sub.find(alpha) == sub.end())
return NULL;
return &sub[alpha];
}
};
TreeDict DICTIONARY;
set<string> boggle_h(const string board, string word, int index, int mask, TreeDict *dict) {
if(index < 0 || index >= 16 || (mask & (1 << index)))
return set<string>();
word += board[index];
mask |= 1 << index;
dict = (*dict)[board[index]];
if(dict == NULL)
return set<string>();
set<string> rt;
if((*dict).exists())
rt.insert(word);
if((*dict).sub.empty())
return rt;
if(index % 4 != 0) {
set<string> a = boggle_h(board, word, index - 4 - 1, mask, dict);
set<string> b = boggle_h(board, word, index - 1, mask, dict);
set<string> c = boggle_h(board, word, index + 4 - 1, mask, dict);
rt.insert(a.begin(), a.end());
rt.insert(b.begin(), b.end());
rt.insert(c.begin(), c.end());
}
if(index % 4 != 3) {
set<string> a = boggle_h(board, word, index - 4 + 1, mask, dict);
set<string> b = boggle_h(board, word, index + 1, mask, dict);
set<string> c = boggle_h(board, word, index + 4 + 1, mask, dict);
rt.insert(a.begin(), a.end());
rt.insert(b.begin(), b.end());
rt.insert(c.begin(), c.end());
}
set<string> a = boggle_h(board, word, index + 4, mask, dict);
set<string> b = boggle_h(board, word, index - 4, mask, dict);
rt.insert(a.begin(), a.end());
rt.insert(b.begin(), b.end());
return rt;
}
set<string> boggle(string board) {
set<string> words;
for(int i = 0; i < 16; i++) {
set<string> a = boggle_h(board, "", i, 0, &DICTIONARY);
words.insert(a.begin(), a.end());
}
return words;
}
void buildDict(string file, TreeDict &dict = DICTIONARY) {
ifstream fstr(file.c_str());
string s;
if(fstr.is_open()) {
while(fstr.good()) {
fstr >> s;
dict.insert(s);
}
fstr.close();
}
}
struct lencmp {
bool operator()(const string &a, const string &b) {
if(a.size() != b.size())
return a.size() > b.size();
return a < b;
}
};
int main() {
srand(time(NULL));
buildDict("/Users/XXX/Desktop/TWL06.txt");
set<string> a = boggle("SEROPITSLANESERG");
set<string, lencmp> words;
words.insert(a.begin(), a.end());
set<string>::iterator it;
for(it = words.begin(); it != words.end(); it++)
cout << *it << endl;
cout << words.size() << " words." << endl;
}
Произвольное создание досок и тестирование на них не оказалось слишком эффективным, как я и ожидал, я не особо задумывался об этом, но я был бы удивлен, если бы они пересекли 200 слов. Вместо этого я изменил поколение плат, чтобы генерировать доски с буквами, распределенными пропорционально их частоте в TWL06, что достигается быстрой кумулятивной частотой (частоты были уменьшены в 100 раз) ниже.
string randomBoard() {
string board = "";
for(int i = 0; i < 16; i++)
board += (char)('A' + rand() % 26);
return board;
}
char distLetter() {
int x = rand() % 15833;
if(x < 1209) return 'A';
if(x < 1510) return 'B';
if(x < 2151) return 'C';
if(x < 2699) return 'D';
if(x < 4526) return 'E';
if(x < 4726) return 'F';
if(x < 5161) return 'G';
if(x < 5528) return 'H';
if(x < 6931) return 'I';
if(x < 6957) return 'J';
if(x < 7101) return 'K';
if(x < 7947) return 'L';
if(x < 8395) return 'M';
if(x < 9462) return 'N';
if(x < 10496) return 'O';
if(x < 10962) return 'P';
if(x < 10987) return 'Q';
if(x < 12111) return 'R';
if(x < 13613) return 'S';
if(x < 14653) return 'T';
if(x < 15174) return 'U';
if(x < 15328) return 'V';
if(x < 15452) return 'W';
if(x < 15499) return 'X';
if(x < 15757) return 'Y';
if(x < 15833) return 'Z';
}
string distBoard() {
string board = "";
for(int i = 0; i < 16; i++)
board += distLetter();
return board;
}
Это было значительно более эффективно, очень легко достичь 400+ досок для слов. Я оставил его работающим (дольше, чем я предполагал), и после проверки более миллиона досок, самое высокое найденное было около 650 слов. Это было все еще по существу случайное поколение, и это имеет свои пределы.
Вместо этого я выбрал жадную стратегию максимизации, в которой я брал доску и вносил в нее небольшие изменения, а затем совершал изменения, только если они увеличивали количество слов.
string changeLetter(string x) {
int y = rand() % 16;
x[y] = distLetter();
return x;
}
string swapLetter(string x) {
int y = rand() % 16;
int z = rand() % 16;
char w = x[y];
x[y] = x[z];
x[z] = w;
return x;
}
string change(string x) {
if(rand() % 2)
return changeLetter(x);
return swapLetter(x);
}
int main() {
srand(time(NULL));
buildDict("/Users/XXX/Desktop/TWL06.txt");
string board = "SEROPITSLANESERG";
int locmax = boggle(board).size();
for(int j = 0; j < 5000; j++) {
int changes = 1;
string board2 = board;
for(int k = 0; k < changes; k++)
board2 = change(board);
int loc = boggle(board2).size();
if(loc >= locmax && board != board2) {
j = 0;
board = board2;
locmax = loc;
}
}
}
Это очень быстро дало мне более 1000 досок слов с почти одинаковыми буквенными узорами, несмотря на рандомизированные начальные точки. Что заставляет меня верить, что данная доска лучший возможный доска — это то, как она или одно из ее различных отражений неоднократно поднималась в течение первых 100 нечетных попыток максимизации случайной доски.
Основной причиной скептицизма является жадность этого алгоритма, и то, что это каким-то образом приведет к тому, что алгоритм упустит лучшие платы. Внесенные небольшие изменения весьма гибки в своих результатах, то есть они способны полностью преобразовать сетку из ее (рандомизированной) начальной позиции. Число возможных изменений, 26 * 16 для свежего письма и 16 * 15 для обмена буквами, значительно меньше 5000, что позволяет непрерывно отбрасывать изменения.
Тот факт, что программе удалось повторить этот вывод платы в течение первых 100 нечетных времен, означает, что число локальных максимумов относительно мало, а вероятность того, что существует необнаруженный максимум минимума.
Хотя жадность казалась интуитивно правильной — на самом деле не должно быть меньше возможности достичь заданной сетки с дельта-изменениями от случайной доски — и два возможных изменения, своп и свежая буква, похоже, заключают в себе все возможные улучшения, я изменил программу, чтобы она могла вносить больше изменений, прежде чем проверять увеличение. Это снова возвращал ту же доску, неоднократно.
int main() {
srand(time(NULL));
buildDict("/Users/XXX/Desktop/TWL06.txt");
int glomax = 0;
int i = 0;
while(true) {
string board = distBoard();
int locmax = boggle(board).size();
for(int j = 0; j < 500; j++) {
string board2 = board;
for(int k = 0; k < 2; k++)
board2 = change(board);
int loc = boggle(board2).size();
if(loc >= locmax && board != board2) {
j = 0;
board = board2;
locmax = loc;
}
}
if(glomax <= locmax) {
glomax = locmax;
cout << board << " " << glomax << " words." << endl;
}
if(++i % 10 == 0)
cout << i << endl;
}
}
Обойдя этот цикл около 1000 раз, при этом конкретная конфигурация платы показалась ~ 10 раз, я вполне уверен, что на данный момент это плата Ruzzle с самыми уникальными словами, пока не изменится английский язык.
Другие решения
Интересная проблема. Я вижу (по крайней мере, но в основном) два подхода
-
Один из них — это попробовать сложный способ, чтобы сунуть как можно больше wordable буквы (во всех направлениях), насколько это возможно, на основе словаря. Как вы сказали, существует множество возможных комбинаций, и этот маршрут требует хорошо проработанного и сложного алгоритма для достижения чего-то осязаемого
-
есть еще одно «слабое» решение, основанное на вероятностях, которое мне нравится больше. Вы предложили убрать несколько некачественных букв, чтобы максимизировать доходность доски. Расширением этого может быть использование большего количества букв высокого появления в словаре.
Дальнейший шаг может быть:
-
на основе словаря 80k
DВы узнаете для каждого l1 Письмо нашего ансамбля из 26 букв вероятность того, что письмо l2 предшествует или следует l1. ЭтоL x Lмассив вероятностей, и он довольно мал, так что вы можете даже расширить доL x L x Lт.е. l1 а также l2 какая вероятность имеет l3 подходить. Это немного сложнее, если алгоритм хочет оценить точные вероятности, так как сумма вероятностей зависит от взаимного расположения 3 букв, например, в конфигурации «треугольник» (например, позиции (3,3), (3,4) ) и (3,5)) результат, вероятно, менее эффективен, чем когда буквы выровнены [только предположение]. Почему бы не подняться наL x L x L x L, что потребует некоторых оптимизаций … -
затем вы распределяете несколько букв с высокой внешностью (скажем, 4 ~ 6) случайным образом на доске (каждая из которых имеет по крайней мере 1 пустую ячейку вокруг по крайней мере в 5 из 8 возможных направлений), а затем используете ваши
L x L [xL]Пробные массивы для завершения — это означает, что, основываясь на существующей букве, следующая ячейка заполняется буквой с высокой вероятностью, учитывая конфигурацию [снова, буквы сортируются по убыванию проба, и используют случайность, если две буквы находятся в тесной связи].
Например, принимая только горизонтальную конфигурацию, имея на месте следующие буквы, и мы хотим найти лучшие 2 между ER а также TO
...ER??TO...
С помощью L x L, как петля (l1 и l2 наши две пропущенные буквы). Найти абсолютно лучшие буквы — но Лучший выбор а также bestproba вместо этого можно использовать массивы и сохранить, скажем, 10 лучших вариантов.
Примечание: в этом случае нет необходимости держать пробу в диапазоне [0,1], мы можем суммировать пробы (которые не дают пробу — но число имеет значение. Математическая проба может быть чем-то вроде p = (p (l0, l1) + p (l2, l3)) / 2, l0 и l3 являются р а также T в нашем L x L Exemple)
bestproba = 0
bestchoice = (none, none)
for letter l1 in L
for letter l2 in L
p = proba('R',l1) + proba(l2,'T')
if ( p > bestproba )
bestproba = p
bestchoice = (l1, l2)
fi
rof
rof
алгоритм может принимать во внимание больше факторов, а также принимать во внимание вертикаль и диагонали. С L x L x Lбольше букв в разных направлениях, например ER?,R??,??T,?TO — это требует больше думать через алгоритм — возможно, начиная с L x L Можно дать представление об актуальности этого алгоритма.
Обратите внимание, что многое из этого может быть предварительно рассчитано, и L x L массив, конечно, один из них.