Você é um rato. Seus amigos do mouse foram capturados e estão inconscientes e presos em um labirinto que tem apenas uma entrada / saída. Por acaso, você tem um mapa perfeito do labirinto, para poder planejar uma solução para entrar e levá-los todos em segurança. No entanto, o labirinto é protegido por um sistema de segurança que acionará um alerta se um limite 1000for atingido, fazendo com que você seja capturado e falhe em sua missão de resgate.

De suas investigações anteriores do labirinto, cada quadrado que você pisa (ou seja, cada movimento horizontal ou vertical - os ratos não podem se mover na diagonal ) é adicionado 1ao balcão do sistema de segurança. No entanto, se você está carregando um peso (um bloco de dinamite ou um amigo inconsciente do mouse), ele adiciona, 2pois detecta a pressão adicional. A praça de entrada / saída não possui esse sistema de segurança e, portanto, não é adicionada ao balcão.

Você tem um suprimento ilimitado de dinamite que você trouxe para a entrada, então você pode simplesmente explodir todas as paredes para libertar seus amigos. Mas você precisa ser cauteloso ao fazer isso, pois cada explosão aumenta 50o contador devido à pressão concussiva. Além disso, você só pode carregar uma coisa de cada vez, um mouse ou um bloco de dinamite. Como cada bloco de dinamite pode detonar apenas um espaço de parede, isso significa que, se houver várias paredes seguidas, você precisará fazer uma viagem de mãos vazias de volta à entrada para obter mais.

Exemplo elaborado

Suponha que nosso labirinto se pareça com o seguinte:

######
#M# E#
######

Vou usar cno balcão. Começamos no Entrance, movemos um quadrado à esquerda enquanto carregamos dinamite c=2. Nós detonamos a dinamite para explodir a parede c=52. Movemos dois quadrados para a esquerda, de mãos vazias, para chegar c=54, e agora estamos de pé no quadrado do mouse. Pegamos nosso amigo e movemos 3 quadrados de volta para o Exit, mas o último quadrado não conta, pois não possui sensores, então são apenas 2 quadrados com algo nas costas. Isso significa que quando chegamos à saída com o mouse final c=58, que é menor que 1000e, portanto, a missão é bem-sucedida.

Desafio

Dado um labirinto de entrada, verifique se você, o herói do mouse, pode resgatar com êxito todos os ratos presos dentro das restrições descritas acima ou se a missão é uma falha.

Entrada

