Самый простой алгоритм для создания Филворда (Часть 1)

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Привет, Хабровцы. В этой статье я хочу поделиться с вами немного своим опытом и показать вам мой простой алгоритм, который я придумал для создания Филворда.


Под «Филвордом» я буду иметь ввиду эту многим знакомую игру.



В игре есть поле размером обычно NxN заполненное словами. Наша цель — найти все слова.
В нашей версии не будет букв в поле, которые не принадлежат ни одному слову и служат для сбивания игрока, а также не будет букв, которые принадлежат сразу нескольким словам. Обычный классический Филворд. И так, задача поставлена. Нужно решать.


Первым делом я всегда разбиваю задачу на подзадачи. Для решения этой задачи мне понадобится:


  1. БД со словами.
  2. Алгоритм, который вставляет слова в поле.
  3. Алгоритм, который проверяет выбранное пользователем слово на корректность. К примеру мы в поле поместили слово «программирование», а пользователь увидел там «мир» и выделяет это слово. Пользователь прав – такое слово есть, но мы его не загадывали. Нам нужен алгоритм, который будет проверять догадки пользователя и говорить ему прав он или нет.

Все, игра простая поэтому пунктов тоже не много. Начнем выполнять по порядку.


1) БД со словами.


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


Пример

words_2
-Як
-Ад
-Еж
-Юг
words_3
-Кот
-Мох
-Рот
-Ток
words_4
-Нора
-Коза
words_5
-Кадык
-Кумыс


И т.д. (Будем считать, что в БД у нас тысячи слов любой длины и сложности и все они по длине в нужных таблицах хранятся).


Размер для поля установим 5x5.


Теперь немного продумаем логику выборки из этой БД. Нам нужно заполнить поле 5x5, значит нам нужны слова, длинна которых в сумме будет = 25. Здесь я вижу 2 способа по выбору слов:


  1. Мы задаем кол-во слов в нашем поле и тогда подбираем это N-ое кол-во слов так, чтобы сумма их букв = 25.
  2. Мы не указываем кол-во слов и тогда мы берем слова из БД, пока сумма букв выбранных слов не станет = 25.

1 способ


У нас есть кол-во слов N, которое должно быть в Филворде. Пусть N = 6. Я предлагаю искать среднюю длину слова путем деления свободных мест на кол-во слов.


25/6 = 4. Выбираем случайное слово из таблицы words_4 и ложем в массив слов.
Уменьшаем N на 1, а от числа свободных мест в поле отнимаем среднюю длину слова.
25 – 4 = 21
6-1 = 5;
Все это зацикливаем пока N!=1;


Примерная реализация на С++ тут

giveWord() – Некий волшебный метод, возвращающий случайное слово из БД той длинны, которая была передана в метод в качестве параметра.


wordsArray.Push() – Некий волшебный метод, который ложит слова переданное в качестве параметра в массив.


N=6;
freePlace =25;
While(N!=1)
{
wordsArray.Push( giveWord( freePlace/N ) ); // Ложим слово в массив
freePlace-= freePlace/N; // Уменьшаем кол-во свободных мест
N--; //Уменьшаем кол-во слов
}

И вот после выполнения данного цикла у нас будет массив wordsArray, в котором будет лежать 5 слов длиной (4,4,4,4,4).


После выполнение цикла нам останется лишь добавить последнее слово, которое = freePlace.


wordsArray.Push( giveWord( freePlace ) );

Получилось (4,4,4,4,4,5). Сумма =25. Условие выполнено.


Но вот мне не нравится, что все слова будут одной длины. Хотелось бы чтобы длинна слов была разной.


Как это сделать зависит уже от вашей безграничной фантазии.


Я рандомно генерировал бы число от 0 до 1 и отнимал или прибавлял (знак я тоже регулировал бы случайным числом от 0 до 1) эту случайно сгенерированную 0 или 1 к freePlace / N. Это могло бы привнести тот самый необходимый хаос и при этом не так уж сложно реализуется.


2 способ


Тут у нас уже нет кол-ва слов, от которых можно плясать. Вообще ничего нет кроме одного числа – 25. У нас не хватает чисел для работы, придется добавить чисел. Нам нужно как-то установить кол-во слов. Генерировать рандомно кол-во нам не подходит, как бы глупо это не звучало, но такой способ слишком рандомный из-за чего контроль усложняется. Нужно также помнить, что игроку не будет интересно играть на поле в 25 ячеек, в котором всего 2 слова, каждое из которых имеет длину 12 и 13 букв. Поэтому здесь я предлагаю вашему вниманию следующий лайфхак. Вспоминаем что 25 ячеек – это поле размера 5x5, 9 ячеек – это поле размером 3x3, улавливаете мысль? Верно, берем эти коэффициенты за кол-во слов на поле и применяем 1-ый способ описанный выше. В итоге у нас получится удовлетворяющее кол-во слов для заполнения поле и они будут нормальной длинны.


Итак. 1/3 часть мы выполнили. У нас есть БД и алгоритм для формирования массива слов, которыми мы будем заполнять наше поле и 1-ая часть на этом завершается. В след. части мы будем эти слова пихать в поле так, чтобы они все влезли.

Источник: https://habr.com/ru/post/487630/


Интересные статьи

Интересные статьи

Это подборка текстовых материалов и тематических подкастов с участием представителей Университета ИТМО — студентов, аспирантов, научных сотрудников и преподавателей. Мы обсуждаем науч...
Предыстория Когда-то у меня возникла необходимость проверять наличие неотправленных сообщений в «1С-Битрикс: Управление сайтом» (далее Битрикс) и получать уведомления об этом. Пробле...
Применением IoT в фитнес-трекерах, колонках, пылесосах уже никого не удивишь. Думали ли вы, что различные датчики можно установить в мусорные контейнеры и мусоровозы для контроля выво...
В мультфильме «Ледниковый период» мы наблюдаем за веселыми приключениями группы разношерстных животных во время глобального оледенения. В реальности же условия были гораздо более суровыми, а ...
Недавно я вернулся к анализу погрешностей чисел с плавающей запятой, чтобы усовершенствовать некоторые детали в следующей редакции книги Physically Based Rendering. Числа с плавающей запятой — ...