[Из песочницы] Самый простой алгоритм для создания Филворда (Часть 1)09.02.2020 22:33

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

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

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

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

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

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

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

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

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

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

Теперь немного продумаем логику выборки из этой БД. Нам нужно заполнить поле 5×5, значит нам нужны слова, длинна которых в сумме будет = 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;

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 ячеек — это поле размера 5×5, 9 ячеек — это поле размером 3×3, улавливаете мысль? Верно, берем эти коэффициенты за кол-во слов на поле и применяем 1-ый способ описанный выше. В итоге у нас получится удовлетворяющее кол-во слов для заполнения поле и они будут нормальной длинны.

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

© Habrahabr.ru