Titik potong dalam labirin

13

Labirin diberikan sebagai matriks 0s (dinding) dan 1s (ruang walkable) dalam format apa pun yang nyaman. Setiap sel dianggap terhubung dengan 4 (atau lebih sedikit) tetangga ortogonalnya. Sebuah komponen terhubung adalah satu set sel walkable semua transitif terhubung satu sama lain. Tugas Anda adalah mengidentifikasi cutpoint - sel walkable yang, jika diubah menjadi dinding, akan mengubah jumlah komponen yang terhubung. Keluarkan matriks boolean dengan 1-s hanya di lokasi tersebut. Tujuannya adalah melakukannya dalam byte kode paling sedikit.

Matriks input akan terdiri dari setidaknya 3 baris dan 3 kolom. Setidaknya satu dari sel-selnya akan menjadi dinding dan setidaknya satu akan berjalan. Fungsi atau program Anda harus dapat memproses salah satu contoh di bawah ini dalam waktu kurang dari satu menit di TIO (atau di komputer Anda sendiri, jika bahasa tersebut tidak didukung oleh 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
sumber
jadi, temukan semua jembatan di semua subgraph
HyperNeutrino
1
Saya pikir tantangan akan mendapat manfaat dari contoh langkah-demi-langkah untuk matriks yang lebih kecil.
Tn. Xcoder
1
@HyperNeutrino, bridge adalah sesuatu yang berbeda - itu adalah edge (bukan vertex) yang penghapusannya menambah jumlah komponen yang terhubung
ngn
1
@HyperNeutrino juga, sebuah subgraph tidak cukup sama dengan komponen yang terhubung
ngn
1
@ Notatree Anda benar. Saya membuat kesalahan. Sudah terlambat untuk memperbaikinya sekarang tapi saya harap itu tidak akan merusak kesenangan.
ngn

Jawaban:

3

Stax , 40 byte

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

Jalankan dan debug kasus uji

Program ini mengambil input sebagai string yang dipisahkan spasi yang berisi baris. Outputnya dalam format yang sama. Inilah representasi ascii yang belum dibongkar. 

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

Operasi mendasar untuk menghitung sebuah pulau bekerja seperti ini.

  1. Ganti yang pertama '1'dengan a'2' .
  2. Regex ganti '12|21'dengan'22' .
  3. Berpisah pada spasi.
  4. Matikan matriks.
  5. Ulangi dari 2. hingga string diulang.
  6. Ulangi dari 1. sampai tidak ada lagi '1'dalam string. Jumlah repetisi adalah jumlah pulau.

.

{               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

Program bonus 44 byte - versi ini input dan output menggunakan format grid.

rekursif
sumber
apakah itu memproses contoh kedua dalam waktu kurang dari satu menit di komputer Anda?
ngn
@ ngn: Ini melakukan ketiga contoh dalam 41-an pada laptop kelas menengah ini di Chrome. Juga, saya baru saja memperbaiki tautan utama. Saya tidak sengaja membiarkannya disetel ke versi tidak berfungsi yang lebih lama.
rekursif
3

MATL , 26 byte

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

Input adalah matriks numerik, menggunakan ;pemisah baris.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

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
sumber
2

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

Gunakan bbukan 1pada input.

Pastikan matriks pada STDIN diakhiri dengan baris baru

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

Cobalah online!

Gunakan 3 level subtitusi!

Versi 87 byte ini dalam format input dan output lebih mudah untuk diartikan, tetapi tidak bersaing karena menggunakan 3 karakter berbeda dalam output:

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

Cobalah online!

Sangat mudah untuk menyimpan byte lain ( spengubah regex ) di kedua versi dengan menggunakan beberapa karakter (non-alfanumerik) yang berbeda sebagai terminator baris (alih-alih baris baru), tetapi itu membuat input cukup tidak dapat dibaca lagi.

Bagaimana itu bekerja

Pertimbangkan substitusi 

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

Ini akan menemukan dua huruf yang berbeda dan bersebelahan secara horizontal atau vertikal dan menggantinya dengan c. Dalam labirin yang jalurnya terdiri dari seluruhnya huruf btidak akan terjadi karena huruf-hurufnya sama, tetapi segera setelah salah satu huruf diganti dengan yang lain (mis. z) Surat itu dan tetangga akan diganti oleh cdan aplikasi berulang adalah isi banjir komponen yang terhubung dengan cdari benihz .

Namun dalam hal ini saya tidak ingin banjir penuh. Saya hanya ingin mengisi salah satu lengan tetangga z, jadi setelah langkah pertama saya ingin yang zhilang. Itu sudah bekerja dengan c$2cpenggantian, tetapi saya kemudian ingin memulai kembali banjir-mengisi sepanjang lengan lain mulai dari titik yang sama dan saya tidak tahu yang mana dari cs awalnya z. Jadi alih-alih saya gunakan

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

b | aadalah c, b | csedang cdan z | asedang {. Jadi dalam sebuah labirin dengan jalan setapak yang terbuat dari bdan sebuah benih zpada langkah pertama bakan digantikan oleh cdan zakan digantikan oleh {yang bukan huruf dan tidak cocok \wsehingga tidak akan menyebabkan pengisian lebih lanjut. The cnamun akan tetap banjir-fill lanjut pergi dan satu tetangga lengan benih akan diisi. Misalnya mulai dari

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

Saya kemudian dapat mengganti semua c dengan beberapa huruf (misalnya -) dan mengganti {dengan zlagi untuk memulai kembali pengisian banjir:

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

dan ulangi proses ini sampai semua tetangga benih telah bertobat. Jika saya sekali lagi ganti {dengan zdan isi banjir:

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

Yang ztertinggal di akhir karena tidak ada tetangga untuk melakukan transformasi dengan. Itu memperjelas apa yang terjadi dalam fragmen kode berikut:

/\n/ >

Temukan baris baru pertama. Offset awal sekarang dalam@-

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

Regex yang dibahas di atas dengan @{-}jumlah kolom (karena plain @-membingungkan parser perl dan tidak dapat diganti dengan benar)

&&

Yang /\n/selalu berhasil dan substitusi itu benar selama kita masih bisa mengisi banjir. Jadi bagian setelah &&dieksekusi jika mengisi banjir satu lengan dilakukan. Jika tidak sisi kiri mengevaluasi ke string kosong

y/{c/z / > 0

Nyalakan kembali isian banjir dan kembalikan 1 jika isian banjir sebelumnya melakukan sesuatu. Lain kembali string kosong. Seluruh bagian kode ini terbungkus di dalamnya

s:|.: code :seg

Jadi jika ini dieksekusi pada string awal $_dengan zposisi seed, potongan kode di dalamnya akan dieksekusi berkali-kali sebagian besar tidak menghasilkan apa-apa kecuali 1setiap kali lengan tetangga dipenuhi banjir. Secara efektif $_dihancurkan dan diganti oleh sebanyak 1komponen yang terhubung z. Perhatikan bahwa perulangan perlu dieksekusi hingga jumlah ukuran komponen + jumlah lengan, tetapi itu OK karena akan "jumlah karakter termasuk baris baru * 2 + 1" kali.

Labirin akan terputus jika tidak ada 1(string kosong, titik terisolasi) atau jika ada lebih dari 1 lengan (lebih dari 2 1detik). Ini dapat diperiksa menggunakan regex /\B/(ini memberikan 0bukan 1pada versi perl yang lebih lama. Ini bisa diperdebatkan mana yang salah). Sayangnya jika tidak cocok ini akan memberikan string kosong sebagai gantinya 0. Namun s:|.: code :segitu dirancang untuk selalu mengembalikan nomor ganjil sehingga dengan melakukan &dengan /\B/ini akan memberi 0atau 1.

Yang tersisa adalah berjalan seluruh array input dan pada setiap posisi benih berjalan dengan zdan menghitung lengan yang terhubung. Itu mudah dilakukan dengan:

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

Satu-satunya masalah adalah bahwa dalam posisi non-walkable nilai lama dipertahankan. Karena kita memerlukannya 0di sana, itu berarti array input asli harus memiliki 0posisi yang tidak dapat dilalui dan 0cocok \wdengan subtitusi asli dan akan memicu banjir. Itu sebabnya saya menggunakan \pLsebagai gantinya (hanya huruf yang cocok).

Ton Hospel
sumber
2

Java 8, 503 489 459 455 byte

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 byte terima kasih kepada @ceilingcat .

Penjelasan:

Cobalah 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
Kevin Cruijssen
sumber
1

Python 2 , 290 byte

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

Cobalah online!

-11 byte berkat Rod
-11 byte terima kasih kepada Lynn

HyperNeutrino
sumber
1
Ini lebih pendek untuk digunakan F(m,i,j)untuk setiap elemen, menghemat 11 byte
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 outer parens
ngn
Sejak Fkembali secara implisit None, Anda dapat menggunakan F(m,i,j)or cbukan [F(m,i,j)]and c.
Lynn
Juga, and m[i][j]bisa >0<m[i][j], dan [q[:]for q in m]bisa eval(`m`).
Lynn
@ Lynn maksudmu eval ('m')? bukankah itu mengembalikan contoh daftar yang sama?
ngn
1

Bahasa Wolfram (Mathematica) , 118 byte

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

Cobalah online!

alephalpha
sumber
1

Javascript 122 byte

Input / output sebagai string multiline.

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

Untuk setiap sel walkable, letakkan blok dan coba isi 4 sel tetangga. Jika sel saat ini bukan titik potong, maka mulai dari tetangga terbuka akan mengisi semuanya. Selain itu, saya membutuhkan lebih dari satu operasi pengisian untuk menjangkau semua sel tetangga.

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

Uji 

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

edc65
sumber