Ist mein Gefängnis sicher?

58

Ihre Herausforderung wird durch Eingabe eines Gefängnislayouts beantwortet, um herauszufinden, ob einer der Gefangenen fliehen kann.

Eingang

Eingabe kann in jedem angemessenen Format sein , wie beispielsweise eine Kette, ein Array Array von Arrays usw. Die Eingabe wird von drei Zeichen bestehen, in diesem Fall #, Pund Raum. Die Eingabe muss nicht alle drei Zeichen enthalten.

  • #: Eine Mauer
  • P: Ein Gefangener
  • Raum: Ein leerer Raum

Eine Beispieleingabe sieht folgendermaßen aus:

#####
#   #
# P #
#   #
#####

Ausgabe

Ein wahrer / falscher Wert, der angibt, ob das Gefängnis sicher ist oder nicht. Das Gefängnis ist nur dann sicher, wenn es alle Gefangenen aufnehmen kann. Wenn ein Gefangener entkommen kann, ist dies nicht sicher.

Ein Gefangener kann fliehen, wenn er nicht vollständig von einer Mauer umschlossen ist. Eine diagonale Verbindung ist vollständig gekapselt.

Testfälle

############# Truthy
# P #  P#   #
#   #   # P #
#############

############# Truthy
# P    P    #
#   #   # P #
#############

############# Falsey
# P #  P#   #
#   #   # P #
########## ##

####          Truthy
#   #
 #   #
  # P ####
  ####

P             Falsey

###           Falsey
# #
# #
### P
TheLethalCoder
quelle
8
Ich habe das Gefühl, dass dies eine doppelte oder zumindest eine ähnliche Herausforderung ist. Trotzdem eine gute Herausforderung.
John Dvorak
2
@JanDvorak Es könnte sein, aber mit meinem eingeschränkten Google Fu konnte ich kein Duplikat finden.
TheLethalCoder
2
related (2D-Raster füllen)
Esolanging Fruit
3
Es wäre gut, Beispiele von Falsey zu haben, bei denen sowohl horizontale als auch vertikale Bewegungen erforderlich sind, um zu entkommen.
14.
2
@tfbninja Nicht wirklich ein Duplikat. Dieser fragt nach dem Versuch, das Programm aus den angegebenen Daten extrapolieren zu lassen, um festzustellen, ob das Wort in der Box enthalten ist. Dies ist eine BFS-Überflutung, um festzustellen, ob nicht eingeschlossene Bereiche mit markierten Werten vorhanden sind.
HyperNeutrino

Antworten:

54

Schnecken , 13 Bytes

!(t\P(o\ ),o~

Probieren Sie es online!

Druckt 0für unsichere Gefängnisse und die Größe des Begrenzungsrahmens der Eingabe für sichere Gefängnisse.

Damit soll sichergestellt werden, dass wir keinen Pfad von einer PZelle zu einer Zelle außerhalb der Grenzen finden ( ~), der sich nur orthogonal ( o) durch Räume bewegt . Das tist ein Teleport, so dass egal wo wir das Match versuchen es versucht alle möglichen Startpositionen zu finden P.

Martin Ender
quelle
23
Das richtige Werkzeug.
Jonathan Allan
16

C # (.NET Core) , 485 480 474 470 421 408 Bytes

Das absolut falsche Werkzeug und Ansatz, aber trotzdem ...

  • Mit den nützlichen Tipps von TheLethalCoder werden 7 Bytes (und mehr) gespart.
  • 4 Bytes werden durch die Rückgabe einer Ganzzahl gespeichert.
  • 4 weiteres Bytes gespeichert Dank (wieder) zu TheLethalCoder durch den Austausch ' 'mit 32in dem Vergleichen.
  • VIELE Bytes, die durch das Refactoring des Codes eingespart wurden.
  • 13 weitere Bytes dank TheLethalCoder. :) Ich vergesse immer wieder seine Trinkgelder und er erinnert mich immer wieder daran.
