Балда — довольно простая и распространённая настольная игра, в которой необходимо составлять слова с помощью букв, расположенных на игровом поле.

Материал из Википедии — свободной энциклопедии

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

Правила игры

Игровое поле представляет собой таблицу 5×5 клеток, в центральный горизонтальный ряд которого ставится произвольное слово из пяти букв, каждая буква которого находится в отдельной ячейке.

Игроки ходят по очереди. Во время своего хода игрок должен подставить в свободную клетку игрового поля букву так, чтобы она располагалась в клетке, смежной уже заполненным клеткам по горизонтали или по вертикали.

После этого необходимо составить слово с использованием установленной буквы. При этом действуют следующие правила:

• Слово должно существовать в словаре.
• Слово не должно совпадать с каким-либо словом, составленным прежде кем-нибудь из игроков.
• Слово должно составляться переходом по смежным клеткам по горизонтали или по вертикали.
• Каждая буква на поле может быть использована в слове не более одного раза.
• В слове должна быть использована поставленная на поле буква.
• Количество очков, получаемое за один ход, равно длине составленного слова.

Игра заканчивается, когда будут заполнены все клетки. Побеждает тот игрок, который набрал наибольшую сумму очков.

Правила соревнования

Соревнование программ будет происходить по круговой системе – каждая программа сыграет с каждой. Для одной пары программ будет сыграно две партии с одним и тем же стартовым словом, но разным порядком хода игроков. По результатам каждой игры программа будет получать очки:

• 2 очка за победу
• 1 очко за ничью
• 0 очков за поражение

Побеждает тот, чья программа наберет наибольшее суммарное количество очков.

Отправка решений

Исходные тексты программ для участия в соревнованиях нужно отправлять на fpmi.game@yandex.by. Этот же адрес можно использовать для вопросов по задаче (не забудьте представиться).

В письме обязательно указать:

• ФИО
• Место учебы, курс/класс
• Приложить исходные файлы решения.

Решения принимаются до 26.04.2012 23:59 по Минскому времени. Решения можно отсылать несколько раз – засчитывается последний вариант.

25 и 26 апреля будут опубликованы промежуточные результаты.

Требования к программе

Программа для участия в соревнованиях может быть написана на следующих языках программирования: Free Pascal 2.x, GCC С/C++ 4.2, Java 1.6, Python 2.6.

Программа должна читать входные данные из файла input.txt и выводить результат в файл output.txt. На выполнение хода программе дается не более 3-х секунд. В случае превышения этого времени программе засчитывается поражение в этой партии. В случае нарушения правил игры или формата ввода/вывода программе также засчитывается поражение. В случае, если не все клетки на поле заняты, но текущий игрок не может сделать ход – ему также засчитывается поражение.

Программа будет запускаться на машине с тактовой частотой не менее 2GHz и с объемом оперативной памяти не менее 2Gb.

Формат словаря  

Вам дается файл dict.txt, содержащий словарь доступных в игре слов. Слова состоят только из строчных букв русского алфавита. В каждой строке файла содержится по одному слову из словаря. Все партии будут проходить с использованием данного словаря. Файл dict.txt будет доступен для чтения вашей программе.

Формат ввода

Текущее состояние поля задается в файле input.txt в виде 5 строк по 5 символов в каждой строке. Каждый символ может быть строчной буквой русского алфавита или точкой. Если символ является точкой, то это означает, что соответствующая клетка таблицы свободна. В противном случае соответствующая клетка таблицы занята этой буквой.

После описания поля в файле содержится список слов, которые уже были использованы в игре. Шестая строка файла содержит единственное число N – количество использованных слов. Последующие N строк содержат использованные слова по одному в строке.

Формат вывода

Описание хода выводится в файл output.txt. Первая строка файла содержит слово, используемое на этом ходу. Это слово должно содержаться в словаре и не быть использованным ранее в игре. Последующие строки описывают клетки таблицы, которые используются для составления этого слова, начиная с первой буквы слова по порядку. Каждая строка содержит два числа – номер строки и номер столбца данной клетки. Количество строк должно соответствовать количеству символов в слове. Ровно одна из описываемых клеток должна соответствовать точке в файле input.txt.

Временные файлы

Ваша программа может создавать временные файлы в своей рабочей директории для сохранения промежуточной информации. Все ваши файлы должны начинаться с yourlastname_ (например, ivanov_tmp.txt). В случае совпадения фамилий, организаторы оставляют за собой право попросить участника добавить еще какой-нибудь префикс.

Пример