Jesteś myszką Wszyscy twoi przyjaciele myszy zostali schwytani, są nieprzytomni i uwięzieni w labiryncie, który ma tylko jedno wejście / wyjście. Zdarza się, że masz idealną mapę labiryntu, dzięki czemu możesz opracować rozwiązanie, które pozwoli Ci wskoczyć i zabrać je wszystkie w bezpieczne miejsce. Jednak labirynt jest strzeżony przez system bezpieczeństwa, który wywoła alarm, jeśli próg 1000zostanie osiągnięty, co spowoduje, że zostaniesz schwytany i nie powiedzie się Twoja misja ratunkowa.

Na podstawie poprzednich badań labiryntu każdy kwadrat, na który wchodzisz (tj. Każdy ruch poziomy lub pionowy - myszy nie mogą się poruszać po przekątnej ) dodaje 1do licznika systemu bezpieczeństwa. Jeśli jednak nosisz ciężar (blok dynamitu lub nieprzytomny przyjaciel myszy), dodaje się, 2ponieważ wykrywa dodatkowy nacisk. Kwadrat wejścia / wyjścia nie ma tego systemu bezpieczeństwa, więc nie dodaje się do licznika.

Masz nieograniczoną podaż dynamitu, który doprowadziłeś do wejścia, więc możesz po prostu wysadzić wszystkie ściany, aby uwolnić przyjaciół. Musisz jednak zachować ostrożność, ponieważ każda eksplozja zwiększa 50kontratak wywołany wstrząsającą presją. Dodatkowo możesz nosić tylko jedną rzecz na raz, jedną mysz lub jeden blok dynamitu. Ponieważ każdy blok dynamitu może zdetonować tylko jedno miejsce na ścianie, oznacza to, że jeśli jest wiele ścian w rzędzie, musisz zrobić pustą podróż z powrotem do wejścia, aby złapać więcej.

Przepracowany przykład

Załóżmy, że nasz labirynt wygląda następująco:

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

Użyję cdo licznika. Zaczynamy na EN-Trance, przesuń jeden lewy kwadrat podczas przenoszenia dynamitu c=2. Mamy detonować dynamit eksploduje ściany, c=52. Przesuwamy się o dwa kwadraty w lewo, z pustymi rękami, aby się dostać c=54, i teraz stoimy na polu myszy. EPodnosimy naszego przyjaciela i przenosimy 3 kwadraty z powrotem do xitu, ale ostatni kwadrat się nie liczy, ponieważ nie ma żadnych czujników, więc są to tylko 2 kwadraty z czymś na plecach. Oznacza to, że kiedy dotrzemy do wyjścia ostatnią myszą c=58, czyli mniej niż 1000, i dlatego misja się powiedzie.

Wyzwanie

Biorąc pod uwagę labirynt wejściowy, wypowiedz, czy ty, mysz-bohater, możesz skutecznie uratować wszystkie uwięzione myszy w ramach ograniczeń opisanych powyżej, czy też misja kończy się niepowodzeniem.

Wkład

