Kann Labyrinth gelöst werden?

20

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

Dwana
quelle
Sollte die Eingabe eine Zeichenfolge oder ein Array sein?
Apsillers
3
Wenn es bei (n, m) eine 1 (Wand) gibt, sollte der Code 0 zurückgeben?
Trichoplax
3
(Dasselbe gilt für eine Mauer um (0,0)?)
Martin Ender
3
Sie sagen, es ist ein × m-Labyrinth, aber Ihre Indizierung impliziert, dass es ein (n + 1) × (m + 1) -Labyrinth ist.
Nick Matteo
3
Ich freue mich auf die Regex-Lösung =)
Fehler

Antworten:

7

CJam, 42 41 39 36 35 Bytes

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=

Basierend auf den Ideen in dieser Antwort .

4 Bytes dank Optimizer.

Eingabeformat:

[[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]]
jimmy23013
quelle
@Optimizer Danke dafür. Aber dann habe ich einen kürzeren Weg gefunden ...
Jimmy23013
1
q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=- 36. Obwohl davon ausgegangen wird, dass die ersten drei Zeichen der Eingabe lauten[[0
Optimizer
7

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.

(~×⍳∘⍴)Aist eine Gabel äquivalent zu (~A) × ⍳⍴A. Es muss vermieden werden, zweimal zu erwähnen oder eine Variable einzuführen.

⍴Aist die Form von A. Für eine 4-mal-7-Matrix lautet die Form 4 7.

ist der Indexgenerator. ⍳4ist 1 2 3 4. ⍳4 7sind die Vektoren, (1 1)(1 2)...(4 7)die in einer 4 × 7-Matrix angeordnet sind.

~Adreht die Bits von A.

×Durch Multiplikation ⍳⍴Amit den umgedrehten Bits behalten wir die Koordinaten aller freien Zellen bei und verwandeln alle Wände in 0 0.

,reist die Matrix der Koordinatenpaare, dh linearisiert sie in einen Vektor. In diesem Fall besteht der Vektor aus Paaren.

∘.-⍨Aoder A∘.-Asubtrahiert Elemente Apaarweise. Beachten Sie, dass die Elemente von Ahier 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) wobei neine ganze Zahl der Energieoperator ist. Es gilt fzu A nZeiten: f f ... f A.

(f⍣g)AWo gist eine Funktion, ist der Festpunktoperator, auch bekannt als "Leistungsgrenze". Es hält auf die Serie der Berechnung A, f A, f f A, ... bis ((f⍣i)A) g ((f⍣(i+1))A)kehrt gilt für einige i. In diesem Fall verwenden wir match ( ) als g.

∨.∧⍨Aoder A∨.∧Aist ein Schritt in Floyds Algorithmus. f.gist 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 ⍣≡Schritte

ngn
quelle
5

Python, 164 Bytes

def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

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.

Sp3000
quelle
4

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).

/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0

Probieren Sie es online! (und wenn Sie die 1111011Zeile durch ersetzen 1111111, ist das Labyrinth nicht mehr lösbar, und die Ausgabe erfolgt 0statt 1: 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ührt A, ist sie erreichbar und wir markieren sie mit einem Aebenfalls; 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 befindet A, während s/0(.{@{+}})?A/A$1A/süberprüft wird, ob sich ein Leerzeichen links oder oben von einem befindet A. Am Ende enthält , wenn die letzte Zelle , die einen Aes ist erreichbar, ansonsten ist es nicht (das ist , was say/A$/+0überprüft, der +0hier ist , um sicherzustellen , dass das Ergebnis wird sein , 0oder 1statt leeren String und 1).
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)

Dada
quelle
In diesem Testfall betrachtet Ihr Code das Labyrinth als lösbar, selbst wenn die endgültige Position erreicht ist 1.
Jitse
@Jitse Guter Fang. Eigentlich lag es daran, dass die TIO-Links nicht den richtigen Code verwendeten (ich denke, es war eine frühere Version und ich habe sie nicht entdeckt). Die Antwort ist immer noch gültig und ich habe die TIO-Links aktualisiert. Dein Beispiel funktioniert dann einwandfrei: Probiere es online aus!
Dada
Oh, richtig! Vielen Dank für die Klarstellung, ich mag diesen Ansatz.
Jitse
@Jitse danke, das ist einer meiner Lieblingsgolfplätze :)
Dada
3

Ruby, 133 130 129 Zeichen

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]

Eingang an STDIN, Ausgängen 1oder 0an STDOUT.

Ärgerlich lang. Es füllt einfach 1s ab (0, 0)und prüft dann, ob das "Ende" -Quadrat a ist 1.

Türknauf
quelle
Wird dies das Labyrinth als lösbar behandeln, wenn es bereits eine 1 bei (n, m) enthält?
Trichoplax
2

Java, 418 Bytes

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

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:

......#;.....#.;....#..;#......
bace1000
quelle
1
Tipp: Benennen Sie Ihre Klasse mit einem Zeichen, lassen Sie das Leerzeichen zwischen String[]und aweg und nehmen Sie die Eingabe von Befehlszeilenargumenten anstelle von StdIn, was zulässig ist.
Pavel
1

Python 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

Das 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.

FryAmTheEggman
quelle
1

J 75 Zeichen

Ansteuerung der Adjazenzmatrix (sehr zeit- und speicherineffizient). (Wird es auf Englisch Powering genannt?)

   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Einige Testfälle:

   m1=. 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
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0
randomra
quelle
0

Python 3 , 184 Bytes

f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))

Probieren Sie es online!

Matthew Jensen
quelle