m=>{var p='P';int a=m.Length,b=m[0].Length,i=0,j,x,y;var c=new System.Collections.Stack();for(;i<a;i++)for(j=0;j<b;j++)if(m[i][j]==p)c.Push(new[]{i,j});while(c.Count>0){var t=(int[])c.Pop();x=t[0];y=t[1];if(x<1|x>a-2|y<1|y>b-2)return 0;foreach(var v in new[]{-1,1}){var z=x>0&x<a-1&y>0&y<b-1;if(z&m[x+v][y]==32){m[x][y]=p;c.Push(new[]{x+v,y});}if(z&m[x][y+v]==32){m[x][y]=p;c.Push(new[]{x,y+v});}}}return 1;}

Probieren Sie es online!

Grundsätzlich erweitere ich die Positionen der Ps, wenn ein weißer Bereich vorhanden ist, bis er den Rand des Layouts erreicht (oder nicht).

Einige Lizenzen:

  • Ich benutze ein char[][]als Eingabe für das Layout.
  • Kehrt 0als unsicher und 1als sicher zurück.
Charlie
quelle
Sie können keine zusätzlichen Eingaben in die Funktion vornehmen, damit Sie die Dimensionen annehmen können ... Es sei denn, Sie finden einen Metaposten, um mich von etwas anderem zu überzeugen.
TheLethalCoder
1>0und 1<0sind kürzer als trueund false.
TheLethalCoder
1
Kann ==0werden <1? Sie haben mindestens 1 Byte irrelevantes Leerzeichen. Können Sie das new[]s entfernen ? (Funktioniert nicht immer, gefällt aber manchmal int[] n = {1,2,3};).
TheLethalCoder
1
{m[x][y]= p; c.Push(new[]->{m[x][y]=p;c.Push(new[]
TheLethalCoder
1
Sie können chars mit ints vergleichen , also glaube ich, dass Sie das ==' 'to ersetzen können ==32, um Bytes zu sparen. Dies sollte auch bei ähnlichen Vergleichen möglich sein.
TheLethalCoder
15

Perl 5 , 69 Bytes

-10 Bytes dank @Grimy .

-2 Bytes dank @Neil .

77 Byte Code + -p0Flags.

/
/;$_=s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s?redo:!/\A.*P|P.*\Z|^P|P$/m

Probieren Sie es online!

Einige kurze Erklärungen:
Die Idee ist, einen Püberall dort zu platzieren, wo die Gefangenen hinkommen können. Befindet sich einer Pin der ersten / letzten Zeile oder in der ersten / letzten Spalte, können die Gefangenen dorthin und dorthin fliehen, was bedeutet, dass das Gefängnis nicht sicher ist.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/sErsetzt ein Leerzeichen rechts von oder unter a Pdurch a Poder ein Leerzeichen links oder über a P.
Prüft /\A.*P|P.*\Z|^P|P$/mabschließend, ob eine Zeile mit einem beginnt oder endet Poder ob sich Pin der ersten oder letzten Zeile ein befindet.

Dada
quelle
cooler Ansatz mit Regexps! (aber wahrscheinlich sehr teuer, wenn der Raum wächst)
Olivier Dulac
Eigentlich ist es nicht so ineffizient. Insbesondere erfordert es nicht viel Backtracking, es gibt keine *oder +die längste Übereinstimmung, die es kann, ist die Größe einer Zeile ... Nun, natürlich, wenn Sie mit einem Ansatz vergleichen, der manueller ist, der beispielsweise auf Arrays basiert , dann ist es ja ziemlich ineffizient!
Dada
1
-6 Bytes , die durch die beiden Substitutionen verschmelzenden: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.
Grimmy
1
-2 Bytes , die durch die zusammengefügte Substitution Golf: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.
Grimmy
2
@Grimy sehr schönes Golfen des Regex! Danke :)
Dada
7

JavaScript (ES6), 134 133 Byte

Nimmt die Eingabe als Array von Arrays von Zeichen. Gibt 0(unsicher) oder 1(sicher) zurück.

f=a=>a.map((r,y)=>r.map((c,x)=>c>'O'&&[-1,1,0,0].map((X,i)=>(R=a[y+1-'1102'[i]])&&R[X+=x]?R[X]<'!'?R[o=2,X]=c:0:o=0)),o=1)|o&2?f(a):o

Testfälle

Arnauld
quelle
Kann das &&nur sein &?
TheLethalCoder
@TheLethalCoder Nicht der erste, sondern der zweite kann durch ersetzt werden |. Vielen Dank!
Arnauld
Wusste nicht, dass der Spread-Operator an Strings arbeitet. Cool!
Aebabis
6

JavaScript (ES6), 121 Byte

f=s=>s==(s=s.replace(eval('/( |P)([^]{'+s.search`
`+'})?(?!\\1)[ P]/'),'P$2P'))?!/^.*P|P.*$/.test(s)&!/^P|P$/m.test(s):f(s)

Übernimmt die Eingabe als durch Zeilenumbrüche getrennte rechteckige Zeichenfolge. Gibt 0 für unsicher und 1 für sicher zurück. Basierend auf meiner Antwort auf Detect Failing Castles , obwohl es effizienter wäre, bei jedem Schritt nach einem entkommenen Gefangenen zu suchen, als wenn sie die Erkundung des Gefängnisses beendet hätten.

Neil
quelle
2

Oktave, 64-55 Bytes

@(a,z=padarray(a,[1 1]))~nnz(bwfill(z==35,1,1,4)&z>35);

Probieren Sie es online!

oder

Überprüfen Sie alle Testfälle!

Erläuterung:

z=padarray(a,[1 1])       %add a boundary(of 0s) around the scene
F = bwfill(z==35,1,1,4)   %flood fill the prison starting from the boundary
~nnz(F&z>35);             %if position of at least a prisoner  is filled then the prison is not secure 
rahnema1
quelle
2

APL (Dyalog Classic) , 40 Byte

{⊃2≠(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡(⌽1,⍉)⍣4'# '⍳⍵}

Probieren Sie es online!

'# '⍳⍵kodieren '#', ' ', 'P'wie 0 1 2

(⌽1,⍉)⍣4 umgeben mit 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ max-of-neighbours füllen sich mit Zellen ungleich null

⊃2≠ Haben wir oben links keine 2?

ngn
quelle
1

Stax , 35 Bytes CP437

ä¬my■╡╤▲l@┤êr*⌠\¶ƒläå─▄¶√¿ [Uy⌠Só4↔

Probieren Sie es online!

Sicherlich kann dies auch eine Golfsprache sein, die nicht über eine interne Wegfindung verfügt!

Erläuterung

Verwendet das entpackte Format zur Erklärung.

zLz]Y+Mys+y+{{{" P|P ""PP"Rm}Y!My!Mgphh' =
zLz]Y+Mys+y+                                  Surround the original matrix with four borders of whitespaces
            {                      gp         Iterate until a fixed point is found, return the single fixed point
             {              }Y!               Store the block in register Y and execute it
              {" P|P ""PP"Rm                  For each row, flood every space adjacent to a P with P.
                               My!            Transpose the matrix and do the flooding again
                                     hh' =    The final matrix has a space on the upper left corner that has not been flooded by P 
Weijun Zhou
quelle
1

SmileBASIC, 154 146 Bytes

Ich hatte gehofft, eine Antwort mit Flood Fill würde kürzer sein.

DEF S P
FOR J=0TO 1X=1Y=1FOR I=0TO LEN(P)-1GPSET X,Y,-(P[I]=="#")GPAINT X,Y,-1,-J*(P[I]>@A)X=X*(P[I]>"31")+1INC Y,X<2NEXT
NEXT?!GSPOIT(0,0)GCLS
END

Ersetzen Sie 31durch das entsprechende ASCII-Zeichen.

12Me21
quelle