Введение
Год назад я приобрел смартфон на базе ОС Android (HTC Hero). Вволю наигравшись с девайсом, решил попробовать написать что-то для платформы Android. Писать решил не абы что, а то, в чем нуждался. В ту пору я еще был студентом и мы на парах часто играли в Балду. Вот поэтому и было решено написать помощника для этой игры, который бы выдавал все подходящие слова для текущего расклада на игровом поле.
Краткие правила игры «Балда»
Имеется поле 5х5 клеток, на котором написано слово или набор слов (букв). Требуется придумать новое слово, которое составляется из имеющихся букв плюс новая буква. Шагать по буквам, при составлении слова, можно влево, вправо, вверх или вниз. Побеждает игрок с самой большой суммой числа букв в написанных им словах. (как закрутил-то..)
Алгоритм поиска слов
Готового алгоритма на просторах интернета обнаружить не удалось. Возможно, потому что игра популярна только в России. Все, что удалось найти по теме — обсуждение на форумах здесь и здесь.
А посему было принято решения изобрести свой велосипед.
Сам алгоритм незамысловат, его можно разложить на несколько шагов.
Шаг 0
Представим ситуацию, когда уже было сделано несколько ходов и игровое поле имеет следующий вид:
Стартовым словом было – «МАСКА». Первый игрок, дописав букву «К», вписал слово «КАСКА», второй – букву «С» и слово «ФАКС». Теперь наш ход.
Шаг 1
Найти все клетки, в которые можно вписать букву. Эти клетки, прилегающие к клеткам с буквами (на рисунке имеют голубой цвет).
Шаг 2
На этом шаге необходимо найти все возможные пути, по которым может «идти» слово. Одна буква в слове должна быть новой, это новая буква будет написана в одной из голубых клеток. Поэтому, для каждой прилегающей клетки построим путь по которому может «идти» слово. На рисунке ниже представлены все возможные пути (два) для стартовой клетки, помеченной красной точкой. Это пути «*МАФ», «*МАКССКА», «*МАСКА» и «*МАССК». Вместо * — любая буква алфавита.
Шаг 3
Поиск подходящего слова в словаре. В словаре должны находиться только существительные в именительном падеже и единственном числе (таковы правила игры). Как не сложно догадаться, от полноты словаря сильно зависит уровень подсказчика. В словаре необходимо найти самое длинное слово, которое соответствует найденным путям и их инверсии. Например, для нашего пути «*МАФ» сгодились бы слова «АМАФ», «ЯМАФ» или «ФАМА», если бы таковые имелись в русском языке. Однако, ни одного слова найти не удалось, поэтому построим все возможные пути для другой стартовой точки.
Например, для этой:
(стартовая позиция отмечена красным кружком)
Алгоритм строит пути методом рекурсивного спуска.
1. Если снизу буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
2. Если справа буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
3. Если сверху буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
4. Если слева буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
Дабы не городить кучу линий разные пути обозначил разными цветами. Цвет меняется при рекурсивном переходе.
Получаем следующие пути: «*ССКА», «*ССАК», «*ССАФ», «*ССАМ». Для инвертированного пути «*ССАК» подходит слово «КАССА».
С гордостью вписываем его:
Реализация
Не буду в подробностях описывать процесс инсталяции среды для разработки и основные концепции программирования под Android, это не раз было разжевано на хабре.
Что полулось
На реализацию все этого ушло немного времени, хотя интерфейс программы оставляет желать лучшего.
Поле для игры:
При нажатии на одну из клеток появляется поп-ап выбора буквы:
При нажатии на кнопку «Ход» запускается алгоритм перебора, результаты которого отображаются в поп-апе:
Как видно, программа предлагает и уже использованные слова (хотя повторы запрещены правилами), это не сложно исправить.
Проблемы
Основной проблемой является низкая скорость подбора. Это вызвано тем, что при достаточном заполнении поля, количество «путей» достигает пары сотен, а количество возможных слов кандидатов (с одной из 33 букв вместо звездочки) достигает десятков тысяч.
Заключение
Исходный код программы не отличается особой красотой ввиду того, что это не только мой первый опыт разработки под Android, но и первый опыт использования Java. Код доступен по ссылке.
Первоначально у меня были планы по допиливанию интерфеса и юзабилити программы, однако так и не выкроил времени.
Нужно отметить, что в андройд-маркете есть программа Blockhead(Балда)(линк на 4pda.ru), однако это игра, и она не может быть использована в качестве помощника.
Год назад я приобрел смартфон на базе ОС Android (HTC Hero). Вволю наигравшись с девайсом, решил попробовать написать что-то для платформы Android. Писать решил не абы что, а то, в чем нуждался. В ту пору я еще был студентом и мы на парах часто играли в Балду. Вот поэтому и было решено написать помощника для этой игры, который бы выдавал все подходящие слова для текущего расклада на игровом поле.
Краткие правила игры «Балда»
Имеется поле 5х5 клеток, на котором написано слово или набор слов (букв). Требуется придумать новое слово, которое составляется из имеющихся букв плюс новая буква. Шагать по буквам, при составлении слова, можно влево, вправо, вверх или вниз. Побеждает игрок с самой большой суммой числа букв в написанных им словах. (как закрутил-то..)
Алгоритм поиска слов
Готового алгоритма на просторах интернета обнаружить не удалось. Возможно, потому что игра популярна только в России. Все, что удалось найти по теме — обсуждение на форумах здесь и здесь.
А посему было принято решения изобрести свой велосипед.
Сам алгоритм незамысловат, его можно разложить на несколько шагов.
Шаг 0
Представим ситуацию, когда уже было сделано несколько ходов и игровое поле имеет следующий вид:
Стартовым словом было – «МАСКА». Первый игрок, дописав букву «К», вписал слово «КАСКА», второй – букву «С» и слово «ФАКС». Теперь наш ход.
Шаг 1
Найти все клетки, в которые можно вписать букву. Эти клетки, прилегающие к клеткам с буквами (на рисунке имеют голубой цвет).
Шаг 2
На этом шаге необходимо найти все возможные пути, по которым может «идти» слово. Одна буква в слове должна быть новой, это новая буква будет написана в одной из голубых клеток. Поэтому, для каждой прилегающей клетки построим путь по которому может «идти» слово. На рисунке ниже представлены все возможные пути (два) для стартовой клетки, помеченной красной точкой. Это пути «*МАФ», «*МАКССКА», «*МАСКА» и «*МАССК». Вместо * — любая буква алфавита.
Шаг 3
Поиск подходящего слова в словаре. В словаре должны находиться только существительные в именительном падеже и единственном числе (таковы правила игры). Как не сложно догадаться, от полноты словаря сильно зависит уровень подсказчика. В словаре необходимо найти самое длинное слово, которое соответствует найденным путям и их инверсии. Например, для нашего пути «*МАФ» сгодились бы слова «АМАФ», «ЯМАФ» или «ФАМА», если бы таковые имелись в русском языке. Однако, ни одного слова найти не удалось, поэтому построим все возможные пути для другой стартовой точки.
Например, для этой:
(стартовая позиция отмечена красным кружком)
Алгоритм строит пути методом рекурсивного спуска.
1. Если снизу буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
2. Если справа буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
3. Если сверху буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
4. Если слева буква и мы там еще не были – переходим туда и рекурсивно повторяем операции
Дабы не городить кучу линий разные пути обозначил разными цветами. Цвет меняется при рекурсивном переходе.
Получаем следующие пути: «*ССКА», «*ССАК», «*ССАФ», «*ССАМ». Для инвертированного пути «*ССАК» подходит слово «КАССА».
С гордостью вписываем его:
Реализация
Не буду в подробностях описывать процесс инсталяции среды для разработки и основные концепции программирования под Android, это не раз было разжевано на хабре.
Что полулось
На реализацию все этого ушло немного времени, хотя интерфейс программы оставляет желать лучшего.
Поле для игры:
При нажатии на одну из клеток появляется поп-ап выбора буквы:
При нажатии на кнопку «Ход» запускается алгоритм перебора, результаты которого отображаются в поп-апе:
Как видно, программа предлагает и уже использованные слова (хотя повторы запрещены правилами), это не сложно исправить.
Проблемы
Основной проблемой является низкая скорость подбора. Это вызвано тем, что при достаточном заполнении поля, количество «путей» достигает пары сотен, а количество возможных слов кандидатов (с одной из 33 букв вместо звездочки) достигает десятков тысяч.
Заключение
Исходный код программы не отличается особой красотой ввиду того, что это не только мой первый опыт разработки под Android, но и первый опыт использования Java. Код доступен по ссылке.
Первоначально у меня были планы по допиливанию интерфеса и юзабилити программы, однако так и не выкроил времени.
Нужно отметить, что в андройд-маркете есть программа Blockhead(Балда)(линк на 4pda.ru), однако это игра, и она не может быть использована в качестве помощника.