Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Поиск решений для игр со словами. Использование бора

Anna | 24.06.2014 | нет комментариев
Существует уйма игр, где игроку нужно искать слова из определенного комплекта букв. Вот две особенно знаменитые из них.
1. 4 фото 1 слов (4 Pics 1 Word) AppStoreGoogle Play
У этой игры достаточно много реализаций, но идея у всех одна.
2. Словомания (Wordsmania) AppStoreGoogle Play
Суть первой игры: даны 4 картинки, длина угадываемого слова и комплект букв, выбирать буквы дозволено в любом порядке.

image

Суть 2-й сводится к тому, что на поле 4х4, заполненном буквами, нужно обнаружить как дозволено огромнее слов, из всякой клетки дозволено передвигаться в следующую по вертикали, горизонтали и диагоналям.

image

Меня заинтересовала идея по программному решению задач, которые ставят эти игры. Я не ставлю цели сделать игру нечестной, это скорее чисто спортивный интерес к поставленной самому себе задаче. Пик популярности этих игр теснее прошёл, следственно не так жутко, если кто-то немножко поиграет нечестно.

Постановка задачи

Если рассматривать задачу больше официально, то нужно реализовать перебор допустимых комбинаций, исходя из правил игры. Будет реализовано два алгорифма перебора для всякой игры. Дальше нужно проверять присутствие этих комбинаций в словаре, для этого необходимо реализовать конструкцию, которая сумеет результативно отвечать на запрос о наличии слова в словаре. Будет применяться бор.

Отчего бор

В стандартных библиотеках C теснее реализованы конструкции, которые умеют стремительно отвечать на единичные запросы, это map и unordered_map (hash map). Но реализация задачи с поддержкой этих конструкций будет уступать по асимптотике бору, так как в нём будут учитываться особенности поставленной задачи. Перебор значений будет представлять из себя дерево, так как рекурсивно из всякой буквы будет пытаться обнаружить следующую. Бор — тоже дерево, следственно поиск слов будет проходить в худшем случае за суммарную длину всех обнаруженных слов, плюс то число итераций, пока алгорифм не дойдёт до несуществующего перехода в словаре, на практике такой переход достигается достаточно стремительно. Результативнее алгорифм будет трудиться, когда есть строка S, содержащая в себе в качестве префикса строку P, принадлежащую словарю, в таком случае поиск будет проходить за длину S, а все остальные P добавятся в результат по ходу поиска S.

Дальше нужно вывести полученные слова в отсортированном виде.

Реализация

Разглядим реализацию решения задачи по частям.

Включения

Нужно обеспечить консольный и файловый ввод-итог, iostream, fstream. Необходимы типовые образцы STL: vector — для построения бора, string и set — для хранения итогов и отсечения идентичных обнаруженных слов, algorithm для сортировки.

Включения

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
Объявления

Для того, Дабы применять русские символы, без включения локализации, Дабы такой код дозволено было легко подогнать под другие кодировки, решено применять примитивный пример строки для ввода и итога. Это пример, получаемый при вводе в консоль русского алфавита ConsoleSample и пример, получаемый при чтении из файла FstreamSample.
Дальше идёт изложение конструкции для всякой вершины бора, она будет беречь переходы по всякой букве, либо 0, если перехода нет, также с поддержкой переменной isLeaf в структуре указывается, что в данной вершине оканчивается какое-либо слово.
Оной длины, следственно спускаемся только до глубины, равной длине строки, дальше спускаться смысла нет. Не забываем на всякой итерации проверить переменную isLeaf, если она равна true и длина обнаруженного слова равна указанному значению, то добавляем слово в set Res.

Обход

void GuessWordBypass(unsigned N, __int8 X, bool Used[], string &S, string W, short &L) {
	if (W.size() > L) return;
	for (__int8 i(0); i != S.size();   i) {
		if (i == X) continue;
		if (!Used[i]) {
			if (Trie[N].child[S[i]] != 0) {
				Used[i] = true;
				GuessWordBypass(Trie[N].child[S[i]], i, Used, S, W   S[i], L);
				Used[i] = false;
			}
		}
		if (Trie[N].isLeaf && W.size() == L) {
			Res.insert(W);
		}
	}
}

И дальше функция, реализующая исходный запуск обхода из всех букв слова.

Запуск

void GuessWord(string &S, short &L) {
	bool *Used = new bool [S.size()];
	memset(Used, 0, S.size());
	for (__int8 i(0); i != S.size();   i) {
		if (Trie[0].child[S[i]] != 0) {
			Used[i] = true;
			GuessWordBypass(Trie[0].child[S[i]], i, Used, S, S.substr(i, 1), L);
			Used[i] = false;
		}
	}
	delete [] Used;
}
Реализация решения для игры Словомания

