Задача конкурса ICFPC-2012: робот и λ

Автор оригинала: ICFPC 2012
  • Перевод
Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.

Задача вполне понятная, так что дерзайте.

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

Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.


Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012


Основные правила


  • Робот пропускает любые неизвестные ему символы (а известны ему только L, R, U, D, W, A.
  • Если Робот не может выполнить команду, он этот ход просто ничего не делает.
  • После хода робота обновляется карта по правилам, описанным ниже.
  • После обновления карты проверяются условия завершения работы.


Описание карты

Карта — это сетка m×n клеток, координата (1,1) расположена внизу и слева.

Каждая клетка содержит один из следующих символов:
  1. R — робот
  2. * — камень
  3. L — закрытый выход
  4. . — земля
  5. # — стена
  6. \ — λ
  7. O — открытый выход
  8. " " — пробел, пустая клетка

Ничто не может проникнуть сквозь стену. Ничто не может выйти за пределы поля m×n. Робот может копать землю, собирать λ и двигать камни. Камни падают. Камни могут убить робота.

Пример начального состояния:
#######
#..***#
#..\\\#
# ..**#
#.*.*\#
LR....#
#######

Команды робота

Если координаты робота (x, y):
  1. L — налево, в (x-1, y)
  2. R — направо, в (x+1, y)
  3. U — вверх, в (x, y+1)
  4. D — вниз, в (x, y-1)
  5. W — ждать, ничего не делать
  6. A — прервать исследование шахты


Двигаться можно в клетку с открытым выходом, в пустую, в клетку с землёй и клетку с λ. Ещё можно двигаться (только налево и направо) в клетку с камнем, если за камнем пустое место. После ухода из клетки робот всегда оставляет в клетку пустоту.

Обновление карты (симуляция)

После движения робота проходит шаг симуляции. Во время этого этапа всегда читается старое состояние и пишется в новое. В следующем порядке по координатам: (1, 1), (2, 1), ..., (n, 1), (1, 2)… (n, m).

Правила проверяются по порядку, сверху вниз. Если одно сработало, то следующее уже не сработает.
  1. Под камнем пустота — камень падает на 1 клетку вниз.
  2. Под камнем — камень, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
  3. Под камнем — камень, слева пусто и слева внизу пусто — камень падает по диагонали влево.
  4. Под камнем — λ, справа пусто и справа внизу пусто — камень падает по диагонали вправо.
  5. Остальные клетки не трогаются.


Если на карте больше нету λ, все закрытые выходы открываются.

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

За один шаг симуляции камни падают на 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 Гамильтонов цикл
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 15

    +2
    Дописал, что задача NP-полна даже без усложнений.
      0
      За собранную λ в момент достижения выхода +50

      Это как?
        +2
        Чтобы тот кто собрал 5 лямбд и вышел был круче чем тот кто собрал 5 лямбд и не вышел
        0
        За каждую собранную в процессе лямбду при полном выполнении задания
          +1
          За собранную λ в момент выполнения команды A +25
          За собранную λ в момент достижения выхода +50


          Точнее сказать: «за каждую собранную ранее лямбду...».
            +12
            Ну вот, а сказку вы перевести поленились :(
            В общем, прологом к задаче является история о том, что из-за возросшей популярности функциональных ЯП, многие языки начали перенимать различный функционал ФЯП, вроде лямбда-функций. Это привело к тому, что мировые запасы лямбд крайне быстро истощаются, и, по прогнозам аналитиков, закончатся уже к октябрю. Однако, организаторы обнаружили огромнейшие природные запасы лямбд в Lomond Hills в Шотландии и даже составили карты подземных шахт. Соответственно, ваша задача: спасти мир от лямбда-кризиса, запрограммировав робота.
            Вот такое вот веселье.
              0
              Здорово :)
              +2
              Это ж Supaplex!
                +1
                Он самый. Вот реализация по текущей задаче: icfpcsupaplex.narod.ru/
                  0
                  Кажется, я знаю кто победит.
                0
                Я думаю, что единственный «правильный» способ — это перебрать все возможные ходы, отсекая последовательности, не изменяющие никак ситуацию в игре или приводящие к проигрышному положению (например, когда на карте есть лямбды/открытые выходы, до которых нельзя добраться), и выбирая выигрышные решения с наименьшим числом ходов. Но это потребует ужасно много ресурсов, в то время, как имеется только 150сек.

                Интересно было бы посмотреть программы победителей, когда конкурс закончится.
                0
                Я только выход из лабиринта делал, волновой алгоритм тут не канает, да?=(
                  0
                  Почему не канает? Как способ найти лямбду — вполне.
                    0
                    Если бы не камни можно было бы и его использовать — а так ;) То попадаешь в состояние «слишком много вершин» в следующей волне, то в состояние «почему там мало вершин» в следующей волне ;)

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

                Самое читаемое