# Cutpoints in a maze

A maze is given as a matrix of 0s (walls) and 1s (walkable space) in any convenient format. Each cell is considered connected to its 4 (or fewer) orthogonal neighbours. A connected component is a set of walkable cells all transitively connected to each other. Your task is to identify the cutpoints - walkable cells which, if turned into walls, would change the number of connected components. Output a boolean matrix with 1-s only at those locations. The goal is to do it in the fewest bytes of code.

The input matrix will consist of at least 3 rows and 3 columns. At least one of its cells will be a wall and at least one will be walkable. Your function or program must be able to process any of the examples below in under a minute on TIO (or on your own computer, if the language is not supported by TIO).

in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010

• so, find all bridges in all subgraphs – HyperNeutrino Mar 7 '18 at 21:27
• I think that the challenge would benefit from a step-by-step example for a smaller matrix. – Mr. Xcoder Mar 7 '18 at 21:28
• @HyperNeutrino a bridge is something different - it's an edge (not a vertex) whose removal increases the number of connected components – ngn Mar 7 '18 at 21:38
• @HyperNeutrino also, a subgraph is not quite the same as a connected component – ngn Mar 7 '18 at 21:40
• @Notatree You're right. I made a mistake. It's too late to fix it now but I hope it won't spoil the fun. – ngn Mar 8 '18 at 17:55

# Stax, 40 bytes

