13
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ so, find all bridges in all subgraphs \$\endgroup\$ – HyperNeutrino Mar 7 '18 at 21:27
  • 1
    \$\begingroup\$ I think that the challenge would benefit from a step-by-step example for a smaller matrix. \$\endgroup\$ – Mr. Xcoder Mar 7 '18 at 21:28
  • 1
    \$\begingroup\$ @HyperNeutrino a bridge is something different - it's an edge (not a vertex) whose removal increases the number of connected components \$\endgroup\$ – ngn Mar 7 '18 at 21:38
  • 1
    \$\begingroup\$ @HyperNeutrino also, a subgraph is not quite the same as a connected component \$\endgroup\$ – ngn Mar 7 '18 at 21:40
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – ngn Mar 8 '18 at 17:55
3
\$\begingroup\$

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
    G           jump to unbalanced }, then return; counts islands (c)
    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.

\$\endgroup\$
  • \$\begingroup\$ does it process the second example in under a minute on your computer? \$\endgroup\$ – ngn Mar 8 '18 at 12:34
  • \$\begingroup\$ @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. \$\endgroup\$ – recursive Mar 8 '18 at 14:33
3
\$\begingroup\$

MATL, 26 bytes

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

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

Try it online! Or verify all test cases.

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

Perl 5, -p0 105 101 96 93 90 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).

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

Java 8, 503 489 459 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
\$\endgroup\$
1
\$\begingroup\$

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

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

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!

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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