tło

Polyomino jest nazywany L-wypukłą , jeżeli jest to możliwe do podróży z dowolnego dachówka do jakiejkolwiek innej płytki przez ścieżką w kształcie litery L, czyli drogi, która przechodzi w kierunkach kardynalnych i zmienia kierunek co najwyżej raz. Na przykład poliomino 1s na rysunku

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

nie jest wypukły w kształcie litery L, ponieważ obie ścieżki w kształcie litery L od dolnej lewej 1do prawej górnej 1zawierają 0:

0>0>1>1>1 0
^       ^
1 1 1 1 0 0
^       ^
1>1>0>0>0 0

Jednak poliomino 1s na tej figurze jest wypukłe w kształcie litery L:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

Wejście

Twoje dane wejściowe to tablica 2D bitów w natywnym formacie Twojego języka lub ciąg znaków rozdzielany znakiem nowej linii, jeśli nasz język nie ma tablic. Gwarantuje, że zawiera co najmniej jeden 1.

Wynik

Twój wynik powinien być prawdziwą wartością, jeśli zbiór 1s jest L-wypukłym poliomino, i wartością fałszowania, jeśli nie. Te dane wyjściowe muszą być spójne: musisz wygenerować tę samą wartość prawdy dla wszystkich danych wejściowych wypukłych w kształcie litery L i tę samą wartość fałszowania dla innych. Zauważ, że rozłączony zestaw 1s (który nie jest poliomino) powoduje powstanie fałszowania.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Te przypadki testowe powinny również działać, jeśli obrócisz lub odzwierciedlisz tablice lub dodasz rzędy 0s do dowolnych granic.

False instances
01
10

111
101
111

1101
1111
1110

1100
1000
0011

01100
11110
01110
00110

011000
011110
001111

True instances
1

01
11

010
111
010

001
011
111

11100
11110
01100
01000

011000
011000
111100
111111
001000

Ślimaki , 45 24

