Ты мышь. Все ваши друзья-мыши были захвачены, находятся в бессознательном состоянии и попали в лабиринт, в котором есть только один вход / выход. У вас получилась отличная карта лабиринта, так что вы можете найти решение, чтобы спешить и отнести их всех в безопасное место. Тем не менее, лабиринт охраняется системой безопасности, которая будет вызывать предупреждение, если будет достигнут порог 1000
, в результате чего вы будете захвачены и провалите свою спасательную миссию.
Из ваших предыдущих исследований лабиринта каждый квадрат, который вы делаете (т.е. каждое горизонтальное или вертикальное движение - мыши не могут двигаться по диагонали ) добавляет 1
счетчика системы безопасности. Однако, если вы несете вес (блок динамита или мышь без сознания), он вместо этого добавляет, 2
поскольку обнаруживает дополнительное давление. Квадрат входа / выхода не имеет этой системы безопасности, и поэтому не добавляет к прилавку.
У вас есть неограниченный запас динамита, который вы принесли на вход, так что вы можете просто взорвать все стены, чтобы освободить своих друзей. Но вы должны быть осторожны с этим, так как каждый взрыв добавляет 50
к счетчику от сотрясения давления. Кроме того, вы можете носить только одну вещь за один раз, одну мышь или один блок динамита. Поскольку каждый блок динамита может взорвать только одну стену, это означает, что если в стенке несколько стен, вам нужно с пустыми руками вернуться ко входу, чтобы захватить больше.
Проработанный пример
Предположим, наш лабиринт выглядит следующим образом:
######
#M# E#
######
Я буду использовать c
для счетчика. Мы начинаем с E
ntrance, передвигаясь на одну клетку влево, неся динамит c=2
. Мы взрываем динамит, чтобы взорвать стену c=52
. Мы перемещаем два квадрата влево, с пустыми руками, чтобы получить c=54
, и теперь мы стоим на квадрате мыши. Мы подбираем нашего друга и перемещаем 3 квадрата обратно к E
кситу, но последний квадрат не считается, так как у него нет датчиков, так что это всего 2 квадрата с чем-то на нашей спине. Это означает, что когда мы дойдем до выхода с последней мышью c=58
, которой меньше 1000
, и, следовательно, миссия выполнена успешно.
Вызов
Учитывая входной лабиринт, укажите, можете ли вы, герой мыши, успешно спасти всех пойманных в ловушку мышей в рамках ограничений, описанных выше, или же миссия провалена.
вход
- Двухмерный лабиринт в любом приемлемом формате (многострочная строка, массив строк и т. Д.).
- Для этой задачи я буду использовать
#
как внутренние, так и внешние стены,M
для друзей-мышки иE
для входа. - Вход никогда не будет непосредственно примыкать к внутренней стене (всегда будет хотя бы одно пространство, в котором можно свободно перемещаться).
- Вы можете заменить любые печатные символы ASCII, какие пожелаете, при условии их согласованности. Это действительно позволяет использовать два различные символ для внутренних стен против наружных стен, так долго , как вы поддерживать согласованность (например, если вы решили использовать
@
для внутренних стен вместо и оставить#
на внешний вид, каждая внутренняя стенка должна быть@
и каждая внешняя стена#
). - Лабиринт всегда будет полностью ограничен стенами, но не обязательно будет прямоугольным. При желании вы можете предположить, что лабиринт дополнен пробелами для прямоугольного ввода (необязательно).
- Лабиринт может иметь разделы, которые недоступны без динамита.
- Вы не можете динамить внешние стены лабиринта.
Выход
Truthy / falsey значение. Правда для «Да, мышь может спасти любую другую мышь» или Falsey для «Нет, сигнализация будет отключена».
Правила
- Либо полная программа или функция приемлемы.
- Стандартные лазейки запрещены.
- Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).
Примеры
Правдивые примеры, разделенные пустыми строками.
#####
#M E#
#####
######
#M# E#
######
########
#E # M#
# # #
# # #
# #
########
#############################
# ## # # #
# M ## M # # #
# ## # M # E #
#M ## # # #
#############################
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############
Ложные примеры, разделенные пустыми строками
#############################
#M ## ## ## #
# M ## M ## ## #
# ## ## M ## E #
#M ## ## ## #
#############################
#############################
########
########
# # #
# M # M#
########
#####
# M #
#####
#####
#####
#####
###################
# # # ## ## # # #
#M#M#M## E ##M#M#M#
# # # ## ## # # #
###################
#######
######
#####
####
# M#
####
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############
источник
Ответы:
Perl,
216215 байтВключает +2 для
-0p
Дайте вход на STDIN. Используйте
%
для наружных стен,#
для внутренних стен,0
для пустых пространств,8
для мышей иr
для начальной позиции. Все доски должны быть дополнены так, чтобы они образовывали прямоугольник. Вы можете преобразовать и запустить примеры как:dynamite.pl
:Замените
\xhh
побеги на заявленный счет.Программа не может реально обрабатывать сложные случаи. В частности, он не может справиться ни с одним из случаев отказа. Это связано с тем, что существует слишком много разных способов взорвать внутренние стены или подобрать мышей, поэтому поиск становится слишком широким и использует слишком много памяти, хотя он по крайней мере достаточно умен, чтобы никогда не обрабатывать одно и то же состояние несколько раз. Предел давления должен быть снижен до
100
или около того для несколько терпимого времени выполнения и использования памяти.объяснение
Я использую битовую комбинацию символа для представления состояния поля:
Например, hero (
01000000
), несущий Dynamite (00000001
), должен находиться в месте, где он может ходить (00010000
), и мы хотим, чтобы все значения были пригодны для печати ASCII (00100000
). Взятие побитовыхor
всех этих битовых масок дает01110001
код ASCII дляq
. Всего это становится ::В программе будет учитываться только движение героя вправо (вращение, описанное ниже, позаботится о других направлениях) Битовые маски были тщательно подобраны таким образом, чтобы герой всегда был представлен буквой, а место, в которое он может переместиться, - цифрой (за исключением того, что герой дома несет жертву, но, опять же, это преднамеренно, так что единственным ходом героя будет падение жертва). Таким образом, герой, который может двигаться вперед, соответствует
/\pL\d/
. Соответствующая подстрока должна быть модифицирована таким образом, чтобы герой и то, что он несет, были удалены из первого символа и добавлены ко второму, что можно сделать с помощью побитового значенияxor
с одинаковым значением для обоих символов. Значение xor состоит из бита героя (01000000
), бита динамита (00000001
) и бита мыши для переноса (00000100
). Вместе ониor
в01000101
который является ASCIIE
. Итак, перемещение героя становится:Герой может взорвать стену , если он стоит прямо перед ним и несет динамит (
q
,s
илиy
). Герой потеряет свой динамит (xor
с00000001
), и стена#
изменится на проход0
(xor с00010011
), поэтомуЧтобы справиться с другими направлениями, вся доска вращается (повернутая доска заканчивается
$o
):Помимо перемещения у героя также есть ряд других вариантов, которые он может сделать:
Это сделано
Доска заканчивается, если герой дома не несет ничего (
x
) и больше нет жертв для спасения (нет2
). Это может быть удобно проверено с помощьюКак только доска решена, я хочу запомнить это состояние и в конце напечатать его. Для этого я несу флаг «решено»
$\
и печатаю его в конце программы без печати$_
, поэтомуСостояния, которые должны обрабатываться при давлении 0, сохраняются
@0
, при давлении 1@1
и т. Д. Текущее давление сохраняется$%
. Использование$n
или что-то вроде этого было бы короче, но код не работает, если переменная не инициализируется чем-то, потому что в противном случае автовивификация изменится$n
на ссылку ARRAY. Цикл по состояниям при определенном давлении выполняется с использованием а,for
а неmap
потому, что с помощью afor
вы можете расширить массив, пока он все еще зацикливается, и выберете новые элементы. Это необходимо, потому что повороты и выбор героя в одном поле происходят за 0 раз и заканчиваются в одном массиве давления. Таким образом, цикл для данного давления осуществляетсяЭто повторяется до тех пор, пока давление не достигнет 1000 или не будет найдено решение:
Осталось только добавить вновь обнаруженные состояния в соответствующие им массивы давления. Это будет сделано с помощью подпрограммы
f
. Мы хотим добавить состояние, только если оно еще не было просмотрено. Состояния, которые были замечены ранее, сохраняются в%a
так:$n
представляет новое давление для государства. Я выведу это из состояния, которое все еще имеют переменные регулярного выражения в результате действия героя, ведущего к этому вызову:Это приводит к следующей формуле
$n
:Все замены получают
r
модификатор, поэтому они возвращают измененное состояние и оставляют текущее состояние в$_
покое.f
затем вызывается в этом измененном состоянии, так что вы получите код какПоскольку при вычислении
$n
потребностей в переменных регулярного выражения они должны по умолчанию не задавать значения, если подстановки ничего не меняют (поскольку условие для их запуска не выполняется). Я также не должен брать какие-либо переменные регулярного выражения из предыдущего цикла. Поэтому подстановки заключены в{}
блоки для сохранения и восстановления состояния регулярного выражения. Вот как вы получаете такие заявления, какВ частности, вращение так упаковано, что вызывает
f
без регулярных выражений и получает вклад давления 0.Единственное, что еще нужно сделать, это
@0
начать с начального состояния в началеЭто находится в основном цикле, поэтому он также пытается добавить
$_
к более поздним массивам давления, но, поскольку начальное состояние уже будет в,%a
ничего не произойдет.Вместе все это в основном находит самое короткое решение, используя алгоритм Дейкстры . Хотя есть потенциальная проблема. Текущий код не будет добавлять состояние, если он будет заново открыт с более низким давлением, чем первое обнаружение. Я не смог построить доску, которая могла бы вызвать это, но я также не смог доказать, что это невозможно.
источник
JavaScript,
863834785781 байтСохранено 29 байтов благодаря ETHproductions
Сохранено 53 байта благодаря Иордании
Принимает ввод в виде многострочной строки.
Это определяет анонимную функцию, которая использует рекурсивную функцию,
f
чтобы определить, отключили ли вы тревогу, прежде чем получить все мыши.f
возвращается,1000
если давление выше 1000 (чтобы избежать бесконечной рекурсии), возвращает давление, если больше нет мышей для спасения и мыши на выходе, и возвращает минимальное давление всех возможных ходов из текущего состояния в противном случае. Он использует массивL
для отслеживания уже посещенных позиций, где,L[pos]==0
если он посещен, и неопределенный, если это не так. Это может не быть необходимым, но это препятствует тому, чтобы мышь делала бесполезные движения и выбрасывала ошибки рекурсии по крайней мере. (Это означает, что вы должны переопределить,L
если вы тестируете это несколько раз)Это использует формат в вопросе, кроме того, что он требует, чтобы вы использовали другой символ для внешних стен. (Что-нибудь кроме
# MEmecd
)Более читаемая версия:
источник
s in L|p > 999
.eval
и заменить@
с$1
(не уверен , если это будет работать, но вы пишете$1
много)f
однострочник:f=(...)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...
$1
18 раз и.replace("@","$1")
составляет 18 байт. Я не вижу способа осуществить это.