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

в 23:12, , рубрики: haskell, icfpc, Программирование, Спортивное программирование, функциональное программирование

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

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

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

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

  • Робот пропускает любые неизвестные ему символы (а известны ему только 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/

Автор: jerom

* - обязательные к заполнению поля