Latar Belakang

Sebuah polyomino disebut L-cembung , apakah itu mungkin untuk wisata dari setiap tile untuk setiap genteng lain dengan jalur L-berbentuk, yaitu jalan yang masuk dalam arah mata angin dan perubahan arah paling banyak sekali. Misalnya, polyomino dari 1s pada gambar

0 0 1 1 1 0

1 1 1 1 0 0

1 1 0 0 0 0

bukan L-cembung, karena kedua jalur berbentuk L dari kiri bawah 1ke kanan atas 1mengandung 0:

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

Namun, poliomino 1s pada gambar ini adalah L-cembung:

0 1 1 1 0 0

1 1 1 1 1 1

0 1 1 0 0 0

Memasukkan

Input Anda adalah array 2D bit dalam format asli bahasa Anda, atau sebagai string yang dibatasi baris baru jika bahasa kami tidak memiliki array. Dijamin mengandung setidaknya satu 1.

Keluaran

Output Anda akan menjadi nilai kebenaran jika himpunan 1s adalah polomino L-cembung, dan nilai palsu jika tidak. Output ini harus konsisten: Anda harus menampilkan nilai kebenaran yang sama untuk semua input L-cembung, dan nilai falsy yang sama untuk yang lain. Perhatikan bahwa himpunan terputus 1s (yang bukan polyomino) menghasilkan output palsu.

Aturan dan Penilaian

Anda dapat menulis program lengkap atau fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

Kasing uji ini harus berfungsi juga jika Anda memutar atau merefleksikan array, atau menambahkan baris 0ke batas mana pun.

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

Siput , 45 24

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

Tepat setelah memposting solusi awal saya, saya menyadari ada cara yang jauh lebih baik. Program asli berjalan di sekitar alun-alun yang dibentuk oleh jalur antara dua 1s, menguji keberadaan 0 di setiap pasangan sisi. Itu juga harus memiliki kasus khusus untuk jalur garis lurus. Versi baru dimulai dengan teleportasi dari satu 1ke yang lain, dan menguji tidak adanya jalur lurus atau berbentuk L dari 1belakang ke awal.

Matlab, 182 byte

Ide: Ulangi untuk setiap 1dalam matriks polyomino:

• Buat matriks baru hanya dengan yang diberikan 1tetapi sisanya nol.
• untuk setiap 1dalam matriks baru ini (ulangi sampai tidak ada yang berubah lagi)
  • tambahkan 1sebagai tetangga di arah x jika ada 1sebagai tetangga di polinomio
• untuk setiap 1dalam matriks baru ini (ulangi sampai tidak ada yang berubah lagi)
  • tambahkan 1sebagai tetangga di arah x jika ada 1sebagai tetangga di polinomio

Sekarang 1dalam matriks baru harus mencakup semua 1dalam polynomio-matrix yang dapat dijangkau dari titik awal yang diberikan dengan terlebih dahulu pergi dalam arah x dan kemudian di arah y. Sekarang kita dapat mengulangi proses yang sama tetapi dengan terlebih dahulu masuk ke arah y dan kemudian di arah x. Sekarang setiap 1matriks polyomino harus dicapai sekaligus atau kedua kali. Jika tidak, maka kami telah menemukan posisi dalam matriks polynomio yang tidak dapat dijangkau dari setiap posisi lain dengan sebuah L-path.

Golf:

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

Dengan komentar:

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

Skrip uji kasus:

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 byte

Ok, mungkin itu tidak akan memenangkan penghargaan untuk singkatnya, tapi itu memang menggunakan pendekatan baru. Lihat versi yang tidak diklik untuk cara kerjanya.

Bukti untuk metode ini dapat ditemukan di: Seluler Automata dan Sistem Kompleks Diskrit .

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

Tidak Disatukan:

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 byte

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

Penjelasan:

Pertama, jika ada 0antara dua 1s pada baris atau kolom yang sama, arraynya bukan L-cembung, karena kita tidak dapat menghubungkan keduanya 1.

Setelah mengecualikan kasing ini, setiap dua 1s pada baris atau kolom yang sama dapat dihubungkan dengan jalur lurus. Kita dapat menghasilkan grafik, yang simpulnya adalah posisi 1s dalam array, dan ujungnya adalah pasangan 1s pada baris atau kolom yang sama. Maka array adalah L-cembung jika dan hanya jika diameter grafik kurang dari 3.

JavaScript (ES6) 174

Melihat kisi-kisi sel kosong atau terisi, untuk setiap pasangan sel terisi, saya memeriksa jalur horizontal ke kolom sel lainnya (bisa ada 1 jika sel-sel berada di baris yang sama, atau 2) dan jalur vertikal ke baris sel lain (mungkin ada 1 atau 2 juga). Jika saya menemukan sel kosong di kedua jalur vertikal atau kedua jalur horizontal, maka tidak mungkin ada jalur berbentuk L di antara sel.

(Saya mengalami kesulitan mencoba untuk memasang penjelasan ini - saya harap sudah jelas)

Tes menjalankan cuplikan di bawah ini di peramban apa pun yang mendukung 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>