Задача вполне понятная, так что дерзайте.
В задачу вносились изменения: вода, телепорты, борода и суперкамни.
Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.
Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012
Основные правила
- Робот пропускает любые неизвестные ему символы (а известны ему только L, R, U, D, W, A.
- Если Робот не может выполнить команду, он этот ход просто ничего не делает.
- После хода робота обновляется карта по правилам, описанным ниже.
- После обновления карты проверяются условия завершения работы.
Описание карты
Карта — это сетка m×n клеток, координата (1,1) расположена внизу и слева.
Каждая клетка содержит один из следующих символов:
- R — робот
- * — камень
- L — закрытый выход
- . — земля
- # — стена
- \ — λ
- O — открытый выход
- " " — пробел, пустая клетка
Ничто не может проникнуть сквозь стену. Ничто не может выйти за пределы поля m×n. Робот может копать землю, собирать λ и двигать камни. Камни падают. Камни могут убить робота.
Пример начального состояния:
####### #..***# #..\\\# # ..**# #.*.*\# LR....# #######
Команды робота
Если координаты робота (x, y):
- L — налево, в (x-1, y)
- R — направо, в (x+1, y)
- U — вверх, в (x, y+1)
- D — вниз, в (x, y-1)
- W — ждать, ничего не делать
- A — прервать исследование шахты
Двигаться можно в клетку с открытым выходом, в пустую, в клетку с землёй и клетку с λ. Ещё можно двигаться (только налево и направо) в клетку с камнем, если за камнем пустое место. После ухода из клетки робот всегда оставляет в клетку пустоту.
Обновление карты (симуляция)
После движения робота проходит шаг симуляции. Во время этого этапа всегда читается старое состояние и пишется в новое. В следующем порядке по координатам: (1, 1), (2, 1), ..., (n, 1), (1, 2)… (n, m).
Правила проверяются по порядку, сверху вниз. Если одно сработало, то следующее уже не сработает.
- Под камнем пустота — камень падает на 1 клетку вниз.
- Под камнем — камень, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
- Под камнем — камень, слева пусто и слева внизу пусто — камень падает по диагонали влево.
- Под камнем — λ, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
- Остальные клетки не трогаются.
Если на карте больше нету λ, все закрытые выходы открываются.
Если под только что упавшим камнем стоял робот — робот ломается, это — поражение.
За один шаг симуляции камни падают на 1 клетку вниз.
Иногда камни с разных сторон могут упасть в одну клетку. В этом случае в этой клетке теперь лежит 1 камень.
Условия завершения
- Робот вошёл в открытый лифт — WIN
- Робот выполнил команду A — WIN
- Робота раздавило камнем — LOSE
Ввод/вывод
Ввод с stdin, вывод в stdout
Если некоторые строки короче максимальной по длине строки, то они считаются дополненными пробелами справа.
На каждой карте в начале нет открытых выходов. Есть ровно 1 робот и ровно 1 закрытый выход.
Карта может быть 1000×1000 и более.
Начисление очков
За каждый шаг -1
За собранную λ +25
За собранную λ в момент выполнения команды A +25
За собранную λ в момент достижения выхода +50
Скрипт для тестирования своих вариантов прохождения тестовых карт: validator
Лимиты
Программа должна работать на 32bit Debian-linux c 1 Gb RAM.
Через 150 секунд программа получает SIGINT, после этого у неё есть 10 секунд на вывод ответа.
После этих 10 секунд SIGKILL и 0 очков.
В течение конкурса будет от 1 до 4 изменений правил.
Детали на английском: icfpcontest2012.wordpress.com
Первое изменение правил: вода
Некоторые шахты начало затапливать!
Теперь после описание карты может идти пустая строка и потом 3 параметра (по 1 на строке):
Water 0
Flooding 0
Waterproof 10
(0, 0, 10) — дефолтные значения.
Water указывает на начальное значение уровня воды (помним, что координаты мы считаем с 1, а уровень воды может быть и 0).
Flooding — скорость прибывания воды. Если 0 — вода не прибывает совсем. Если N>0, то тогда ровно после N шагов уровень воды увеличивается на 1.
Waterproof — уровень защиты робота, сколько шагов без выныривания он может пройти под водой. Как только вынырнул — счётчик шагов сбрасывается и можно нырять опять.
Робот считается находящимся под водой, если его y координата <= уровня воды.
Если робот проводит под водой больше, чем Waterproof шагов, он ломается.
Второе изменение правил: телепорты
В игру добавлены телепорты (в доке названы трамплинами). Вход телепорта обозначается буквами A..I, выход телепорта — цифры 1..9.
После входа в телепорт исчезает и вход телепорта, и его выход.
Какой вход ведёт к какому выходу описывается после карты фразами:
Trampoline A targets 1
Trampoline B targets 1
Trampoline C targets 2
Третье изменение правил: биомасса и бритвы
Добавлена борода — W и бритва — !. В конце карты теперь написано, сколько у робота с собой бритв и с какой скоростью растёт борода:
Growth 15
Razors 2
Значение роста (g) по дефолту — 25, количества бритв — 0.
Каждые g шагов борода заполняет 8 соседних клеток, если они пусты (то есть, включая диагональ).
Бритва — единственное средство борьбы с бородой. После выполнения команды S бритва (если она есть у робота) применяется и очищает от бороды 8 соседних клеток.
Последнее изменение правил: камни высшего порядка
Добавлены @ — камни высшего порядка, внутри которых скрыты λ. При падении с любой высоты камень разбивается и на его месте появляется λ.
Об оценке сложности
Обратите внимание, что задача очень похожа на усложнённый Boulder Dash, прохождение которого, в общем случае, как доказано, NP-полная задача.
Доказательство достаточно простое: существую такие лабиринты, решение которых эквивалентно нахождению гамильтонова цикла в графе, а это известная задача: wiki Гамильтонов цикл