Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.
Задача вполне понятная, так что дерзайте.
В задачу вносились изменения: вода, телепорты, борода и суперкамни.
Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.
Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012
Карта — это сетка m×n клеток, координата (1,1) расположена внизу и слева.
Каждая клетка содержит один из следующих символов:
Ничто не может проникнуть сквозь стену. Ничто не может выйти за пределы поля m×n. Робот может копать землю, собирать λ и двигать камни. Камни падают. Камни могут убить робота.
Пример начального состояния:
Если координаты робота (x, y):
Двигаться можно в клетку с открытым выходом, в пустую, в клетку с землёй и клетку с λ. Ещё можно двигаться (только налево и направо) в клетку с камнем, если за камнем пустое место. После ухода из клетки робот всегда оставляет в клетку пустоту.
После движения робота проходит шаг симуляции. Во время этого этапа всегда читается старое состояние и пишется в новое. В следующем порядке по координатам: (1, 1), (2, 1), ..., (n, 1), (1, 2)… (n, m).
Правила проверяются по порядку, сверху вниз. Если одно сработало, то следующее уже не сработает.
Если на карте больше нету λ, все закрытые выходы открываются.
Если под только что упавшим камнем стоял робот — робот ломается, это — поражение.
За один шаг симуляции камни падают на 1 клетку вниз.
Иногда камни с разных сторон могут упасть в одну клетку. В этом случае в этой клетке теперь лежит 1 камень.
Ввод с 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 Гамильтонов цикл
Задача вполне понятная, так что дерзайте.
В задачу вносились изменения: вода, телепорты, борода и суперкамни.
Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.
Ссылка на красивый симулятор: 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 Гамильтонов цикл
