Punkty odcięcia w labiryncie

13

Labirynt jest podawany w postaci macierzy zer (ścian) i 1 (przestrzeni do przejścia) w dowolnym dogodnym formacie. Każda komórka jest uważana za podłączoną do 4 (lub mniej) ortogonalnych sąsiadów. Podłączone urządzenie jest zestaw komórek walkable przechodni wszystkich połączonych ze sobą. Twoim zadaniem jest zidentyfikowanie punktów odcięcia - możliwych do przejścia komórek, które po przekształceniu w ściany zmieniłyby liczbę połączonych komponentów. Wyjście macierzy boolowskiej z 1-sekundami tylko w tych lokalizacjach. Celem jest zrobienie tego w jak najmniejszej liczbie bajtów kodu.

Matryca wejściowa będzie się składać z co najmniej 3 wierszy i 3 kolumn. Co najmniej jedna z jego komórek będzie ścianą, a co najmniej jedna będzie dostępna. Twoja funkcja lub program musi być w stanie przetworzyć dowolny z poniższych przykładów w ciągu niecałej minuty na TIO (lub na twoim komputerze, jeśli język nie jest obsługiwany przez 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
źródło
więc znajdź wszystkie mosty we wszystkich
podgrafach
1
Myślę, że wyzwanie przydałoby się krok po kroku dla mniejszej matrycy.
Pan Xcoder,
1
@HyperNeutrino most jest czymś innym - to krawędź (nie wierzchołek), której usunięcie zwiększa liczbę połączonych komponentów
ngn
1
@HyperNeutrino Również subgraph nie jest zupełnie taka sama jak podłączonego urządzenia
NGN
1
@Notatree Masz rację. Popełniłem błąd. Jest już za późno, aby to naprawić, ale mam nadzieję, że nie zepsuje to zabawy.
ngn

Odpowiedzi:

3

Stax , 40 bajtów

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

Uruchom i debuguj przypadki testowe

Ten program przyjmuje dane wejściowe jako ciąg oddzielony spacjami zawierający wiersze. Dane wyjściowe są w tym samym formacie. Oto rozpakowana reprezentacja ascii. 

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

Podstawowa operacja liczenia wyspy działa w ten sposób.

  1. Zamień pierwszy '1'na '2'.
  2. Regex zastąpić '12|21'z '22'.
  3. Podziel na spacje.
  4. Transponuj macierz.
  5. Powtarzaj od 2., aż ciąg zostanie powtórzony.
  6. Powtarzaj od 1., aż '1'w łańcuchu nie będzie już znaku „a”. Liczba powtórzeń to liczba wysp.

.

{               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

Dodatkowy program 44-bajtowy - ta wersja wprowadza i wysyła dane w formacie siatki.

rekurencyjny
źródło
czy przetwarza drugi przykład w niecałą minutę na twoim komputerze?
ngn
@ngn: Robi wszystkie trzy przykłady w 41 roku na tym laptopie średniej klasy w Chrome. Poza tym właśnie naprawiłem główny link. Przypadkowo zostawiłem go w starszej niedziałającej wersji.
rekurencyjny
3

MATL , 26 bajtów

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

Dane wejściowe to macierz numeryczna, używana ;jako separator wierszy.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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
źródło
2

Perl 5 , -p0 105 101 96 93 90 89 bajtów

Używa bzamiast 1w danych wejściowych.

Upewnij się, że macierz na STDIN jest zakończona nową linią

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

Wypróbuj online!

Wykorzystuje 3 poziomy substytucji!

Ta 87-bajtowa wersja jest łatwiejsza do interpretacji zarówno w formacie wejściowym, jak i wyjściowym, ale nie konkuruje, ponieważ używa 3 różnych znaków w danych wyjściowych:

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

Wypróbuj online!

Łatwo jest zapisać kolejny bajt ( smodyfikator wyrażenia regularnego ) w obu wersjach, używając jakiegoś innego (nie alfanumerycznego) znaku jako terminatora wiersza (zamiast nowej linii), ale to sprawia, że ​​dane wejściowe są ponownie nieczytelne.

Jak to działa

Rozważ zamianę 

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

Znajdują dwie litery, które są różne i znajdują się obok siebie w poziomie lub w pionie i zastępują je c. W labiryncie, którego ścieżki składają się w całości z litery, bnic się nie wydarzy, ponieważ litery są takie same, ale gdy tylko jedna z liter zostanie zastąpiona inną (np. z) Ta litera i sąsiad zostaną zastąpione, ca wielokrotne stosowanie będzie wypełnienie zalewowe podłączonego elementu z cnasion z.

W tym przypadku nie chcę jednak pełnego wypełnienia. Chcę wypełnić tylko jedno z sąsiadujących ramion z, więc po pierwszym kroku chcę zodejść. To już działa z c$2czamiennikiem, ale później chcę ponownie uruchomić wypełnienie zalewowe wzdłuż innego ramienia, zaczynając od tego samego punktu i nie wiem, który z nich cbył zjuż pierwotnie . Zamiast tego używam

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

b | ajest c, b | cjest ci z | ajest {. Tak więc w labiryncie z utworzonymi ścieżkami bi ziarnem zw pierwszym kroku bzostanie zastąpione przez ci zzostanie zastąpione przez, że {nie jest literą i nie pasuje, \wa więc nie spowoduje dalszych wypełnień. cJednak będzie prowadzić dalsze przeciwpowodziowe syta dzieje i jedno ramię sąsiada nasion zostanie wypełnione. Np. Zaczynając od

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

Mogę następnie zastąpić wszystkie litery c niektórymi literami (np. -) I zastąpić {je zponownie, aby ponownie uruchomić wypełnianie zalania:

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

i powtarzajcie ten proces, aż wszyscy sąsiedzi nasienia zostaną nawróceni. Gdybym wtedy jeszcze raz zastąpić {przez zi powódź-fill:

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

Te zszczątki tył na końcu, ponieważ nie ma sąsiad zrobić transformacji. To wyjaśnia, co dzieje się w następującym fragmencie kodu:

/\n/ >

Znajdź pierwszą nową linię. Początkowe przesunięcie jest teraz w@-

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

Wyrażenie regularne omówione powyżej z @{-}liczbą kolumn (ponieważ zwykły @-myli parser perla i nie zastępuje go poprawnie)

&&

/\n/Zawsze udaje i podstawienie jest prawdą tak długo, jak możemy nadal przeciwpowodziowe wypełnienia. Tak więc część następna &&jest wykonywana, jeśli wypełnienie jednego ramienia zostanie wykonane. Jeśli nie, lewa strona jest pusta

y/{c/z / > 0

Uruchom ponownie wypełnienie i zwróć 1, jeśli poprzednie wypełnienie zrobiło cokolwiek. W przeciwnym razie zwróć pusty ciąg. Cały kawałek kodu jest zawinięty w środku

s:|.: code :seg

Jeśli więc zostanie to wykonane na łańcuchu początkowym $_z zpozycją początkową, fragment kodu w środku zostanie wykonany wiele razy, w większości nie zwracając niczego, ale za 1każdym razem, gdy ramię sąsiada zostanie wypełnione zalaniem. Skutecznie $_zostaje zniszczony i zastąpiony przez tyle 1s, ile jest połączonych ze sobą komponentów z. Zauważ, że pętla musi zostać wykonana do sumy rozmiarów komponentów + liczby czasów uzbrojenia, ale jest to w porządku, ponieważ będzie to „liczba znaków łącznie z znakami nowej linii * 2 + 1”.

Labirynt zostaje rozłączony, jeśli nie ma go 1(pusty ciąg, izolowany wierzchołek) lub jeśli jest więcej niż 1 ramię (więcej niż 2 1s). Można to sprawdzić za pomocą wyrażenia regularnego /\B/(daje to 0zamiast 1starszych wersji perla. Można argumentować, który z nich jest zły). Niestety, jeśli nie pasuje to da pusty ciąg zamiast 0. Jednak s:|.: code :segzostał zaprojektowany, aby zawsze powrócić nieparzystą liczbę więc wykonując &z /\B/tego da 0lub 1.

Wszystko, co pozostało, to chodzenie po całej tablicy wejściowej i w każdej pozycji do przejścia na piechotę zi zpoliczyć połączone ramiona. Można to łatwo zrobić za pomocą:

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

Jedynym problemem jest to, że w pozycjach, na których nie można chodzić, stara wartość jest zachowywana. Ponieważ potrzebujemy 0s, oznacza to, że pierwotna tablica wejściowa musi znajdować się w 0pozycjach nie 0pasujących \wdo przejścia i dopasowań w pierwotnym podstawieniu i wyzwalać przepełnienia. Dlatego używam \pLzamiast tego (pasują tylko litery).

Ton Hospel
źródło
2

Java 8, 503 489 459 455 bajtów

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 bajtów dzięki @ceilingcat .

Wyjaśnienie:

Wypróbuj 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
źródło
1

Python 2 , 290 bajtów

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

Wypróbuj online!

-11 bajtów dzięki Rod
-11 bajtów dzięki Lynn

HyperNeutrino
źródło
1
Jest krótszy w użyciu F(m,i,j)dla każdego elementu, oszczędzając 11 bajtów
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 parens zewnętrzne
ngn
Ponieważ Fniejawnie zwraca wartość None, można użyć F(m,i,j)or czamiast [F(m,i,j)]and c.
Lynn,
Ponadto, and m[i][j]może być >0<m[i][j], a [q[:]for q in m]może być eval(`m`).
Lynn,
@ Lynn masz na myśli eval ('m')? czy to nie zwróci tej samej instancji listy?
ngn
1

JavaScript 122 bajty

Wejście / wyjście jako ciąg wieloliniowy.

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

Dla każdej możliwej do przejścia komórki wstaw blok i spróbuj wypełnić 4 sąsiednie komórki. Jeśli bieżąca komórka nie jest punktem przecięcia, wówczas rozpoczęcie od dowolnego otwartego sąsiada wypełni wszystkie z nich. W przeciwnym razie będę potrzebować więcej niż jednej operacji napełniania, aby dotrzeć do wszystkich sąsiednich komórek.

Mniej golfa

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)
}
Rozwiń fragment kodu

edc65
źródło