57
\$\begingroup\$

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
\$\endgroup\$
  • 8
    \$\begingroup\$ I have a feeling this is a duplicate or at least a similar challenge. Good challenge anyways. \$\endgroup\$ – John Dvorak Jun 14 '17 at 12:53
  • 2
    \$\begingroup\$ @JanDvorak It might be but with my limited Google Fu I could not find a duplicate. \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 12:55
  • 2
    \$\begingroup\$ related (Flood-fill a 2D grid) \$\endgroup\$ – Esolanging Fruit Jun 14 '17 at 16:32
  • 3
    \$\begingroup\$ It would be good to have Falsey examples where both horizontal and vertical movement are required to escape. \$\endgroup\$ – xnor Jun 14 '17 at 20:38
  • 2
    \$\begingroup\$ @tfbninja Not really a duplicate. That one asks to try to have the program extrapolate from given data to determine if the word is in the box. This one is BFS floodfill to see if there are unenclosed spaces holding marked values. \$\endgroup\$ – HyperNeutrino Mar 2 '18 at 2:57
54
\$\begingroup\$

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.

\$\endgroup\$
  • 23
    \$\begingroup\$ The right tool. \$\endgroup\$ – Jonathan Allan Jun 14 '17 at 14:10
16
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ You can't take extra input to the function so you can assume the dimensions... Unless you can find a meta post to persuade me otherwise. \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 14:41
  • \$\begingroup\$ 1>0 and 1<0 are shorter than true and false. \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 14:44
  • 1
    \$\begingroup\$ Can ==0 become <1? You have at least 1 byte of irrelevant whitespace. Can you remove the new[]s? (Doesn't always work but sometimes does like in int[] n = {1,2,3};). \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 14:51
  • 1
    \$\begingroup\$ {m[x][y]= p; c.Push(new[] -> {m[x][y]=p;c.Push(new[] \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 15:13
  • 1
    \$\begingroup\$ You can compare chars to ints so I believe you can replace the ==' ' to ==32 to save bytes. You should be able to do this on similar comparisons as well. \$\endgroup\$ – TheLethalCoder Jun 15 '17 at 15:54
15
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ cool approach using regexps! (but probably VERY expensive when the space grows) \$\endgroup\$ – Olivier Dulac Jun 14 '17 at 14:30
  • \$\begingroup\$ Actually, it's not that inefficient. In particular, it doesn't require a lot of backtracking, there are not * or +, the longest match it can do is the size of a line... Now of course if you compare with an approach more manual, based on arrays for instance, then yes it's quite inefficient! \$\endgroup\$ – Dada Jun 14 '17 at 14:47
  • 1
    \$\begingroup\$ -6 bytes by merging the two substitutions: s/P(.{@{-}})? | (.{@{-}})?P/P$1$2P/s. \$\endgroup\$ – Grimy Jun 16 '17 at 11:17
  • 1
    \$\begingroup\$ -2 bytes by golfing the merged substitution: s/(P| )(.{@{-}})?(?!\1)(?1)/P$2P/s. \$\endgroup\$ – Grimy Jun 16 '17 at 11:22
  • 2
    \$\begingroup\$ @Grimy very nice golfing of the regex! Thanks :) \$\endgroup\$ – Dada Jun 17 '17 at 15:29
7
\$\begingroup\$

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']
]))

\$\endgroup\$
  • \$\begingroup\$ Can the &&s just be &? \$\endgroup\$ – TheLethalCoder Jun 14 '17 at 15:36
  • \$\begingroup\$ @TheLethalCoder Not the first one, but the second one can be replaced by |. Thanks! \$\endgroup\$ – Arnauld Jun 14 '17 at 15:40
  • \$\begingroup\$ Didn't know the spread operator worked on strings. Cool! \$\endgroup\$ – acbabis Jun 15 '17 at 22:01
6
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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 
\$\endgroup\$
2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

Stax, 35 bytesCP437

ä¬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 
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.