&
!{\1t\1!{o\1,nf\1,!.!~

Zaraz po opublikowaniu mojego pierwszego rozwiązania zdałem sobie sprawę, że istnieje o wiele lepszy sposób. Pierwotny program podróżował po kwadracie utworzonym przez ścieżki między dwoma 1s, testując obecność 0 w każdej parze boków. Musiał też mieć specjalny przypadek dla ścieżek linii prostych. Nowa wersja zaczyna się od teleportacji z jednej 1do drugiej i testowania braku prostej lub w kształcie litery L ścieżki 1powrotnej do początku.

Matlab, 182 bajty

Pomysł: Powtórz dla każdego 1w macierzy poliomino:

• Utwórz nową macierz tylko z podanym, 1ale pozostałym zerem.
• dla każdego 1w tej nowej matrycy (powtarzaj, aż nic się już nie zmieni)
  • dodaj 1jako sąsiadów w kierunku x, jeśli są 1wielomian jako sąsiedzi
• dla każdego 1w tej nowej matrycy (powtarzaj, aż nic się już nie zmieni)
  • dodaj 1jako sąsiadów w kierunku x, jeśli są 1wielomian jako sąsiedzi

Teraz 1w nowej macierzy należy objąć wszystko 1w macierzy wielomianowej, które są osiągalne z danego punktu początkowego, najpierw w kierunku x, a następnie w kierunku y. Teraz możemy powtórzyć ten sam proces, ale najpierw w kierunku y, a następnie w kierunku x. Teraz do każdej 1matrycy poliomino należy dotrzeć jednocześnie lub za każdym razem. Jeśli nie, to znaleźliśmy pozycję w macierzy wielomianu, do której nie można dotrzeć z każdej innej pozycji przez L-path.

Gra w golfa:

function r=f(a);[i,j,b]=find(a);N=nnz(i);r=1;for k=1:N;K=1:3;for l=1:2;c=b;b=a*0;b(i(k),j(k))=1;for z=1:2*N; b=conv2(b+0,K,'s')&a;if z==N;K=K';end;end;end;r=r*all(b(:)|c(:)>=a(:));end

Z komentarzami:

function r=codegolf_L_convex(a);
%a=[0,1;1,1];
[i,j,b]=find(a);%b just needs to be initialized, does not really mattter
N=nnz(i);%number of ones in the matrix
r=1;%return value
for k=1:N;%go throu all '1' in the matrix
    %expand that pixel in x dir:
    K=1:3;%convolution kernel (just three positive values needed)
    for l=1:2;%first horizontal->vertical then vertical->horizontal
        c=b;%backup for considering both runs
        b=a*0;
        b(i(k),j(k))=1; %set the seed
        for z=1:2*N;     
            b=conv2(b+0,K,'s')&a; %expand the seed horizontally (or vertically for the second half) but only within the polyomino
            if z==N;
                K=K'; %change horizontal/vertical 
            end;
        end;
    end;
    r=r*all(b(:)|c(:)>=a(:));%check whether we can really reach every point
end

Skrypt przypadków testowych:

disp('all false -------------');
a=[0,1;1,0];
f(a)
a=[1,1,1;1,0,1;1,1,1];
f(a)
a=[1,1,0,1;1,1,1,1;1,1,1,0];
f(a)
a=[1,1,0,0;1,0,0,0;0,0,1,1];
f(a)
a=[0,1,1,0,0;1,1,1,1,0;0,1,1,1,0;0,0,1,1,0];
f(a)
a=[0,1,1,0,0,0;0,1,1,1,1,0;0,0,1,1,1,1];
f(a)
 disp('all true +++++++++++++');
a=[1];
f(a)
a=[0,1;1,1];
f(a)
a=[0,1,0;1,1,1;0,1,0];
f(a)
a=[0,0,1;0,1,1;1,1,1];
f(a)
a=[1,1,1,0,0;1,1,1,1,0;0,1,1,0,0;0,1,0,0,0];
f(a)
a=[0,1,1,0,0,0;0,1,1,0,0,0;1,1,1,1,0,0;1,1,1,1,1,1;0,0,1,0,0,0];
f(a)

JavaScript ES6, 290 bajtów

Ok, może nie zdobędzie żadnych nagród za zwięzłość, ale stosuje nowatorskie podejście. Zobacz wersję bez golfa, jak to działa.

Dowód tej metody można znaleźć w: Automaty komórkowe i dyskretne złożone systemy .

L=a=>[1,0,1].every($=>(a=a[0].map((_,col)=>a.map(row=>row[col]))).map(r=>($?r.reverse():r).join``).every((r,i,b)=>r.replace(/^(0*)(1*)(0*)$|(.+)/,(_,s,m,o,e)=>(c=e)?'':!m||b[i-1]&&+b[i-1][s.length]?1:b.every((r,j)=>j<i||(c=c||!+r[l=s.length])?r.search(`0{${l}}.*0{${o.length}}`)+1:1)||'')))

Nie golfowany:

function L(a) {
  /* Runs three times and ensure all pass validation
   * 1: horizontally reversed
   * 2: 90 degrees rotated
   * 3: original
   *
   *     | 1:  | 2:  | 3:
   * =====================
   * 001 | 100 | 111 | 001
   * 011 | 110 | 011 | 011
   * 111 | 111 | 001 | 111
   *
   * By finding maximal rectangles with corners on all NW and NE corners
   * (separately) of a HV-convex polyomino and ensuring it doesn't enter the
   * boundaries labelled ABCD for the rectangle X below:
   *
   *   A  |         |  B
   * -----===========-----
   *      |    X    |
   * -----===========-----
   *   C  |         |  D
   *
   * The first iteration tests the NE corners and horizontal convexity.
   * The second iteration test vertical convexity.
   * The third iteration tests the NW corners.
   *
   * If all pass then the polyomino is L-convex.
   */
  return [1,0,1].every(function($){
    return (a=a[0].map((_,col)=>{
      // Transpose rows with columns
      return a.map(row=>row[col])
    })).map(row=>{
      // Join rows as strings and on odd iterations reverse them
      return ($ ? row.reverse() : row).join``
    }).every(function(row, i, b) {
      if (i == 0) console.log(b.join('\n'));
      return row.replace(/^(0*)(1*)(0*)$|(.+)/, function(_, start, middle, end, invalid) {
        // Non H-convex polyomino (0 between 1s)
        if (invalid) return '';
        // Is not a NW corner (character above is 1)
        if (!middle || b[i-1] && +b[i-1][start.length]) return 1;
        c=1;
        return b.every(function(row, j) {
          // Above or below maximal rectangle from corner
          if (j < i || !(c=c&&+row[l=start.length])) {
            // Area before and after maximal rectangle doesn't contain 1
            return row.search(`0{${l}}.*0{${end.length}}`)+1
          }
          return 1;
        }) || '';
      });
    });
  });
}

Mathematica, 129 127 bajtów

3>GraphDiameter@Graph[#,#<->#2&@@@Select[#~Tuples~2,!FreeQ[#-#2&@@#,0]&]]&@Position[#,1]&&{#,Thread@#}~FreeQ~{___,1,0..,1,___}&

Wyjaśnienie:

Po pierwsze, jeśli w tym samym rzędzie lub kolumnie znajdują się 0między dwoma 1sami, tablica nie jest wypukła w kształcie litery L, ponieważ nie możemy połączyć dwóch 1s.

Po wykluczeniu tego przypadku co dwa 1s w tym samym rzędzie lub kolumnie mogą być połączone prostą ścieżką. Możemy wygenerować wykres, którego wierzchołki są pozycjami 1s w tablicy, a krawędzie są parami 1s w tym samym rzędzie lub kolumnie. Następnie tablica jest wypukła w kształcie litery L, jeśli tylko wtedy, gdy średnica wykresu jest mniejsza niż 3.

JavaScript (ES6) 174

Patrząc na siatkę pustych lub wypełnionych komórek, dla każdej pary wypełnionych komórek sprawdzam poziome ścieżki do drugiej kolumny komórek (może być 1, jeśli komórki znajdują się w tym samym rzędzie, w przeciwnym razie lub 2) i pionowe ścieżki do inny wiersz komórki (może być też 1 lub 2). Jeśli znajdę pustą komórkę w obu ścieżkach pionowych lub obu ścieżkach poziomych, wówczas między komórkami nie będzie ścieżki w kształcie litery L.

(Trudno mi było wytłumaczyć to wyjaśnienie - mam nadzieję, że było jasne)

Przetestuj poniższy fragment kodu w dowolnej przeglądarce zgodnej z EcmaScript 6

F=p=>!p.some((n,y)=>n.some((q,x)=>q&&p.some((o,u)=>o.some((q,t)=>{for(f=0,i=y;q&i<=u;i++)f|=!p[i][x]|2*!p[i][t];if(f<3)for(f=0,j=x;q&j<=t;j++)f|=!n[j]|2*!o[j];return f>2}))))

// TEST
console.log=(...x)=>O.innerHTML+=x+'\n'

tko = [
 [[0,1],[1,0]]
,[[1,1,1],[1,0,1],[1,1,1]]
,[[1,1,0,1],[1,1,1,1],[1,1,1,0]]
,[[1,1,0,0],[1,0,0,0],[0,0,1,1]]
,[[0,1,1,0,0],[1,1,1,1,0],[0,1,1,1,0],[0,0,1,1,0]]
,[[0,1,1,0,0,0],[0,1,1,1,1,0],[0,0,1,1,1,1]]
]
tko.forEach(t=>(console.log(t.join`\n`+`\nFalse? ${F(t)}\n`)));
tok = [
 [[1]]
,[[0,1],[1,1]]
,[[0,1,0],[1,1,1],[0,1,0]]
,[[0,0,1],[0,1,1],[1,1,1]]
,[[1,1,1,0,0],[1,1,1,1,0],[0,1,1,0,0],[0,1,0,0,0]]
,[[0,1,1,0,0,0],[0,1,1,0,0,0],[1,1,1,1,0,0],[1,1,1,1,1,1],[0,0,1,0,0,0]]
]  
tok.forEach(t=>(console.log(t.join`\n`+`\nTrue? ${F(t)}\n`)));

// LESS GOLFED

U=p=>
  !p.some((n,y)=>  
    n.some((q,x)=> 
      q && p.some((o,u)=>  
        o.some((q,t)=>{
          for(f=0,i=y; q&i<=u; i++)f|=!p[i][x]|2*!p[i][t]
          if (f<3)
            for(f=0,j=x; q&j<=t; j++)f|=!n[j]|2*!o[j]
          return f>2
        })
      )
    )
  )

<pre id=O></pre>