¿Es segura mi prisión?

58

Su desafío recibe una entrada del diseño de la prisión para determinar si alguno de los prisioneros puede escapar.

Entrada

La entrada puede estar en cualquier formato razonable, como una cadena, matriz, matriz de matrices, etc. La entrada constará de tres caracteres, en este caso #, Py espacio. La entrada no contendrá necesariamente los tres caracteres.

  • #: Una pared
  • P: Un prisionero
  • espacio: un espacio vacío

Un ejemplo de entrada se verá así:

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

Salida

Un valor verdadero / falso de si la prisión es segura o no. La prisión solo es segura si puede contener a todos los prisioneros. Si algún prisionero puede escapar, no es seguro.

Un prisionero puede escapar si no está completamente cercado por una pared. Una unión diagonal está completamente cerrada.

Casos de prueba

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

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

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

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

P             Falsey

###           Falsey
# #
# #
### P
TheLethalCoder
fuente
8
Tengo la sensación de que este es un duplicado o al menos un desafío similar. Buen desafío de todos modos.
John Dvorak
2
@ JanDvorak Puede ser, pero con mi limitado Google Fu no pude encontrar un duplicado.
TheLethalCoder
2
relacionado (Flood-fill a 2D grid)
Esolanging Fruit
3
Sería bueno tener ejemplos de Falsey donde se requieren movimientos horizontales y verticales para escapar.
xnor
2
@tfbninja No es realmente un duplicado. Ese pide intentar que el programa extrapole a partir de los datos dados para determinar si la palabra está en el cuadro. Este es el relleno BFS para ver si hay espacios no cerrados que contienen valores marcados.
HyperNeutrino

Respuestas:

54

Caracoles , 13 bytes

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

Pruébalo en línea!

Imprime 0para prisiones inseguras y el tamaño del cuadro delimitador de la entrada para prisiones seguras.

La idea es asegurarnos de que no podamos encontrar una ruta desde una Pcelda fuera de los límites ( ~) moviéndose solo ortogonalmente ( o) a través de espacios. El tes un teletransporte para que, independientemente de dónde intentemos el partido, intente todas las posiciones iniciales posibles para encontrar a P.

Martin Ender
fuente
23
La herramienta adecuada
Jonathan Allan
16

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

La herramienta y el enfoque absolutamente incorrectos, pero no obstante ...

  • 7 bytes (y más) guardados con los consejos útiles de TheLethalCoder.
  • 4 bytes guardados al devolver un entero.
  • 4 bytes más guardados gracias (una vez más) a TheLethalCoder al reemplazar ' 'con 32en las comparaciones.
  • MUCHOS bytes guardados al refactorizar el código.
  • 13 bytes más gracias a (¿adivina quién?) TheLethalCoder. :) Sigo olvidando sus consejos y él me los sigue recordando.
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;}

Pruébalo en línea!

Básicamente amplío las posiciones de las P cada vez que hay un espacio en blanco alrededor hasta que alcanza (o no) el borde del diseño.

Algunas licencias:

  • Yo uso a char[][]como entrada para el diseño.
  • Vuelve 0como inseguro y 1tan seguro.
Charlie
fuente
No puede tomar una entrada adicional a la función, por lo que puede asumir las dimensiones ... A menos que pueda encontrar una meta publicación para persuadirme de lo contrario.
TheLethalCoder
1>0y 1<0son más cortos que truey false.
TheLethalCoder
1
Puede ==0convertirse <1? Tiene al menos 1 byte de espacio en blanco irrelevante. ¿Puedes quitar el new[]s? (No siempre funciona, pero a veces le gusta int[] n = {1,2,3};).
TheLethalCoder
1
{m[x][y]= p; c.Push(new[]->{m[x][y]=p;c.Push(new[]
TheLethalCoder
1
Puede comparar chars a ints, así que creo que puede reemplazar ==' 'a ==32para guardar bytes. También debería poder hacer esto en comparaciones similares.
TheLethalCoder
15

Perl 5 , 69 bytes

-10 bytes gracias a @Grimy .

-2 bytes gracias a @Neil .

77 bytes de código + -p0banderas.

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

Pruébalo en línea!

Algunas explicaciones breves :
la idea es poner un lugar Pdonde los prisioneros puedan ir. Si alguno Pestá en la primera / última línea, o en la primera / última columna, entonces los prisioneros pueden ir allí y escapar, lo que significa que la prisión no está segura.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/sreemplaza un espacio a la derecha o debajo de a Pcon a P, o un espacio a la izquierda o encima de a P.
Finalmente, /\A.*P|P.*\Z|^P|P$/mverifica si una línea comienza o termina con a P, o si hay una Pen la primera o la última línea.

Dada
fuente
enfoque genial con expresiones regulares! (pero probablemente MUY caro cuando crece el espacio)
Olivier Dulac
En realidad, no es que la ineficiente. En particular, no requiere una gran cantidad de retroceso, no hay *o +, la coincidencia más larga que puede hacer es el tamaño de una línea ... Ahora, por supuesto, si se compara con un enfoque más manual, basado en matrices, por ejemplo ¡Entonces sí, es bastante ineficiente!
Dada
1
-6 bytes mediante la fusión de las dos sustituciones: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s.
Grimmy
1
-2 bytes por jugar al golf la sustitución fusionada: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s.
Grimmy
2
@ Grimy muy bonito golf de la expresión regular! Gracias :)
Dada
7

JavaScript (ES6), 134 133 bytes

Toma entrada como una matriz de matrices de caracteres. Devoluciones 0(inseguras) o 1(seguras).

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

Casos de prueba

Arnauld
fuente
¿Pueden los &&s ser &?
TheLethalCoder
@TheLethalCoder No es el primero, pero el segundo puede ser reemplazado por |. ¡Gracias!
Arnauld
No sabía que el operador de propagación trabajaba en cadenas. ¡Bueno!
aebabis
6

JavaScript (ES6), 121 bytes

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)

Toma la entrada como una cadena rectangular delimitada por nueva línea. Devuelve 0 para inseguro y 1 para seguro. Según mi respuesta a Detect Failing Castles , aunque sería más eficiente evaluar a un prisionero fugitivo en cada paso, en lugar de una vez que hubieran terminado de explorar la prisión.

Neil
fuente
2

Octava, 64 55 bytes

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

Pruébalo en línea!

o

¡Verifique todos los casos de prueba!

Explicación:

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
fuente
2

APL (Dyalog Classic) , 40 bytes

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

Pruébalo en línea!

'# '⍳⍵codificar '#', ' ', 'P'como 0 1 2

(⌽1,⍉)⍣4 rodear con 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ relleno de inundación máximo de vecinos de celdas distintas de cero

⊃2≠ ¿No tenemos un 2 en la parte superior izquierda?

ngn
fuente
1

Stax , 35 bytes CP437

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

Pruébalo en línea!

¡Seguramente el lenguaje de golf sin un interno para manejar la búsqueda de caminos también puede hacer esto!

Explicación

Utiliza el formato desempaquetado para explicar.

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
fuente
1

SmileBASIC, 154 146 bytes

Esperaba que una respuesta usando el relleno de inundación fuera más corta que esto.

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

Reemplace 31con el carácter ASCII correspondiente.

12Me21
fuente