Is my prison secure?

Question

Your challenge is given an input of a prison layout to work out whether any of the prisoners can escape.

Input

Input may be in any reasonable format such as a string, array, array of arrays etc. The input will consist of three characters, in this case #, P and space. The input will not necessarily contain all three characters.

• #: A wall
• P: A prisoner
• space: An empty space

An example input will look like:

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

Output

A truthy/falsey value of whether or not the prison is secure. The prison is only secure if it can hold all of the prisoners. If any prisoner can escape it is not secure.

A prisoner can escape if they are not fully enclosed by a wall. A diagonal joining is fully enclosed.

Test cases

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

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

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

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

P             Falsey

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

Answer 1

Snails, 13 bytes

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

Try it online!

Prints 0 for insecure prisons and the size of the input's bounding box for secure prisons.

The idea is to ensure that we can't find a path from a P to an out of bounds cell (~) moving only orthogonally (o) through spaces. The t is a teleport so that regardless where we attempt the match it tries all possible starting positions to find a P.

Answer 2

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

The absolutely wrong tool and approach, but nonetheless...

• 7 bytes (and more) saved with the useful tips from TheLethalCoder.
• 4 bytes saved by returning an integer.
• 4 more bytes saved thanks (once again) to TheLethalCoder by replacing ' ' with 32 in the comparisons.
• LOTS of bytes saved by refactoring the code.
• 13 more bytes thanks to (guess who?) TheLethalCoder. :) I keep forgetting his tips and he keeps reminding me them.

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;}

Try it online!

Basically I expand the positions of the P's whenever a white space is around until it reaches (or not) the border of the layout.

Some licenses:

• I use a char[][] as the input for the layout.
• Returns 0 as insecure and 1 as secure.

Answer 3

Perl 5, 69 bytes

-10 bytes thanks to @Grimy.

-2 bytes thanks to @Neil.

77 byte of code + -p0 flags.

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

Try it online!

Some short explanations:
The idea is to put a P everywhere the prisoners can go. If any P is on the first/last line, or the first/last column, then the prisoners can go there and therefor escape, which means the prison isn't secure.
s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s replaces a space on the right of or bellow a P with a P, or a space on the left or on top of a P.
Finally, /\A.*P|P.*\Z|^P|P$/m checks if a line starts or ends with a P, or if there is a P on the first or the last line.

Answer 4

JavaScript (ES6), 134 133 bytes

Takes input as an array of arrays of characters. Returns 0 (insecure) or 1 (secure).

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

Test cases

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

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P    P    #'],
  [...'#   #   # P #'],
  [...'#############']
]))

console.log(f([
  [...'#############'],
  [...'# P #  P#   #'],
  [...'#   #   # P #'],
  [...'########## ##']
]))

console.log(f([
  [...'####'],
  [...'#   #'],
  [...' #   #'],
  [...'  # P ####'],
  [...'  ####']
]))

console.log(f([
  [...'P']
]))

console.log(f([
  [...'###'],
  [...'# #'],
  [...'# #'],
  [...'### P']
]))

Answer 5

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)

Takes input as a newline-delimited rectangular string. Returns 0 for insecure and 1 for secure. Based on my answer to Detect Failing Castles, although it would be more efficient to test for an escaped prisoner at each step, rather than once they'd finished exploring the prison.

Answer 6

APL (Dyalog Classic), 40 bytes

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

Try it online!

'# '⍳⍵ encode '#', ' ', 'P' as 0 1 2

(⌽1,⍉)⍣4 surround with 1s

(××{1⊃⌈/⍵,⍉⍵}⌺3 3)⍣≡ max-of-neighbours flood fill of non-zero cells

⊃2≠ do we not have a 2 at the top left?

Answer 7

Octave, 64 55 bytes

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

Try it online!

or

Verify all test cases!

Explanation:

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 

Answer 8

Stax, 35 bytes^CP437

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

Try it online!

Surely golfing language without an internal to handle path-finding can do this as well!

Explanation

Uses the unpacked format to explain.

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 

Answer 9

SmileBASIC, 154 146 bytes

I was hoping an answer using flood fill would be shorter than this.

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

Replace 31 with the corresponding ASCII character.