• Labirynt 2D w dowolnym akceptowalnym formacie (ciąg wielowierszowy, tablica ciągów itp.).
• Do tego wyzwania użyję #zarówno ścian wewnętrznych, jak i zewnętrznych, Mprzyjaciół myszy i Ewejścia.
• Wejście nigdy nie będzie bezpośrednio przylegać do ściany wewnętrznej (zawsze będzie co najmniej jedno miejsce do swobodnego poruszania się).
• Możesz zastąpić dowolne znaki ASCII do wydruku , o ile są spójne. Pozwala to na użycie dwóch różnych symboli dla ścian wewnętrznych i zewnętrznych, o ile zachowasz spójność (np. Jeśli @zamiast tego zdecydujesz się na wewnętrzne ściany i pozostawisz #na zewnątrz, każda ściana wewnętrzna musi być @i każda ściana zewnętrzna #).
• Labirynt zawsze będzie całkowicie otoczony ścianami, ale niekoniecznie będzie prostokątny. W razie potrzeby możesz założyć, że labirynt jest wypełniony spacjami, aby wprowadzić prostokątne dane (opcjonalnie).
• Labirynt może mieć sekcje, które są nieosiągalne bez dynamitu.
• Nie można dynamitować zewnętrznych ścian labiryntu.

Wydajność

Truthy / falsey wartość. Prawda dla „Tak, mysz może uratować każdą inną mysz” lub Falsey dla „Nie, system alarmowy zostanie wyzwolony”.

Zasady

• Dopuszczalny jest pełny program lub funkcja.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Przykłady

Prawdziwe przykłady oddzielone pustymi liniami.

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

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

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

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

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

Przykłady Falsey, oddzielone pustymi liniami

#############################
#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 bajtów

Obejmuje +2 za -0p

Podaj dane na STDIN. Użyj %do ścian zewnętrznych, ścian #wewnętrznych, 0pustych przestrzeni, 8myszy i rpozycji wyjściowej. Całe deski muszą być wyściełane, aby tworzyły prostokąt. Możesz przekształcić i uruchomić przykłady w następujący sposób:

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}{

Wymień \xhhucieczki dla żądanego wyniku.

Program nie może realistycznie obsługiwać skomplikowanych przypadków. W szczególności nie może obsłużyć żadnego z przypadków awarii. Wynika to z faktu, że istnieje po prostu zbyt wiele różnych sposobów wysadzenia wewnętrznych ścian lub podnoszenia myszy, więc wyszukiwanie staje się zbyt szerokie i zużywa zbyt dużo pamięci, mimo że jest przynajmniej wystarczająco inteligentne, aby nigdy nie przetwarzać tego samego stanu wiele razy. Limit ciśnienia musi zostać obniżony do 100mniej więcej w celu nieco znośnego czasu działania i zużycia pamięci.

Wyjaśnienie

Używam wzorca bitowego znaku do reprezentowania stanu pola:

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)

Na przykład bohater ( 01000000) niosący dynamit ( 00000001) musi znajdować się w miejscu, do którego może chodzić ( 00010000), a my chcemy, aby wszystkie wartości były drukowalne ASCII ( 00100000). Biorąc bitową ormaskę wszystkich tych bitmasek daje 01110001kod ASCII q. W sumie staje się to:

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

Program uwzględni tylko bohatera poruszającego się w prawo (obrót wyjaśniony później zajmie się innymi kierunkami). Maski bitowe zostały starannie wybrane, tak aby bohater zawsze był reprezentowany przez literę, a miejsce, do którego może się przenieść, za pomocą cyfry (z wyjątkiem bohatera w domu niosącego ofiarę, ale znowu jest to celowe, aby jedynym ruchem bohatera było upuszczenie ofiara). Tak więc dopasowuje się bohater, który może iść naprzód /\pL\d/. Dopasowany podciąg musi zostać zmodyfikowany, aby bohater i to, co nosi, zostało usunięte z pierwszej postaci i dodane do drugiej, co można zrobić za pomocą bitów xoro tej samej wartości dla obu postaci. Wartość xor składa się z bitu bohatera ( 01000000), bitu dynamitu ( 00000001) i bitu myszy przenoszenia ( 00000100). Razem ordo01000101który jest ASCII E. Zatem poruszenie bohatera staje się:

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

Bohater może wysadzić ścianę, jeśli jest on stał tuż przed nim i przewozi dynamit ( q, slub y). Bohater straci swój dynamit ( xorz 00000001), a ściana #zmieni się w przejście 0(xor z 00010011), więc

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

Aby obsłużyć inne kierunki, cała deska jest obracana (obracana deska kończy się w $o):

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

Oprócz poruszania się bohater ma także wiele innych możliwości do wyboru:

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

Odbywa się to przez

y/xr|/ytx/

Plansza jest zakończona, jeśli bohater jest w domu xi nie ma nic ( ) i nie ma już ofiar do uratowania (nie 2). Można to dogodnie przetestować za pomocą

/x/>/2/

Po rozwiązaniu planszy chcę zapamiętać ten stan i na końcu go wydrukować. W tym celu noszę flagę „jest rozwiązany” $\i drukuję ją na końcu programu bez drukowania $_, więc

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

