Du bist eine Maus. Ihre Mausefreunde wurden alle gefangen genommen und sind bewusstlos und in einem Labyrinth gefangen, das nur einen Ein- / Ausgang hat. Sie haben zufällig eine perfekte Karte des Labyrinths, sodass Sie eine Lösung finden können, um sie alle in Sicherheit zu bringen. Das Labyrinth ist jedoch mit einem Sicherheitssystem geschützt, das einen Alarm auslöst, wenn eine Schwelle von 1000
erreicht wird, wodurch Sie gefangen genommen werden und Ihre Rettungsmission nicht bestehen.
Aus früheren Untersuchungen des Labyrinths geht hervor, dass jedes Feld, auf das Sie treten (dh jede horizontale oder vertikale Bewegung - Mäuse können sich nicht diagonal bewegen ) 1
, dem Zähler des Sicherheitssystems hinzugefügt wird. Wenn Sie jedoch ein Gewicht tragen (entweder einen Dynamitblock oder einen bewusstlosen Mäusefreund), fügt es stattdessen hinzu, 2
da es den zusätzlichen Druck erkennt. Der Eingangs- / Ausgangsplatz verfügt nicht über dieses Sicherheitssystem und wird daher nicht zur Theke hinzugefügt.
Sie haben einen unbegrenzten Vorrat an Dynamit, den Sie zum Eingang gebracht haben, sodass Sie einfach alle Wände sprengen können , um Ihre Freunde zu befreien. Aber Sie müssen vorsichtig sein, denn jede Explosion 50
erhöht den Konter durch den Druck der Erschütterung. Außerdem können Sie jeweils nur eine Maus oder einen Dynamitblock tragen. Da jeder Dynamitblock nur einen Wandbereich zur Detonation bringen kann, bedeutet dies, dass Sie bei mehreren Wänden in einer Reihe mit leeren Händen zum Eingang zurückkehren müssen, um mehr zu erhalten.
Durchgearbeitetes Beispiel
Angenommen, unser Labyrinth sieht folgendermaßen aus:
######
#M# E#
######
Ich werde c
für die Theke verwenden. Wir beginnen bei der E
Ntrance, bewegen uns ein Feld nach links, während wir Dynamit tragen c=2
. Wir zünden das Dynamit, um die Mauer zu sprengen c=52
. Wir bewegen uns mit leeren Händen zwei Quadrate nach links, um zu kommen c=54
, und stehen jetzt auf dem Quadrat der Maus. Wir E
heben unseren Freund auf und bewegen 3 Felder zurück zum Ausgang, aber das letzte Feld zählt nicht, da es keine Sensoren hat. Das sind also nur 2 Felder mit etwas auf dem Rücken. Das heißt, wenn wir den Ausgang mit der letzten Maus erreichen, c=58
ist das weniger als 1000
, und daher ist die Mission erfolgreich.
Herausforderung
Wenn Sie ein Eingabelabyrinth haben, geben Sie an, ob Sie als Mausheld alle gefangenen Mäuse innerhalb der oben genannten Einschränkungen erfolgreich retten können oder ob die Mission fehlgeschlagen ist.
Eingang
- Ein 2D-Labyrinth in einem beliebigen zulässigen Format (mehrzeilige Zeichenfolge, Zeichenfolgenarray usw.).
- Für diese Herausforderung werde ich
#
sowohl die Innen- als auch die Außenwände,M
die Mausefreunde undE
den Eingang verwenden. - Der Eingang wird niemals unmittelbar an eine Innenwand angrenzen (es wird immer mindestens einen Raum geben, in dem Sie sich frei bewegen können).
- Sie können beliebige druckbare ASCII-Zeichen ersetzen, sofern dies konsistent ist. Dies hat ermöglicht es Ihnen , gegen Außenwände zwei verschiedene Symbole für Innenwände zu verwenden, so lange , wie Sie Konsistenz zu erhalten (zB wenn Sie verwenden
@
für Innenwände statt, und lassen#
für außen, jeder muss Innenwand sein@
und jede Außenwand#
). - Das Labyrinth wird immer vollständig von Wänden begrenzt, muss aber nicht rechteckig sein. Falls gewünscht, können Sie davon ausgehen, dass das Labyrinth mit Leerzeichen aufgefüllt ist, um rechteckige Eingaben vorzunehmen (optional).
- Das Labyrinth kann Abschnitte enthalten, die ohne Dynamit nicht erreichbar sind.
- Sie können die Außenwände des Labyrinths nicht dynamisieren.
Ausgabe
Ein wahrer / falscher Wert. Wahrheit für "Ja, die Maus kann jede andere Maus retten" oder Falsey für "Nein, das Alarmsystem wird ausgelöst".
Die Regeln
- Es ist entweder ein vollständiges Programm oder eine Funktion zulässig.
- Standardlücken sind verboten.
- Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.
Beispiele
Wahrheitsbeispiele, durch Leerzeilen getrennt.
#####
#M E#
#####
######
#M# E#
######
########
#E # M#
# # #
# # #
# #
########
#############################
# ## # # #
# M ## M # # #
# ## # M # E #
#M ## # # #
#############################
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############
Falsche Beispiele, durch Leerzeilen getrennt
#############################
#M ## ## ## #
# M ## M ## ## #
# ## ## M ## E #
#M ## ## ## #
#############################
#############################
########
########
# # #
# M # M#
########
#####
# M #
#####
#####
#####
#####
###################
# # # ## ## # # #
#M#M#M## E ##M#M#M#
# # # ## ## # # #
###################
#######
######
#####
####
# M#
####
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############
quelle
Antworten:
Perl,
216215 BytesBeinhaltet +2 für
-0p
Geben Sie eine Eingabe für STDIN ein. Verwendung
%
für Außenwände,#
für Innenwände,0
für Freiflächen,8
für Mäuse undr
für die Ausgangsposition. Die gesamten Boards müssen gepolstert sein, damit sie ein Rechteck bilden. Sie können die Beispiele wie folgt transformieren und ausführen:dynamite.pl
:Ersetzen Sie die
\xhh
Escapezeichen für die beanspruchte Punktzahl.Das Programm kann komplexe Fälle nicht realistisch verarbeiten. Insbesondere kann es keinen der Fehlerfälle behandeln. Dies liegt daran, dass es einfach zu viele verschiedene Möglichkeiten gibt, die Innenwände in die Luft zu jagen oder Mäuse aufzunehmen, sodass die Suche zu umfangreich wird und zu viel Speicherplatz beansprucht, obwohl sie mindestens so intelligent ist, dass sie niemals denselben Status mehrmals verarbeitet. Das Drucklimit muss auf
100
ungefähr erträgliche Laufzeiten und Speicherauslastung gesenkt werden .Erläuterung
Ich benutze das Bitmuster eines Zeichens, um den Zustand eines Feldes darzustellen:
Zum Beispiel muss sich der Held (
01000000
), der Dynamit (00000001
) trägt, an einer Stelle befinden, die er gehen kann (00010000
), und wir möchten, dass alle Werte in ASCII (00100000
) gedruckt werden können . Das bitweise Nehmenor
aller dieser Bitmasken ergibt,01110001
wofür der ASCII-Code istq
. Insgesamt wird dies ::Das Programm berücksichtigt nur, dass sich der Held nach rechts bewegt (die später erläuterte Drehung kümmert sich um die anderen Richtungen). Die Bitmasken wurden sorgfältig ausgewählt, sodass der Held immer durch einen Buchstaben und einen Ort dargestellt wird, zu dem er sich mit einer Ziffer bewegen kann (mit Ausnahme des Helden, der zu Hause ein Opfer trägt, aber auch dies ist beabsichtigt, damit der Held nur einen Schritt fallen lässt das Opfer). Ein Held, der sich vorwärts bewegen kann, trifft also auf
/\pL\d/
. Die übereinstimmende Teilzeichenfolge muss so geändert werden, dass der Held und das, was er trägt, aus dem ersten Zeichen entfernt und zum zweiten hinzugefügt werden. Dies kann bitweisexor
mit demselben Wert für beide Zeichen erfolgen. Der xor-Wert besteht aus dem Hero-Bit (01000000
), dem Dynamit-Bit (00000001
) und dem Carry-Mouse-Bit (00000100
). Zusammen sieor
zu01000101
Das ist ASCIIE
. So wird das Bewegen des Helden:Der Held kann eine Mauer sprengen, wenn er direkt davor steht und Dynamit trägt (
q
,s
odery
). Der Held verliert sein Dynamit (xor
mit00000001
) und die Wand#
verwandelt sich in eine Passage0
(oder mit00010011
)Um die anderen Richtungen zu handhaben, wird das gesamte Board gedreht (gedrehtes Board endet in
$o
):Neben dem Bewegen hat der Held noch eine Reihe anderer Entscheidungen, die er treffen kann:
Dies geschieht durch
Das Brett ist fertig, wenn der Held zu Hause ist
x
und keine Opfer mehr zu retten sind (nein2
). Dies kann bequem mit getestet werdenSobald das Board gelöst ist, möchte ich mich an diesen Zustand erinnern und ihn am Ende ausdrucken. Dafür trage ich das "ist gelöst" -Flag ein
$\
und drucke das am Ende des Programms ohne zu drucken aus$_
, alsoDie bei Druck 0 zu bearbeitenden Zustände bleiben erhalten
@0
, bei Druck 1 an@1
usw. Der aktuelle Druck bleibt erhalten$%
. Die Verwendung von$n
oder so ähnlich wäre kürzer, aber der Code funktioniert nicht, wenn die Variable nicht mit etwas initialisiert wird, da sich die Autovivierung ansonsten$n
in eine ARRAY-Referenz ändert. Das Überblättern der Zustände bei einem bestimmten Druck erfolgt mit afor
und nicht mit amap
because Mit a könnenfor
Sie das Array erweitern, während es noch durchgeschleift ist, und die neuen Elemente aufnehmen. Dies ist erforderlich, da die Rotationen und Einzelfeldwahlen des Helden in 0-Zeit erfolgen und im selben Druckfeld enden. Die Schleife für einen gegebenen Druck erfolgt also durchDies wird wiederholt, bis der Druck 1000 erreicht oder eine Lösung gefunden wird:
Alles, was übrig bleibt, ist das Hinzufügen neu entdeckter Zustände zu ihren jeweiligen Druckarrays. Das wird per Subroutine erledigt
f
. Wir möchten nur einen Zustand hinzufügen, der noch nicht gesehen wurde. Zustände, die zuvor gesehen wurden, werden folgendermaßen beibehalten%a
:$n
repräsentiert den neuen Druck für einen Staat. Ich werde das aus dem Zustand ableiten, den die Regex-Variablen als Ergebnis der Aktion des Helden, die zu diesem Aufruf führt, noch haben:Dies führt zu folgender Formel für
$n
:Alle Ersetzungen erhalten einen
r
Modifikator, sodass sie den geänderten Zustand zurückgeben und den aktuellen Zustand in$_
Ruhe lassen.f
wird dann bei diesem geänderten Zustand aufgerufen, so dass man Code wie folgt bekommtDa bei der Berechnung der
$n
Bedürfnisse die Regex-Variablen standardmäßig deaktiviert werden müssen, falls die Substitutionen nichts ändern (da die Bedingung zum Auslösen nicht erfüllt ist). Ich darf auch keine regulären Ausdrücke aus einer vorherigen Schleife aufnehmen. Daher werden die Ersetzungen in{}
Blöcke eingeschlossen, um den regulären Ausdruckszustand zu speichern und wiederherzustellen. So bekommt man Aussagen wieInsbesondere wird die Rotation so gewickelt, dass sie
f
ohne reguläre Ausdrücke aufruft und einen Druckbeitrag von 0 erhält.Das einzige, was Sie noch tun müssen, ist,
@0
am Anfang mit dem Anfangszustand zu beginnenDies ist in der Hauptschleife, so dass auch versucht wird,
$_
zu späteren Druckanordnungen hinzuzufügen , aber da der Anfangszustand bereits in ist, wird%a
nichts passieren.Zusammen ergibt dies im Grunde die kürzeste Lösung unter Verwendung des Dijkstra-Algorithmus . Es gibt jedoch ein potenzielles Problem. Der aktuelle Code fügt keinen Status hinzu, wenn er mit einem niedrigeren Druck als bei der ersten Erkennung erneut erkannt wird. Ich war nicht in der Lage, ein Board zu konstruieren, das dies auslösen würde, aber ich konnte auch nicht beweisen, dass es unmöglich ist.
quelle
JavaScript,
863834785781 BytesDank ETHproductions 29 Bytes gespart
Dank Jordan 53 Bytes gespart
Übernimmt die Eingabe als mehrzeilige Zeichenfolge.
Dies definiert eine anonyme Funktion, die eine rekursive Funktion verwendet
f
, um zu bestimmen, ob Sie den Alarm auslösen, bevor Sie alle Mäuse abrufen.f
Gibt zurück,1000
wenn der Druck über 1000 liegt (um endlose Rekursionen zu vermeiden), gibt den Druck zurück, wenn keine Mäuse mehr zu retten sind und die Maus im Ausgang ist, und gibt den minimalen Druck aller möglichen Bewegungen aus dem aktuellen Zustand zurück. Es verwendet ein ArrayL
, um bereits besuchte Positionen zu verfolgen,L[pos]==0
wenn es besucht wird, und undefiniert, wenn es nicht besucht wird. Dies ist möglicherweise nicht erforderlich, verhindert jedoch, dass die Maus unnötige Bewegungen ausführt und zumindest Rekursionsfehler verursacht. (Dies bedeutet, dass Sie neu definieren sollten,L
wenn Sie dies mehrmals testen.)Hierbei wird das in der Frage verwendete Format verwendet. Es ist jedoch erforderlich, dass Sie für die Außenwände ein anderes Zeichen verwenden. (Alles andere als
# MEmecd
)Mehr lesbare Version:
quelle
s in L|p > 999
.eval
und das Ersetzen@
mit$1
(nicht sicher , ob dies funktionieren wird, aber Sie schreiben$1
viel)f
einenf=(...)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...
$1
18 mal und.replace("@","$1")
ist 18 Bytes. Ich sehe keine Möglichkeit, das durchzuziehen.