Puntos de corte en un laberinto

13

Un laberinto se da como una matriz de 0s (paredes) y 1s (espacio transitable) en cualquier formato conveniente. Cada celda se considera conectada a sus 4 (o menos) vecinos ortogonales. Un componente conectado es un conjunto de celdas transitables todas conectadas transitivamente entre sí. Su tarea es identificar los puntos de corte : celdas transitables que, si se convierten en paredes, cambiarían la cantidad de componentes conectados. Salida de una matriz booleana con 1-s solo en esas ubicaciones. El objetivo es hacerlo en la menor cantidad de bytes de código.

La matriz de entrada constará de al menos 3 filas y 3 columnas. Al menos una de sus celdas será una pared y al menos una será transitable. Su función o programa debe poder procesar cualquiera de los ejemplos a continuación en menos de un minuto en TIO (o en su propia computadora, si el idioma no es compatible con 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
code-golf graph-theory maze binary-matrix ngn
fuente
entonces, encuentre todos los puentes en todos los subgrafos
HyperNeutrino
1
Creo que el desafío se beneficiaría de un ejemplo paso a paso para una matriz más pequeña.
Sr. Xcoder
1
@HyperNeutrino un puente es algo diferente: es un borde (no un vértice) cuya eliminación aumenta el número de componentes conectados
ngn
1
@HyperNeutrino también, un subgrafo no es lo mismo que un componente conectado
ngn
1
@Notatree Tienes razón. Cometí un error. Es demasiado tarde para arreglarlo ahora, pero espero que no estropee la diversión.
ngn

Respuestas:

3

Stax , 40 bytes

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

Ejecutar y depurar casos de prueba

Este programa toma la entrada como una cadena separada por espacios que contiene filas. La salida está en el mismo formato. Aquí está la representación ascii desempaquetada. 

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

La operación fundamental para contar una isla funciona así.

  1. Reemplace el primero '1'con a '2'.
  2. Regex reemplazar '12|21'con '22'.
  3. Split en espacios.
  4. Transponer matriz.
  5. Repita desde 2. hasta que se repita una cadena.
  6. Repita desde 1. hasta que ya no haya un '1'en la cadena. El número de repeticiones es el número de islas.

.

{               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

Programa adicional de 44 bytes : esta versión ingresa y emite utilizando el formato de cuadrícula.

recursivo
fuente
¿procesa el segundo ejemplo en menos de un minuto en su computadora?
ngn
@ngn: Hace los tres ejemplos en 41s en esta computadora portátil de gama media en Chrome. Además, acabo de arreglar el enlace principal. Accidentalmente lo dejé configurado en una versión anterior que no funciona.
recursivo el
3

MATL , 26 bytes

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

La entrada es una matriz numérica, que se usa ;como separador de filas.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

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

Perl 5 , -p0 105 101 96 93 90 89 bytes

Utiliza en blugar de 1en la entrada.

Asegúrese de que la matriz en STDIN termine con una nueva línea

#!/usr/bin/perl -p0
s%b%$_="$`z$'";s:|.:/
/>s#(\pL)(.{@{-}}|)(?!\1)(\pL)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg

Pruébalo en línea!

Utiliza 3 niveles de sustitución!

Esta versión de 87 bytes es más fácil de interpretar en formato de entrada y salida, pero no compite ya que utiliza 3 caracteres diferentes en la salida:

#!/usr/bin/perl -0p
s%b%$_="$`z$'";s:|.:/
/>s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg

Pruébalo en línea!

Es fácil guardar otro byte (el smodificador regex ) en ambas versiones usando algún carácter diferente (no alfanumérico) como terminador de fila (en lugar de nueva línea), pero eso hace que la entrada sea completamente ilegible nuevamente.

Cómo funciona

Considera la sustitución 

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

Esto encontrará dos letras que son diferentes y una al lado de la otra horizontal y verticalmente y las reemplazará por c. En un laberinto cuyas rutas consisten completamente en la letra, bno pasará nada, ya que las letras son las mismas, pero tan pronto como una de las letras sea reemplazada por otra (por ejemplo z), esa letra y un vecino serán reemplazados por cuna aplicación repetida. relleno de inundación del componente conectado con la csemilla z.

En este caso, sin embargo, no quiero un relleno de inundación completo. Quiero llenar solo uno de los brazos vecinos z, así que después del primer paso quiero que se zvaya. Eso ya funciona con el c$2creemplazo, pero luego quiero reiniciar un relleno de inundación a lo largo de otro brazo a partir del mismo punto y ya no sé cuál de los cs era originalmente z. Entonces en su lugar uso

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

b | aes c, b | ces cy z | aes {. Por lo tanto, en un laberinto con caminos formados by una semilla zen el primer paso bserá reemplazada por cy zserá reemplazada por una {que no es una letra y no coincide \wy, por lo tanto, no causará más rellenos. Sin cembargo, esto mantendrá un nuevo llenado de inundación y un brazo vecino de la semilla se llenará. Ej. A partir de

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

Entonces puedo reemplazar todo c por alguna letra que no sea (por ejemplo -) y reemplazar {de znuevo para reiniciar el relleno de inundación:

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

y repita este proceso hasta que todos los vecinos de la semilla se hayan convertido. Si luego, una vez más, reemplazo {por zy relleno de inundación:

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

Los zrestos quedan al final porque no hay ningún vecino con el que hacer una transformación. Eso deja en claro lo que sucede en el siguiente fragmento de código:

/\n/ >

Encuentra la primera línea nueva. El desplazamiento inicial ahora está en@-

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

La expresión regular discutida anteriormente con el @{-}número de columnas (ya que simple @-confunde el analizador perl y no sustituye adecuadamente)

&&

El /\n/siempre tiene éxito y la sustitución es verdadera siempre que podamos llenarnos de inundaciones. Por lo tanto, la parte posterior &&se ejecuta si se completa el relleno de un brazo. Si no, el lado izquierdo se evalúa como una cadena vacía

y/{c/z / > 0

Reinicie el relleno de inundación y devuelva 1 si el relleno de inundación anterior hizo algo. De lo contrario, devuelva la cadena vacía. Todo este código está envuelto dentro

s:|.: code :seg

Por lo tanto, si esto se ejecuta en una cadena de inicio $_con una zposición inicial, el código del interior se ejecutará muchas veces, en su mayoría, devolverá nada más que 1cada vez que un brazo vecino se llene de inundaciones. Efectivamente $_se destruye y se reemplaza por tantos 1s como haya componentes conectados conectados z. Tenga en cuenta que el bucle debe ejecutarse hasta la suma de los tamaños de los componentes + el número de veces de brazos, pero eso está bien ya que "número de caracteres, incluidas las nuevas líneas * 2 + 1" veces.

El laberinto se desconecta si no hay 1's (cadena vacía, un vértice aislado) o si hay más de 1 brazos (más de 2 1s). Esto se puede verificar usando la expresión regular /\B/(esto da en 0lugar de 1versiones anteriores de perl. Es discutible cuál está mal). Desafortunadamente, si no coincide, esto dará una cadena vacía en lugar de 0. Sin embargo, el s:|.: code :segfue diseñado para devolver siempre un número impar, por lo que al hacer un &con /\B/esto dará 0o 1.

Todo lo que queda es recorrer toda la matriz de entrada y en cada posición transitable se siembra zy cuenta los brazos conectados. Eso se hace fácilmente con:

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

El único problema es que en las posiciones no transitables se retiene el valor anterior. Como necesitamos 0s allí, eso significa que la matriz de entrada original debe tener 0en las posiciones y 0coincidencias no transitables \wen la sustitución original y provocaría rellenos de inundación. Es por eso que uso \pLen su lugar (solo letras coincidentes).

Ton Hospel
fuente
2

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 gracias a @ceilingcat .

Explicación:

Pruébalo en línea.

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

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

Pruébalo en línea!

-11 bytes gracias a Rod
-11 bytes gracias a Lynn

Hiperneutrino
fuente
1
Es más corto de usar F(m,i,j)para cada elemento, ahorrando 11 bytes
Rod
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 exterior parens
ngn
Como Fregresa implícitamente None, puede usar en F(m,i,j)or clugar de [F(m,i,j)]and c.
Lynn
Además, and m[i][j]puede ser >0<m[i][j]y [q[:]for q in m]puede ser eval(`m`).
Lynn
@ Lynn te refieres a eval ('m')? ¿No devolvería eso la misma instancia de lista?
ngn
1

Javascript 122 bytes

Entrada / salida como una cadena multilínea.

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

Para cada celda transitable, coloque un bloque e intente llenar las 4 celdas vecinas. Si la celda actual no es un punto de corte, a partir de cualquier vecino abierto se llenarán todos. De lo contrario, necesitaré más de una operación de llenado para llegar a todas las celdas vecinas.

Menos golf

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

Prueba 

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

edc65
fuente