Çóê↓â.Φ}╞│*w<(♦◙¼ñ£º█¢,Dì♥W4·☺╛gÇÜ♠╗4D┬


Run and debug test cases

This program takes input as a space separated string containing rows. The output is in the same format. Here's the unpacked ascii representation.

{2%{_xi48&GxG=-}_?m}{'1'2|e{"12|21".22RjMJguHgu%


The fundamental operation for counting an island works like this.

1. Replace the first '1' with a '2'.
2. Regex replace '12|21' with '22'.
3. Split on spaces.
4. Transpose matrix.
5. Repeat from 2. until a string is repeated.
6. Repeat from 1. until there is no longer a '1' in the string. The number of repetitions is the number of islands.

.

{               start map block over input string, composed of [ 01]
2%            mod by 2. space and 0 yield 0. 1 yields 1. (a)
{             start conditional block for the 1s.
_           original char from string (b)
xi48&       make copy of input with current character replaced with 0
xG          counts islands in original input (d)
=           are (c) and (d) equal? 0 or 1 (e)
-           b - e; this is 1 iff this character is a bridge
}             end conditional block
_?            execute block if (a) is 1, otherwise use original char from string
m               close block and perform map over input
}               goto target - count islands and return
{               start generator block
'1'2|e        replace the first 1 with a 2
{             start generator block
"12|21".22R replace "12" and "21" with "22"
jMJ         split into rows, transpose, and rejoin with spaces
gu            generate values until any duplicate is encountered
H             keep the last value
gu              generate values until any duplicate is encountered
%               count number of iterations it took


Bonus 44 byte program - this version inputs and outputs using the grid format.

• does it process the second example in under a minute on your computer? – ngn Mar 8 '18 at 12:34
• @ngn: It does all three examples in 41s on this mid-range laptop in Chrome. Also, I just fixed the main link. I accidentally left it set to an older non-working version. – recursive Mar 8 '18 at 14:33

# MATL, 26 bytes

n:"GG0@(,w4&1ZIuz]=~]vGZye


The input is a numerical matrix, using ; as row separator.

### Explanation

n           % Implicit input: matrix. Push number of elements, N
:           % Range: gives [1 2 ... N]
"           % For each k in [1 2 ... N]
GG        %   Push input matrix twice
0@(       %   Write 0 at position k (in column-major order: down, then across).
%   The stack now contains the original matrix and a modified matrix
%   with 0 at position k
,         %   Do twice
w       %     Swap
4       %     Push 4. This specifies 4-element neighbourhood
&1ZI    %     Label each connected component, using the specified
%     neighbourhood. This replaces each 1 in the matrix by a
%     positive integer according to the connected component it
%     belongs to
u       %     Unique: gives a vector of deduplicate elements
z       %     Number of nonzeros. This is the number of connected components
]         %   End
=~        %   Are they different? Gives true of false
]           % End
v           % Concatenate stack into a column vector
GZye        % Reshape (in column-major order) according to size of input matrix.
% Implicit display


# Perl 5, -p0105101969390 89 bytes

Uses b instead of 1 in the input.

Make sure the matrix on STDIN is terminated with a newline

#!/usr/bin/perl -p0
s%b%$_="$z$'";s:|.:/ />s#(\pL)(.{@{-}}|)(?!\1)(\pL)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg  Try it online! Uses 3 levels of substitution! This 87 byte version is both in input and output format easier to interpret, but is not competing since it uses 3 different characters in the output: #!/usr/bin/perl -0p s%b%$_="$z$'";s:|.:/
/>s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg


Try it online!

It's easy to save another byte (the regex s modifier) in both versions by using some different (non-alphanumeric) character as row terminator (instead of newline), but that makes the input quite unreadable again.

# How it works

Consider the substitution

s#(\w)(.{columns}|)(?!1)(\w)#c$2c#s  This will find two letters that are different and next to each other horizontally or vertically and replace them by c. In a maze whose paths consist of entirely the letter b nothing will happen since the letters are the same, but as soon as one of the letters is replaced by another one (e.g. z) that letter and a neighbor will be replaced by c and repeated application is a flood-fill of the connected component with c from seed z. In this case I however don't want a complete flood-fill. I want to fill only one of the arms neighboring z, so after the first step I want the z gone. That already works with the c$2c replacement, but I later want to restart a flood-fill along another arm starting from the same point and I don't know which of the cs was originally z anymore. So instead I use

s#(\w)(.{columns}|)(?!\1)(\w)#$&|a.$2.a#se


b | a is c, b | c is c and z | a is {. So in a maze with paths made up of b and a seed z in the first step b will get replaced by c and z will get replaced by { which is not a letter and does not match \w and so will not cause further fills. The c however will keep a further flood-fill going and one neighbor arm of the seed gets filled. E.g. starting from

  b                      c
b                      c
bbzbb       becomes    bb{bb
b                      b
b                      b


I can then replace all c by some non letter (e.g. -) and replace { by z again to restart the flood-fill:

  -                      -
-                      -
bbzbb       becomes    cc{bb
b                      b
b                      b


and repeat this process until all neighbors of the seed have been converted. If I then once more replace { by z and flood-fill:

  -                      -
-                      -
--z--       stays      --z--
-                      -
-                      -


The z remains behind at the end because there is no neighbor to do a transformation with. That makes clear what happens in the following code fragment:

/\n/ >


Find the first newline. The starting offset is now in @-

s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se


The regex discussed above with @{-} as number of columns (since plain @- confuses the perl parser and doesn't properly substitute)

&&


The /\n/ always succeeds and the substitution is true as long as we can still flood-fill. So the part after && is executed if the flood-fill of one arm is done. If not the left side evaluates to an empty string

y/{c/z / > 0


Restart the flood-fill and return 1 if the previous flood-fill did anything. Else return the empty string. This whole piece of code is wrapped inside

s:|.: code :seg


So if this is executed on a starting string $_ with a z at the seed position the piece of code inside will be executed many times mostly returning nothing but a 1 every time a neighbor arm gets flood-filled. Effectively $_ gets destroyed and replaced by as many 1s as there are connected components attached to z. Notice that the loop needs to be executed up to sum of component sizes + number of arms times but that is OK since it will "number of characters including newlines * 2 + 1" times.

The maze gets disconnected if there are no 1's (empty string, an isolated vertex) or if there are more than 1 arms (more than 2 1s). This can be checked using the regex /\B/ (this gives 0 instead of 1 on older perl versions. It's arguable which one is wrong). Unfortunately if it doesn't match this will give an empty string instead of 0. However the s:|.: code :seg was designed to always return an odd number so by doing an & with /\B/ this will give 0 or 1.

All that is left is walking the whole input array and at each walkable position seed with z and count connected arms. That is easily done with:

s%b%$_="$z\$'"; code %eg


The only problem is that in the non-walkable positions the old value is retained. Since we need 0s there that means the original input array must have 0 in the non walkable positions and 0 matches \w in the original substitution and would trigger flood-fills. That's why I use \pL instead (only match letters).

# Java 8, 503489459 455 bytes

int R,C,v[][];m->{int c[][]=new int[R=m.length][C=m[0].length],r[][]=new int[R][C],i=R*C,t,u;for(;i-->0;)c[t=i/C][u=i%C]=m[t][u];for(;++i<R*C;r[t][u]=i(c)!=i(m)?1:0,c[t][u]=m[t][u])c[t=i/C][u=i%C]=0;return r;}int i(int[][]m){int r=0,i=0,t,u;for(v=new int[R][C];i<R*C;)if(m[t=i/C][u=i++%C]>v[t][u]){d(m,t,u);r++;}return r;}void d(int[][]m,int r,int c){v[r][c]=1;for(int k=-3,t,u;k<4;k+=2)if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C&&m[t][u]>v[t][u])d(m,t,u);}


-18 bytes thanks to @ceilingcat.

Explanation:

Try it online.

int R,C,                    // Amount of rows/columns on class-level
v[][];                  // Visited-matrix on class-level

m->{                        // Method with int-matrix as both parameter and return-type
int c[][]=new int[R=m.length][C=m[0].length],
//  Create a copy-matrix, and set R and C
r[][]=new int[R][C],  //  Create the result-matrix
i=R*C,                //  Index-integer
t,u;                  //  Temp integers
for(;i-->0;)              //  Loop i over each cell:
c[t=i/C][u=i%C]=m[t][u];//   And copy the values of the input to the copy-matrix
for(;++i<R*C              //  Loop over the cells again:
;                     //    After every iteration:
r[t][u]=i(c)!=i(m)?  //     If the amount of islands in c and m are different
1                   //      Set the current cell in the result-matrix to 1
:                    //     Else:
0,                  //      Set it to 0
c[t][u]=m[t][u])     //     And set the copy-value back again
c[t=i/C][u=i%C]=0;      //   Change the current value in the copy-matrix to 0
return r;}                //  Return the result-matrix

// Separated method to determine the amount of islands in a matrix
int i(int[][]m){
int r=0,                  //  Result-count, starting at 0
i=0,                  //  Index integer
t,u;                  //  Temp integers
for(v=new int[R][C];      //  Reset the visited array
i<R*C;)               //  Loop over the cells
if(m[t=i/C][t=i++%C]    //   If the current cell is a 1,
>v[t][u]){           //   and we haven't visited it yet:
d(m,i,j);             //    Check every direction around this cell
r++;}                 //    And raise the result-counter by 1
return r;}               //  Return the result-counter

// Separated method to check each direction around a cell
void d(int[][]m,int r,int c){
v[r][c]=1;                //  Flag this cell as visited
for(int k=-3,u,t;k<4;k+=2)//  Loop over the four directions:
if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C
//   If the cell in the direction is within bounds,
&&m[t][u]            //   and it's a path we can walk,
>v[t][u])          //   and we haven't visited it yet:
d(m,i,j);}            //    Do a recursive call for this cell


# Python 2, 290 bytes

lambda m:[[b([[C and(I,J)!=(i,j)for J,C in e(R)]for I,R in e(m)])!=b(eval(m))for j,c in e(r)]for i,r in e(m)]
def F(m,i,j):
if len(m)>i>=0<=j<len(m[i])>0<m[i][j]:m[i][j]=0;F(m,i,j+1);F(m,i,j-1);F(m,i+1,j);F(m,i-1,j)
b=lambda m:sum(F(m,i,j)or c for i,r in e(m)for j,c in e(r))
e=enumerate


Try it online!

-11 bytes thanks to Rod
-11 bytes thanks to Lynn

• It's shorter to use F(m,i,j) for each element, saving 11 bytes – Rod Mar 7 '18 at 22:07
• for q in((i,j+1),(i,j-1),(i+1,j),(i-1,j)): -> for q in(i,j+1),(i,j-1),(i+1,j),(i-1,j): - rm outer parens – ngn Mar 7 '18 at 22:28
• Since F implicitly returns None, you can use F(m,i,j)or c instead of [F(m,i,j)]and c. – Lynn Mar 7 '18 at 22:54
• Also, and m[i][j] can be >0<m[i][j], and [q[:]for q in m] can be eval(m). – Lynn Mar 7 '18 at 22:58
• @Lynn you mean eval('m')? wouldn't that return the same list instance? – ngn Mar 7 '18 at 23:09

# Wolfram Language (Mathematica), 118 bytes

(r=ReplacePart)[0#,Cases[#~Position~1,p_/;(c=Max@MorphologicalComponents[#,CornerNeighbors->1<0]&)@r[#,p->0]>c@#]->1]&


Try it online!

# Javascript 122 bytes

Input/output as a multiline string.

m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search\n)


For each walkable cell, put a block and try to fill the 4 neighbor cells. If the current cell is not a cut point, then starting from any open neighbor will fill all of them. Else, I will need more than one fill operation to reach all neighbor cells.

Less golfed

m=>{
w = m.search('\n') + 1; // offset to the next row
result = [...m].map( // for each cell
( v, // current value
p  // current position
) => {
n = [...m]; // work on a copy of the input
// recursive fill function from position p
// returns 1 if managed to fill at least 1 cell
fill = (p) => {
if (n[p] == 1)
{
n[p] = 0;
// flag will be > 1 if the fill from the current point found disjointed areas
// flag will be 0 if no area could be filled (isolated cell)
var flag = fill(p+1) + fill(p-1) + fill(p+w) + fill(p-w);
// v is modified repeatedly, during recursion
// but I need the value at top level, when fill returns to original caller
v = flag != 1 ? 1 : 0;
return 1; // at least 1 cell filled
}
else
return 0; // no fill
}
fill(p)
return v // orginal value or modified by fill function
})
}


Test

var F=
m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search\n)

var test=in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010
.match(/\d[10\n]+\d/g);
for(i = 0; test[2*i]; ++i)
{
input = test[2*i]
check = test[2*i+1]
result = F(input)
ok = check == result
console.log('Test '+ i + ' ' + (ok?'OK':'FAIL'),
'\n'+input, '\n'+result)
}