• Um labirinto 2D em qualquer formato aceitável (cadeia de linhas múltiplas, matriz de linhas, etc.).
• Para esse desafio, #usarei as paredes internas e externas, Mos amigos do mouse e Ea entrada.
• A entrada nunca será imediatamente adjacente a uma parede interna (sempre haverá pelo menos um espaço para se movimentar livremente).
• Você pode substituir qualquer caractere ASCII imprimível que desejar, desde que consistente. Isso permite que você use dois símbolos diferentes para paredes internas versus paredes externas, desde que mantenha a consistência (por exemplo, se você optar por usar @paredes interiores e deixar #para o exterior, todas as paredes internas devem ser @e todas as paredes externas #)
• O labirinto sempre será completamente delimitado por paredes, mas não é necessariamente retangular. Se desejar, você pode assumir que o labirinto é preenchido com espaços para criar uma entrada retangular (opcional).
• O labirinto pode ter seções inacessíveis sem dinamite.
• Você não pode dinamitar as paredes exteriores do labirinto.

Saída

Um valor de verdade / falsey . Na verdade, para "Sim, o mouse pode resgatar qualquer outro mouse" ou Falsey para "Não, o sistema de alarme será acionado".

As regras

• Um programa completo ou uma função são aceitáveis.
• As brechas padrão são proibidas.
• Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

Exemplos

Exemplos de verdade, separados por linhas em branco.

#####
#M E#
#####

######
#M# E#
######

########
#E  # M#
#   #  #
#   #  #
#      #
########

#############################
#    ##      #       #      #
#  M ## M    #       #      #
#    ##      #   M   #    E #
#M   ##      #       #      #
#############################

###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############

Exemplos de Falsey, separados por linhas em branco

#############################
#M   ##      ##      ##     #
#  M ## M    ##      ##     #
#    ##      ##  M   ##   E #
#M   ##      ##      ##     #
#############################
#############################
                     ########
                     ########
                     #   #  #
                     # M # M#
                     ########

              #####
              # M #
              #####
              #####
              #####
              #####
###################
# # # ##   ## # # #
#M#M#M## E ##M#M#M#
# # # ##   ## # # #
###################
#######
######
#####
####
# M#
####

###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############

Perl, 216 215 bytes

Inclui +2 para -0p

Dê entrada no STDIN. Use %para paredes externas, paredes #internas, 0espaços vazios, 8ratos e rposição inicial. As placas inteiras devem ser acolchoadas para formar um retângulo. Você pode transformar e executar os exemplos como:

cat dynamite.txt | perl -p0e 's/.+/$a^=$&/egr;s//sprintf"%-*s",length$a,$&/eg;1while/\n/,s/^ *\K#|#(?= *$)|^ *.{@{-}}\K#|\A[^\n]*\K#|#(?=[^\n]*\n\z)|#(?=.{@{-}} *$)/%/sm;y/ EM/0x2/' | dynamite.pl

dynamite.pl:

#!/usr/bin/perl -0p
sub f{@a{@_}||=push@{$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)},@_}f$_;for(@{$%}){f y/xr|/ytx/r;{f s/\pL\d/$&^(E&$&)x2/er}{f s/(q|s|y)#/$&^"\x01\x13"/er}my$o;{$\|=/x/>/2/;$o.="
"while s/.$/$o.=$&,""/meg}f$o}$%++>999|$\||redo}{

Substitua as \xhhfugas pela pontuação reivindicada.

O programa não pode lidar realisticamente com casos complexos. Em particular, ele não pode lidar com nenhum dos casos de falha. Isso ocorre porque existem muitas maneiras diferentes de explodir as paredes internas ou pegar ratos, de modo que a pesquisa se torna muito ampla e usa muita memória, embora seja pelo menos inteligente o suficiente para nunca processar o mesmo estado várias vezes. O limite de pressão deve ser reduzido para mais 100ou menos para tempos de execução suportáveis ​​e uso de memória.

Explicação

Eu uso o padrão de bits de um caractere para representar o estado de um campo:

contains victim: 0000 0010
has hero:        0100 0000
carry dynamite   0000 0001
carry mouse      0000 0100
home             0000 1000
walkable         0001 0000 (not really needed but results in shorter regexes)
make printable   0010 0000
wall             0010 xxxx (bit patterns not very important,
permawall        0010 xxxx  just avoid letters and digits)

Por exemplo, o herói ( 01000000) carregando dinamite ( 00000001) deve estar em um lugar em que possa andar ( 00010000) e queremos que todos os valores sejam ASCII ( 00100000) imprimíveis . Tomar o bit a bit orde todas essas máscaras de bits fornece 01110001qual é o código ASCII q. No total, isso se torna:

p: hero                     r hero on victim
q: hero carrying dynamite   s hero carrying dynamite on victim
t: hero carrying mouse      v hero carrying mouse on victim

x : hero at home
y : hero at home carrying dynamite
| : hero at home carrying mouse

0: empty  without hero
8: home   without hero
2: victim without hero

%: permanent wall
#: normal wall

O programa considerará apenas o herói se movendo para a direita (a rotação explicada mais adiante cuidará das outras direções). As máscaras de bits foram escolhidas com cuidado, de modo que o herói sempre seja representado por uma letra e um local para onde ele possa se mover por um dígito (exceto o herói em casa carregando uma vítima, mas novamente isso é intencional, de modo que o único movimento do herói seja soltar). a vítima). Assim, um herói que pode avançar é correspondido por /\pL\d/. A substring correspondente deve ser modificada para que o herói e o que ele está carregando sejam removidos do primeiro caractere e adicionados ao segundo, o que pode ser feito com um bit a bit xorcom o mesmo valor para os dois caracteres. O valor xor consiste no bit de herói ( 01000000), no bit de dinamite ( 00000001) e no bit de mouse de transporte ( 00000100). Juntos, eles ora01000101que é ASCII E. Então, movendo o herói se torna:

s/\pL\d/$&^(E&$&)x2/e

O herói pode explodir um muro se ele estiver bem na frente dele e estiver carregando dinamite ( q, sou y). O herói perderá sua dinamite ( xorcom 00000001) e a parede #mudará para uma passagem 0(xor com 00010011), então

s/(q|s|y)#/$&^"\x01\x13"/e

Para lidar com as outras direções, a placa inteira é girada (a placa girada termina em $o):

my$o;$o.="\n"while s/.$/$o.=$&,""/meg

Além de se mover, o herói também tem várias outras opções que ele pode fazer:

When at home, pick up dynamite:                   x -> y
When on victim not carrying anything pick him up: r -> t
When at home carrying a victim, drop him off:     | -> x

Isso é feito por

y/xr|/ytx/

O tabuleiro termina se o herói estiver em casa carregando nada ( x) e não houver mais vítimas para resgatar (não 2). Isso pode ser convenientemente testado usando

/x/>/2/

Uma vez resolvido o quadro, quero lembrar desse estado e, no final, imprimi-lo. Para isso, carrego a bandeira "está resolvido" $\e a imprimo no final do programa sem imprimir $_, portanto

$\|=/x/>/2/  ...   }{

Os estados a serem processados ​​na pressão 0 são mantidos @0, na pressão 1 ligada @1etc. A pressão atual é mantida $%. Usando $nou algo assim seria mais curto, mas o código não funciona se a variável não é inicializado para alguma coisa, porque autovivification, caso contrário, alterar $na um reference.Looping ARRAY sobre os estados em um determinado pressão é feito através de um fore não uma mapcausa com a, forvocê pode estender a matriz enquanto ela ainda estiver sendo repetida e capturar os novos elementos. Isso é necessário porque as rotações e as opções de campo único do herói acontecem no tempo 0 e acabam na mesma matriz de pressão. Portanto, o loop para uma dada pressão é feito por

for(@{$%}){...}

Isso é repetido até que a pressão atinja 1000 ou seja encontrada uma solução:

$%++>999|$\||redo

Tudo o que resta é adicionar estados recém-descobertos às suas respectivas matrizes de pressão. Isso será feito por sub-rotina f. Queremos adicionar um estado apenas se ele ainda não foi visto. Os estados que foram vistos anteriormente são mantidos em %a:

sub f{@a{@_}||=push@$n, @_}

$nrepresenta a nova pressão para um estado. Deduzirei isso do estado que as variáveis ​​regex ainda têm como resultado da ação do herói que levou a essa chamada:

if $1 is set it was from s/(q|s|y)#/$&^"\x01\x13"/e which blows a wall -> 50
else if $& is set it was from s/\pL\d/$&^(E&$&)x2/e, so the hero moves.
    if $& contains 8 the hero went home -> 0
    else if the hero has carry bits (5) -> 2
    else                                   1
else ($& was not set) it was from y/xr|/ytx/r -> 0

Isso leva à seguinte fórmula para $n:

$%+($&?$1?50:$&=~8?0:$&&"5"?2:1:0)

Todas as substituições obtêm um rmodificador para retornar o estado alterado e deixar o estado atual $_sozinho. fé chamado nesse estado alterado, para que você obtenha código como

f y/xr|/ytx/r;

Como o cálculo de $nprecisa das variáveis ​​regex, elas devem ser desabilitadas como padrão, caso as substituições não alterem nada (porque a condição para acioná-las não é cumprida). Também não devo pegar nenhuma variável regex de um loop anterior. Portanto, as substituições são agrupadas em {}blocos para salvar e restaurar o estado regex. É assim que você obtém declarações como

{f s/\pL\d/$&^(E&$&)x2/er}

Em particular, a rotação é tão empacotada que chama fsem variáveis ​​regex e obtém uma contribuição de pressão de 0.

A única coisa a fazer é @0começar com o estado inicial no início

f$_

Isso está no loop principal e, portanto, também tenta aumentar os $_arrays de pressão posteriores, mas como o estado inicial já estará, %anada acontecerá.

Juntos, tudo isso basicamente encontra a solução mais curta usando o algoritmo de Dijkstra . Existe um problema em potencial. O código atual não adicionará um estado se for redescoberto com uma pressão menor que a primeira descoberta. Não pude construir um quadro que desencadeasse isso, mas também não consegui provar que é impossível.

JavaScript, 863 834 785 781 bytes

Economizou 29 bytes graças à ETHproductions
Economizou 53 bytes graças à Jordan

L=[]
f=(S,r="",R="",p=0,s=S.replace(RegExp(r),R),l=`((.|\n){${s.split`
`[0].length}})`,q=p+1,o=p+2,n=p+50)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...[[/ E/,"me",q],[/ E/,"de",o],[/ME/,"ce",q],[/E /,"em",q],[/E /,"ed",o],[/EM/,"ec",q],[`E${l} `,"e$1m",q],[`E${l} `,"e$1d",o],[`E${l}M`,"e$1c",q],[` ${l}E`,"m$1e",q],[` ${l}E`,"d$1e",o],[`M${l}E`,"c$1e",q],[/ m/,"m ",q],[/m /," m",q],[`m${l} `," $1m",q],[` ${l}m`,"m$1 ",q],[/ (d|c)/,"$1 ",o],[/(d|c) /," $1",o],[`(d|c)${l} `," $2$1",o],[` ${l}(d|c)`,"$3$1 ",o],[/d#/,"m ",n],[/#d/," m",n],[`#${l}d`," $1m",n],[`d${l}#`,"m$1 ",n],[/mM/," c",q],[/Mm/,"c ",q],[`M${l}m`,"c$1 ",q],[`m${l}M`," $1c",q],[/[mc]e/," E",p],[/e[mc]/,"E ",p],[`e${l}[mc]`,"E$1 ",p],[`[mc]${l}e`," $1E",p]].map(a=>f(s,...a)))
F=s=>f(s)<1e3

Recebe a entrada como uma sequência multilinha.

Isso define uma função anônima que usa uma função recursiva fpara determinar se você dispara o alarme antes de recuperar todos os ratos.fretorna 1000se a pressão estiver acima de 1000 (para evitar recursão sem fim), retorna a pressão se não houver mais mouses para resgatar e o mouse na saída e retorna a pressão mínima de todos os movimentos possíveis do estado atual. Ele usa uma matriz Lpara acompanhar as posições já visitadas, onde L[pos]==0se é visitada e indefinida, se não for. Isso pode não ser necessário, mas impede que o mouse faça movimentos inúteis e gere erros de recursão, no mínimo. (Isso significa que você deve redefinir Lse estiver testando isso várias vezes)

Isso usa o formato da pergunta que não seja o que exige que você use um caractere diferente para as paredes externas. (Qualquer coisa que não seja # MEmecd)

Versão mais legível:

stateList = []
f=(s,regex="",replacement="",pressure=0,state=s.replace(regexp(regex),replacement),line=`((.|\n){${state.split("\n")[0].length}})`)=>{
    if (state in stateList || pressure > 999) return 1e3
    if (!/M/.test(state) && /E/.test(state)) return pressure

    stateList[state] = 0

    return [
        [/ E/,"me",pressure+1],
        [/ E/,"de",pressure+2],
        [/ME/,"ce",pressure+1],
        [/E /,"em",pressure+1],
        [/E /,"ed",pressure+2],
        [/EM/,"ec",pressure+1],
        [`E${line} `,"e$1m",pressure+1],
        [`E${line} `,"e$1d",pressure+2],
        [`E${line}M`,"e$1c",pressure+1],
        [` ${line}E`,"m$1e",pressure+1],
        [` ${line}E`,"d$1e",pressure+2],
        [`M${line}E`,"c$1e",pressure+1],
        [/ m/,"m ",pressure+1],
        [/m /," m",pressure+1],
        [`m${line} `," $1m",pressure+1],
        [` ${line}m`,"m$1 ",pressure+1],
        [/ ([dc])/,"$1 ",pressure+2],
        [/([dc]) /," $1",pressure+2],
        [`([dc])${line} `," $2$1",pressure+2],
        [` ${line}([dc])`,"$3$1 ",pressure+2],
        [/d#/,"m ",pressure+50],
        [/#d/," m",pressure+50],
        [`#${line}d`," $1m",pressure+50],
        [`d${line}#`,"m$1 ",pressure+50],
        [/mM/," c",pressure+1],
        [/Mm/,"c ",pressure+1],
        [`M${line}m`,"c$1 ",pressure+1],
        [`m${line}M`," $1c",pressure+1],
        [/[mc]e/," E",pressure],
        [/e[mc]/,"E ",pressure],
        [`e${line}[mc]`,"E$1 ",pressure],
        [`[mc]${line}e`," $1E",pressure]
    ].map(a=>f(state,...a)).reduce((a,b)=>a-b<0?a:b) //reduce used for support in more browsers.
}
s=>f(s)>1e3