Stany, które mają być przetwarzane przy ciśnieniu 0 są utrzymywane @0, przy ciśnieniu 1 @1itd. Utrzymywane jest bieżące ciśnienie $%. Korzystanie $nlub coś podobnego byłoby krócej, ale kod nie działa, jeśli zmienna nie jest zainicjowana do czegoś, bo inaczej będzie zmienić autovivification $ndo reference.Looping ARRAY nad państw pod pewnym ciśnieniem odbywa się za pomocą for, a nie mapdlatego, za pomocą formożesz rozszerzyć tablicę, gdy jest ona jeszcze zapętlona i zbierze nowe elementy. Jest to potrzebne, ponieważ obroty i wybory pojedynczego pola bohatera następują za 0 i kończą się w tym samym układzie nacisku. Więc pętla dla danego ciśnienia jest wykonywana przez

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

Jest to powtarzane, aż ciśnienie osiągnie 1000 lub zostanie znalezione rozwiązanie:

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

Pozostało tylko dodać nowo odkryte stany do odpowiednich tablic ciśnienia. Zostanie to wykonane przez podprogram f. Chcemy dodać stan tylko wtedy, gdy jeszcze go nie widzieliśmy. Stany, które widziały wcześniej, są przechowywane w następujący %asposób:

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

$nreprezentuje nową presję na państwo. Wyprowadzę to ze stanu, który zmienne wyrażenia regularne nadal mają w wyniku akcji bohatera prowadzącej do tego wezwania:

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

Prowadzi to do następującej formuły dla $n:

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

Wszystkie podstawienia otrzymują rmodyfikator, więc zwracają zmieniony stan i pozostawiają bieżący stan w $_spokoju. fjest wywoływany w tym zmienionym stanie, więc otrzymujesz kod podobny do

f y/xr|/ytx/r;

Ponieważ obliczenia $nwymagają zmiennych wyrażeń regularnych, muszą one zostać domyślnie wyłączone, w przypadku gdy podstawienia nic nie zmienią (ponieważ warunek ich uruchomienia nie jest spełniony). Nie wolno mi również odbierać żadnych zmiennych wyrażeń regularnych z poprzedniej pętli. Dlatego podstawienia są zawijane w {}bloki, aby zapisać i przywrócić stan wyrażenia regularnego. Tak otrzymujesz takie stwierdzenia

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

W szczególności obrót jest tak zawinięty, że wywołuje fbez zmiennych wyrażeń regularnych i otrzymuje wkład ciśnienia równy 0.

Jedyne, co pozostaje do zrobienia, to przygotować się do @0stanu początkowego na początku

f$_

Jest to w głównej pętli, więc próbuje również dodać $_do późniejszych tablic ciśnienia, ale ponieważ stan początkowy już %anie będzie, nic się nie stanie.

Razem wszystko to w zasadzie znajduje najkrótsze rozwiązanie przy użyciu algorytmu Dijkstry . Istnieje jednak potencjalny problem. Bieżący kod nie doda stanu, jeśli zostanie ponownie odkryty z mniejszą presją niż pierwsze odkrycie. Nie byłem w stanie zbudować planszy, która by to wywołała, ale nie byłem również w stanie udowodnić, że jest to niemożliwe.

JavaScript, 863 834 785 781 bajtów

Zaoszczędź 29 bajtów dzięki ETHproductions
Zaoszczędź 53 bajty dzięki Jordanowi

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

Pobiera dane wejściowe jako ciąg multilinii.

Definiuje to anonimową funkcję, która korzysta z funkcji rekurencyjnej w fcelu ustalenia, czy wyłączysz alarm przed pobraniem wszystkich myszy. fzwraca, 1000jeśli ciśnienie jest wyższe niż 1000 (aby uniknąć niekończącej się rekurencji), zwraca ciśnienie, jeśli nie ma już myszy do uratowania i myszy na wyjściu, i zwraca minimalne ciśnienie wszystkich możliwych ruchów z bieżącego stanu w przeciwnym razie. Używa tablicy Ldo śledzenia odwiedzonych pozycji, L[pos]==0jeśli są odwiedzane, i niezdefiniowanych, jeśli nie są. Może to nie być konieczne, ale uniemożliwia myszy wykonywanie bezużytecznych ruchów i co najmniej generowanie błędów rekurencji. (Oznacza to, że powinieneś przedefiniować, Ljeśli testujesz to wiele razy)

Używa formatu z pytania innego niż to, że wymaga użycia innego znaku dla ścian zewnętrznych. (Wszystko inne niż # MEmecd)

Bardziej czytelna wersja:

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