Das Puzzle
- Gib 0 aus, wenn ein Labyrinth n * m nicht gelöst werden kann
- Gib 1 aus, wenn ein Labyrinth n * m gelöst werden kann (auf eine oder mehrere Arten)
(also frage ich nicht nach Wegen aber ob es möglich ist zu lösen !!!)
Eingangsarray (2d):
[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]
XXXXXXXXX
XS XX
X X X
X X X
XX FX
XXXXXXXXX
0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line
Regel Die Startposition ist 0,0 und die Endposition ist n, m. Sie können sich nur horizontal und vertikal bewegen. Kürzester Code gewinnt
Antworten:
CJam,
4241393635 BytesBasierend auf den Ideen in dieser Antwort .
4 Bytes dank Optimizer.
Eingabeformat:
quelle
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=
- 36. Obwohl davon ausgegangen wird, dass die ersten drei Zeichen der Eingabe lauten[[0
Dyalog APL, 27 Zeichen
⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕
⎕
ausgewertete Eingabe. APL unterscheidet zwischen einer Matrix und einem Vektor von Vektoren. Dieses Programm geht davon aus, dass die Eingabe eine Matrix ist.(~×⍳∘⍴)A
ist eine Gabel äquivalent zu(~A) × ⍳⍴A
. Es muss vermieden werden,⎕
zweimal zu erwähnen oder eine Variable einzuführen.⍴A
ist die Form vonA
. Für eine 4-mal-7-Matrix lautet die Form4 7
.⍳
ist der Indexgenerator.⍳4
ist1 2 3 4
.⍳4 7
sind die Vektoren,(1 1)(1 2)...(4 7)
die in einer 4 × 7-Matrix angeordnet sind.~A
dreht die Bits vonA
.×
Durch Multiplikation⍳⍴A
mit den umgedrehten Bits behalten wir die Koordinaten aller freien Zellen bei und verwandeln alle Wände in0 0
.,
reist die Matrix der Koordinatenpaare, dh linearisiert sie in einen Vektor. In diesem Fall besteht der Vektor aus Paaren.∘.-⍨A
oderA∘.-A
subtrahiert ElementeA
paarweise. Beachten Sie, dass die Elemente vonA
hier selbst Paare sind.|
Absolutwert+/¨
Summiere jedes Paar absoluter Werte. Dies gibt uns die Gitterabstände zwischen jedem Zellenpaar im Labyrinth, abgesehen von Wänden.1≥
Wir sind nur an Nachbarn interessiert, die nicht weiter als 1 entfernt sind. Dies schließt auch Mauern aus. Jetzt haben wir die Adjazenzmatrix eines Graphen.∨.∧⍨⍣≡
Floyd - Warshalls Transitiver Schließungsalgorithmus(f⍣n)A
(hier nicht verwendet) wobein
eine ganze Zahl der Energieoperator ist. Es giltf
zuA
n
Zeiten:f f ... f A
.(f⍣g)A
Wog
ist eine Funktion, ist der Festpunktoperator, auch bekannt als "Leistungsgrenze". Es hält auf die Serie der BerechnungA
,f A
,f f A
, ... bis((f⍣i)A) g ((f⍣(i+1))A)
kehrt gilt für einigei
. In diesem Fall verwenden wir match (≡
) alsg
.∨.∧⍨A
oderA∨.∧A
ist ein Schritt in Floyds Algorithmus.f.g
ist eine Verallgemeinerung der Matrixmultiplikation (+.×
), hier verwenden wir Konjunktion (∧
) und Disjunktion (∨
) anstelle von+
und×
.⊃⌽
Nachdem⍣≡
wir den Schritt genügend oft angewendet haben und einen stabilen Zustand erreicht haben, müssen wir die obere rechte Ecke der Matrix nachschlagen, um das Ergebnis zu erhalten. Wir drehen es (⌽
) und nehmen das erste Objekt oben links (⊃
).Visualisierung der
⍣≡
Schrittequelle
Python, 164 Bytes
Ich wollte das nicht posten, weil es praktisch so ist, wie ich es normalerweise mache, wenn ich nur leicht Golf spiele. Aber hier ist es trotzdem.
quelle
Perl, 73 Bytes
69 Byte Code + 4 Byte für
-n0E
(ich bin nicht sicher, wie die Tags im Jahr 2014 gezählt wurden, also habe ich sie für 4 statt für 2 gezählt, aber das spielt keine Rolle).Probieren Sie es online! (und wenn Sie die
1111011
Zeile durch ersetzen1111111
, ist das Labyrinth nicht mehr lösbar, und die Ausgabe erfolgt0
statt1
: Probieren Sie es online aus! )Erklärungen:
Dieser Code findet jede erreichbare Zelle des Labyrinths (und markiert sie mit einem
A
): Wenn eine Zelle eine mit einem markierte Zelle berührtA
, ist sie erreichbar und wir markieren sie mit einemA
ebenfalls; und das machen wir nochmal (redo
). Dies geschieht dank zweier regulärer Ausdrücke:s/(^0|A)(.{@{+}})?0/A$2A/s
Überprüft, ob sich ein Leerzeichen rechts oder unten von einem befindetA
, währends/0(.{@{+}})?A/A$1A/s
überprüft wird, ob sich ein Leerzeichen links oder oben von einem befindetA
. Am Ende enthält , wenn die letzte Zelle , die einenA
es ist erreichbar, ansonsten ist es nicht (das ist , wassay/A$/+0
überprüft, der+0
hier ist , um sicherzustellen , dass das Ergebnis wird sein ,0
oder1
statt leeren String und1
).Beachten Sie, dass dies
/.*/
mit einer gesamten Zeile übereinstimmt und somit einstellt@+
zum Index des Endes der ersten Zeile, der zufällig die Größe einer Zeile hat, mit der.{@{+}}
genau so viele Zeichen gefunden werden können, wie in einer Zeile enthalten sind. (@{+}
entspricht,@+
kann aber nur in regulären Ausdrücken verwendet werden)quelle
1
.Ruby,
133130129 ZeichenEingang an STDIN, Ausgängen
1
oder0
an STDOUT.Ärgerlich lang. Es füllt einfach
1
s ab(0, 0)
und prüft dann, ob das "Ende" -Quadrat a ist1
.quelle
Java, 418 Bytes
Mein erster Code Golf. Ich weiß nicht, warum ich mich für Java entschieden habe - es ist so schlecht für das Golfen mit xD
Ein Beispiel-Labyrinth würde wie folgt über stdin eingegeben:
quelle
String[]
unda
weg und nehmen Sie die Eingabe von Befehlszeilenargumenten anstelle von StdIn, was zulässig ist.Python 184
188Das hat viel länger gedauert, als ich gedacht hatte :( Wie auch immer, ich werde eine Erklärung hinzufügen, wenn ich nicht mehr Golf spielen kann.
quelle
J 75 Zeichen
Ansteuerung der Adjazenzmatrix (sehr zeit- und speicherineffizient). (Wird es auf Englisch Powering genannt?)
Einige Testfälle:
quelle
Python 3 , 147 Bytes
Probieren Sie es online!
Port meiner Antwort auf die Suche nach der kürzesten Route auf einer ASCII-Straße .
quelle
Python 3 , 184 Bytes
Probieren Sie es online!
quelle