В целом сам обход не будет ничем отличаться, но различия будут в том, что здесь дозволено перемещаться только в соседние клетки, а не в всякие, также поиск должен находить слова всякий длины. Так как поле размером 4х4 представленно одномерным массивом, то не видимо как переходить в соседние клетки, разглядим как это реализовать.
Если клетка стоит не на границах поля, то с поддержкой добавления чисел от -5 до 5, исключая из них -2, 0 и 2.

image

Если же клетка стоит на границе, то нужно также запретить переходы в другие клетки, выходящие за рубеж.

image

Обход

void WordsmaniaCheatBypass(unsigned N, __int8 X, bool Used[], string &S, string W) {
	__int8 TransitDenied[11] = {0};
	for (__int8 i(-2); i <= 2; i  = 2) 
		TransitDenied[i   5] = true;

	if (X % 4 == 0)
		for (__int8 i(-5); i <= 3; i  = 4) 
			TransitDenied[i   5] = true;

	if (X < 4)
		for (__int8 i(-5); i <= -3;   i) 
			TransitDenied[i   5] = true;

	if (X % 4 == 3)
		for (__int8 i(-3); i <= 5; i  = 4) 
			TransitDenied[i   5] = true;

	if (X >= 12)
		for (__int8 i(3); i <= 5;   i)
			TransitDenied[i   5] = true;

	for (__int8 i(-5); i <= 5;   i) {
		if(TransitDenied[i   5]) continue;
		__int8 tmp = X   i;
		if (!Used[tmp]) {
			if (Trie[N].child[S[tmp]] != 0) {
				Used[tmp] = true;
				WordsmaniaCheatBypass(Trie[N].child[S[tmp]], tmp, Used, S, W   S[tmp]);
				Used[tmp] = false;
			}
		}
		if (Trie[N].isLeaf) {
			Res.insert(W);
		}
	}
}

Запуск

void WordsmaniaCheat(string &S) {
	bool Used[16] = {0};
	for (__int8 i(0); i != 16;   i) {
		if (Trie[0].child[S[i]] != 0) {
			Used[i] = true;
			WordsmaniaCheatBypass(Trie[0].child[S[i]], i, Used, S, S.substr(i, 1));
			Used[i] = false;
		}
	}
}
Функция main

В основной функции инициализируется бор и выполняется основной цикл, в котором обрабатываются запросы. ’1′ либо ’2′ первым доводом, в зависимости от того, какой алгорифм применять, дальше параметры для алгорифма. Позже обработки сортировка и итог итогов. Для первого алгорифма нужно ввести последовательность символов и дальше длину слова, для второго только последовательность, она записывается по строчкам поля, то есть для такого поля нужно ввести строку «сгщатрлпнжилеыйг» (без кавычек).

image

Main

int main() {
	Trie.push_back(NullNode);
	LoadDictonary("Dictonary.txt");

	string Word;
	char mode;

	while (true) {
		cin >> mode;
		switch (mode) {
		case '1':
			short L;
			cin >> Word >> L;
			EncodeString(Word, ConsoleSample);
			GuessWord(Word, L);
			break;
		case '2':
			cin >> Word;
			EncodeString(Word, ConsoleSample);
			WordsmaniaCheat(Word);
			break;
		}
		cout << "==================" << endl;

		for (auto i(Res.begin()); i != Res.end();   i) {
			Output.push_back(*i);
		}
		Res.clear();
		if(mode == '2') sort(Output.begin(), Output.end(), cmp);
		for (auto i(Output.begin()); i != Output.end();   i) {
			for (auto j((*i).begin()); j != (*i).end();   j) {
				cout << ConsoleSample[*j];
			}
			cout << endl;
		}
		cout << "==================" << endl << endl;
		Output.clear();
	}

	return 0;
}

Что дальше

Вот полный код, он проверен под Windows, для других платформ, допустимо, придётся заменить примеры ввода и итога.
А вот словарь малый и огромный словарь (не позабудьте убрать в конце имени цифру 2, если будете применять огромный словарь). Огромный словарь содержит не только исходные формы, он подойдёт для игры Wordament от Microsoft, но там не неизменно на поле стоит по одной букве в клетке. В большинстве случаев хватает малого словаря для 2-х описанных игр, Дабы быть вверху турнирной таблицы.

image

Верю, никто не будет много играть таким образом, все же множество игроков продолжают играть Добросовестно.

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB