Сегодня мы собираемся сделать облегченный решатель для популярной игры WordHunt для iMessage с C ++. Он сможет дать нам безумно высокие оценки и некоторые решения, которые почти невозможно придумать человеку!
Если вы еще не знаете, WordHunt - это игра iMessage, в которой игрокам дают доску с буквами 4x4 и проводят пальцем по доске, чтобы составить как можно больше слов менее чем за минуту и 30 секунд. Чем больше слов произносит игрок, тем больше очков он получает, и чем длиннее слова, тем выше их оценка. Игрок, набравший наибольшее количество очков в конце отведенного времени, побеждает в игре.
Что мы хотим сделать, так это решатель для игры или программу, в которой, когда мы вводим доску букв, она выводит все возможные оптимальные допустимые слова (или решения), которые мы можем использовать в игре. Давайте начнем!
Во-первых, нам нужен список правильных слов (или буквальный словарь), чтобы мы знали, что такое правильное английское слово. С помощью простого поиска в Google я нашел один на Github. Мы хотим сохранить список всех допустимых слов в текстовом файле - я назвал его dictionary.txt:
Теперь мы можем приступить к программированию! Мы можем ввести доску букв 4x4 в виде строки слева направо. Например:
Затем мы можем сохранить это обратно в 2D-массив (я сделал это для демонстрационных целей, но 1D-массив был бы немного более эффективным) с помощью:
cout << "Enter the board:"; string read; cin >> read; board[0] = read.substr(0,4); board[1] = read.substr(4,8); board[2] = read.substr(8,12); board[3] = read.substr(12,16);
Затем мы можем перебрать все возможные комбинации букв, которые могут быть составлены с нашей заданной доской, используя рекурсию. В частности, мы собираемся использовать алгоритм под названием Поиск в глубину. По сути, это имитирует попытку пальца каждой возможной комбинации букв, только намного быстрее. Мы делаем это, сначала вызывая нашу рекурсивную функцию для каждой буквы доски (это то место, где должен начинаться наш палец):
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 4; j++) {
recurse(i, j, "", ("(" + to_string(i) + ", " + to_string(j) + ")"), visited);
}
}
Наша рекурсивная функция выглядит следующим образом:
void recurse(int row, int col, string word, string path, bool visited[4][4],
struct TrieNode *node)
{
if(row < 0 || row >= 4 || col < 0 || col >= 4)
return;
if(visited[row][col])
return;
string letter = string(1,board[row][col]);
visited[row][col] = true;
//Here we have our current combination of letters
word += letter
//Check to see if it is valid here.
vector <pair <pair <int, int>, string >> directions =
{ make_pair(make_pair(1, 0), ", D"),
make_pair(make_pair(0, 1), ", R"),
make_pair(make_pair(-1, 0), ", U"),
make_pair(make_pair(0, -1), ", L"),
make_pair(make_pair(1, -1), ", LD"),
make_pair(make_pair(-1, 1), ", RU"),
make_pair(make_pair(1, 1), ", RD"),
make_pair(make_pair(-1, -1), ", LU") };
for( pair < pair <int, int>, string > elem : directions)
{
int x = elem.first.first;
int y = elem.first.second;
string d = elem.second;
if(row+x >= 0 && row+x < 4 && col+y >= 0 && col+y < 4)
if(!visited[row+x][col+y])
recurse(row+x, col+y, word, path+d, visited, (node->children)[letter]);
}
visited[row][col] = false;
}
Хорошо! Теперь мы можем использовать любую возможную комбинацию букв для нашей доски.
Теперь нам нужно проверить, какие из них действительны, и мы можем сделать это, проверив, какие из них есть в файле dictionary.txt!
Мы можем сделать это, сохранив наш список допустимых английских слов в типе данных карта (словарь в Python). Это не так уж и плохо, потому что поиск чего-либо на карте может выполняться за постоянное время или за O (1). Вот как мы можем это сделать:
dictionary = {};
def make_dict(self):
f = open('dictionaries/470kwords.txt', 'r');
fr = f.read().splitlines();
for word in fr:
self.dictionary[word] = '1';
with open('dict.json', 'w') as outfile:
json.dump(self.dictionary, outfile);
А затем в нашем обходе возможной комбинации букв мы должны проверить, действительна ли она, добавив ее к массиву решений, который начинается как пустой (я также включил путь, который решатель выбрал для создания комбинации):
//Check to see if it is valid here. if(word in self.dictionary and len(word) > 2): self.ans.append(word); self.paths.append(path);
Имея список всех возможных слов, на которые мы можем ответить в игре, мы хотим отсортировать их по длине, чтобы мы могли просто увидеть лучшие решения:
pair = zip(self.ans, self.paths);
final = sorted(pair, key=lambda x: len(x[0]), reverse=True);
for i in range(len(final)):
print(i, final[i][0]);
print(" ", final[i][1]);
Теперь, когда мы запускаем решатель и вводим нашу плату, мы получаем список из более чем 200 решений для платы:
Неплохо, правда? Да, ну, тоже определенно не хорошо. Программа запускалась 33 секунды, что довольно много, учитывая, что игра длится всего 90 секунд. Мы хотим использовать все это время для ввода наших решений в игру, а не ждать, пока запустится решатель. Так как же сделать это быстрее?
Проблема с нашим решателем прямо сейчас заключается в том, что мы продолжаем обход, который имеет комбинацию букв, которая никогда не может составить допустимое слово.
Возьмем, к примеру, эту доску:
Используя наш решатель прямо сейчас, мы будем обходить «nbd» и продолжать поиски. Например, мы продолжаем обход и проверяем, есть ли «nbdt» в правильном слове. Нам не следует этого делать, потому что явно ни одно допустимое английское слово не начинается с «nbd».
Используя карту, у нас нет эффективного способа узнать, следует ли продолжать данный обход или нет. Вместо этого мы собираемся использовать структуру данных trie, которая позволит нам это сделать.
Если бы наш список допустимых слов состоял только из geek, geer, geez, geeks и geekt, то наше дерево выглядело бы так (обратите внимание, как слова, начинающиеся с одинаковых букв, имеют общие узлы в дереве):
С помощью дерева, полученного при обходе, мы можем просто проверить, есть ли у текущего узла в дереве дочерние элементы или узлы, подключенные непосредственно под нашим текущим узлом. Если у нашего текущего узла нет дочерних элементов, то мы знаем, что больше нет возможных слов, которые можно было бы использовать при этом обходе, и мы можем прекратить его работу. Если это так, то мы должны продолжать обход, как обычно. Это экономит нам массу вычислений.
Итак, в нашем коде вместо создания карты мы хотим создать дерево:
void make_trie()
{
ifstream dictionary_file;
dictionary_file.open("dictionary.txt");
string word;
if (dictionary_file.is_open()) {
while (!dictionary_file.eof()) {
struct TrieNode *curr = root;
dictionary_file >> word;
for(int i = 0; i < word.length(); i++)
{
string letter = string(1, word[i]);
if((curr->children).find(letter) == (curr->children).end())
(curr->children)[letter] = new TrieNode;
curr = (curr->children)[letter];
if(i == word.length() - 1)
curr -> full_word = true;
}
}
}
}
И в нашей рекурсивной функции мы хотим проверить, находится ли наше текущее слово в нашем дереве:
//if no children, we are at the end of possible valid combination of letters
//for the current traversal
if((node->children).find(letter) == (node->children).end())
return;
word += letter;
visited[row][col] = true;
//check if word is in trie
if(word.length() > 3 && (node->children)[letter]->full_word)
{
ans.push_back(make_pair(word, path));
}
Теперь, когда мы запускаем решатель, мы по-прежнему получаем тот же список допустимых слов, но намного, намного быстрее (менее чем за одну секунду):
С помощью этого решателя мы практически выигрываем в каждой игре:
Вот и все! Мы только что сделали решатель для игры WordHunt в iMessage.
Просмотрите весь полный код с комментариями на моем Github вместе с инструкциями в README о том, как загрузить и запустить решатель самостоятельно. Не стесняйтесь обращаться ко мне, если у вас есть какие-либо вопросы или проблемы!
