Международный конкурс программистов

Форум для обсуждения вопросов математики

Модератор: Admin

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Международный конкурс программистов

Сообщение omega » Вт мар 06, 2012 11:13 am

Весьма интересный конкурс программистов проходит сейчас на сайте
http://infinitesearchspace.dyndns.org/samegame

В качестве задачи предложена древняя игра.
Задачу можно решать вручную, для этого организаторы конкурса предоставили хорошую программу (скачать на главной странице конкурса, см. ссылку).

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

В задаче предложено 25 вариантов заданий, то есть 25 исходных позиций для игры (используются от 3 до 7 цветов).

Может быть, кто-нибудь из программистов заинтересуется конкурсом.

Сейчас в конкурсе зарегистрированы 8 россиян. Правда, достаточно активны только четверо.

Я играю вручную. Программу написать не получилось.
Пока набрала чуть больше 19 баллов (23-ье место из 78 участников).

Конкурс продлится до 13 апреля.

Vladimir__
Сообщения: 1660
Зарегистрирован: Вс дек 21, 2003 8:52 am

Re: Международный конкурс программистов

Сообщение Vladimir__ » Вт мар 06, 2012 11:27 am

omega писал(а):...В качестве задачи предложена древняя игра...

А в чем суть игры?

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Вт мар 06, 2012 11:56 am

Так на странице по указанной ссылке всё написано :)

Ну, могу кратко рассказать. Эта игра, кажется, тетрикс называется. Я видела, как в неё играли ещё на старых ЭВМ.

На доске размером nxm расположены квадратики нескольких цветов (на конкурсе используются варианты с 3-7 цветами). Надо удалять блоки, состоящие из прилегающих друг к другу квадратиков одного цвета. При этом оставшиеся квадратики падают вниз на освободившееся место, а если оказался свободным целый столбец, то всё сдвигается влево.
Вот, собственно, и всё.
При удалении каждого блока начисляются очки (если в удалённом блоке k квадратиков, начисляется (k-1)^2 очков). Цель игры - набрать как можно больше очков.
При этом если удастся очистить всю доску, получаете бонус - дополнительное количество очков.

Vladimir__
Сообщения: 1660
Зарегистрирован: Вс дек 21, 2003 8:52 am

Сообщение Vladimir__ » Вт мар 06, 2012 12:03 pm

omega писал(а):...Эта игра, кажется, тетрикс называется. Я видела, как в неё играли ещё на старых ЭВМ...

Тетрис: [url]http://ru.wikipedia.org/wiki/Тетрис[/url]

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Вт мар 06, 2012 12:35 pm

Да, похоже, но вариант конкурсной игры намного проще.

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Ср мар 07, 2012 1:22 pm

Хочу показать задачку для конкретики. Эта позиция возникла в игре № 7.

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

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Чт апр 19, 2012 5:35 am

Конкурс закончился.

Предлагаю вниманию форумчан небольшую статью о конкурсе:
http://www.natalimak1.narod.ru/contest4.doc

На этой странице идёт обсуждение алгоритмов решения задачи и итогов конкурса:
http://infinitesearchspace.dyndns.org/c ... -aftermath

Примерно через месяц начнётся новый конкурс.

Ау! Программисты!
Приглашаю вас к участию в международных конкурсах программистов.
Это очень интересно! Поверьте мне :wink:

Я уже в четырёх конкурсах приняла участие.
О прошлом конкурсе даже книгу написала
http://narod.ru/disk/40246727001/contest.rar.html

omega
Сообщения: 61
Зарегистрирован: Вт мар 06, 2012 11:04 am

Сообщение omega » Пт апр 20, 2012 6:46 am

Объявлена дата начала следующего конкурса - 1 июня сего года.

Программисты, на старт!

Если задача будет мне по силам, поучаствую.

Здесь небольшой экскурс в историю конкурсов, в которых приняла участие:
http://www.natalimak1.narod.ru/contests.htm