Latar Belakang

Saya memiliki banyak gambar hitam-putih tua dan kasar. Beberapa dari mereka menggambarkan tanaman merambat memanjat di dinding, yang lain tidak - tugas Anda adalah mengklasifikasikannya untuk saya.

Masukan dan keluaran

Input Anda adalah array 2D persegi panjang dari bit A , diberikan dalam format apa pun yang nyaman. Tidak akan kosong, tetapi tidak dijamin mengandung 0s dan 1s. Array menggambarkan sulur jika kondisi berikut ini berlaku:

Baris bawah A mengandung setidaknya satu 1. Ini adalah akar dari pokok anggur.
Setiap 1 dalam A terhubung ke baris bawah dengan jalur 1s yang hanya bergerak ke kiri, kanan dan bawah (tidak naik, dan tidak secara diagonal). Jalan-jalan ini adalah cabang-cabang dari pokok anggur.

Output Anda adalah nilai kebenaran yang konsisten jika input menggambarkan anggur, dan nilai palsu yang konsisten sebaliknya.

Contohnya

Array ini menggambarkan sulur:

0 0 1 0 0 1
0 1 1 0 0 1
0 1 0 1 1 1
1 1 0 1 0 1
0 1 1 1 0 1
0 0 1 0 1 1

Input ini tidak menggambarkan anggur, karena ada 1 di tengah perbatasan kanan yang tidak terhubung ke akar oleh cabang:

0 0 0 1 1 0
0 1 0 1 1 1
0 1 0 1 0 1
0 1 1 1 1 0
0 0 1 1 0 1

Semua-0 array tidak pernah menggambarkan anggur, tetapi semua-1 array selalu.

Aturan dan penilaian

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

Uji kasus

Masukan yang benar:

Masukan palsu:

code-golf grid decision-problem Zgarb
sumber

1

Tidak menyadari bahwa anggur tidak dapat tumbuh ke bawah, punya ide bagus menggunakan komponen yang terhubung dari grafik, desah ...

desir

@ harap Semua itu berarti bahwa menghapus setiap baris pada gilirannya harus terus menghasilkan grafik yang terhubung ke garis 1s di bagian bawah.

Neil

26

Siput , 25 19 17 byte

&
\0z),(\1dlr)+d~

Cobalah online!

Penjelasan

Snails adalah bahasa pencocokan pola 2D yang terinspirasi oleh regex, yang awalnya dikembangkan untuk tantangan desain bahasa pencocokan pola 2D kami .

Para &siput membuat mencoba pola dari setiap posisi awal yang mungkin dan mencetak 0atau 1tergantung pada apakah pola gagal di salah satu dari mereka atau cocok dengan semuanya.

Sekarang siput dapat bekerja dengan tanda kurung implisit, jadi polanya adalah singkatan untuk yang berikut ini:

(\0z),(\1dlr)+d~

The ,bertindak seperti *di regex (yaitu cocok dengan nol atau lebih kali), sedangkan +adalah sama seperti di regex (mencocokkan satu atau lebih kali). Jadi kita mulai dengan mencocokkan \0zsesering yang diperlukan, yang cocok dengan satu 0dan kemudian memungkinkan siput untuk mengatur ulang arahnya secara sewenang-wenang z. Ini memungkinkan nol di input, asalkan sel anggur yang valid dapat ditemukan di tempat lain.

Kemudian kami mencocokkan setidaknya satu \1dlr, yang cocok dengan satu 1dan kemudian memungkinkan siput untuk mengatur ulang arahnya ke bawah, kiri atau kanan. Perhatikan bahwa jika sel tempat kita memulai mengandung 1maka kita hanya cocok dengan bagian ini. Ini pada dasarnya memungkinkan siput untuk melintasi pohon anggur dari cabang ke akar.

Akhirnya, kita perlu memastikan bahwa kita benar-benar mencapai tanah dengan mencari sel di luar batas ( ~) di bawah ( d).

Martin Ender
sumber

1

Saya terkejut bahwa ada yang bisa mengikuti dokumentasi :)

feersum

3

JavaScript (ES6), 135 byte

s=>s.replace(/^[^1]*\n/,``).split`
`.map(s=>+`0b${s}`).reverse(g=(n,m,o=(m<<1|m|m>>1)&n)=>n-m?o-m&&g(n,o):n).reduce((m,n,i)=>g(n,n&m))

Catatan: Karena keterbatasan tipe bilangan bulat, hanya berfungsi untuk tanaman merambat hingga 31 karakter. Penjelasan: Setiap baris bit ANDed dengan baris yang berdekatan untuk menentukan titik koneksi, dan kemudian gfungsi ini digunakan untuk memperluas baris secara horizontal sampai tidak dapat berkembang lagi. Misalnya, jika dua baris yang berdekatan adalah 1110111dan 1011100kemudian titik koneksi 1010100dan ini kemudian diperluas ke 1110110dan 1110111yang kemudian menemukan bahwa baris terhubung. Jika gfungsi gagal maka mengembalikan nol yang menyebabkan semua gfungsi berikutnya gagal juga, dan hasilnya kemudian palsu. Jika gfungsi berhasil mengembalikan baris baru yang kemudian disebarkan melalui reduceuntuk menguji baris berikutnya.

s=>s.replace(/^[^1]*\n/,``)         Remove irrelevant leading "blank" rows
    .split`\n`                      Split into lines
    .map(s=>+`0b${s}`)              Convert into binary
    .reverse(                       Process from bottom to top
     g=(n,m,o=(m<<1|m|m>>1)&n)=>     Expand row horizontally
      n-m?o-m&&g(n,o):n)             Check whether rows are connected
    .reduce((m,n,i)=>g(n,n&m))      Check all rows

Neil
sumber

Saya akan menetapkan bahwa 31 karakter cukup lebar, dan pendekatan ini valid.

Zgarb

2

Python 2, 254 byte

Tidak ada perpustakaan

def f(A,r=0,c=-1):
 B=A[r];R=len(A)-1;C=len(B);i=1 in A[R]
 if c<0:
    for j in range(R*C+C):
        if A[j/C][j%C]:i&=f(A,j/C,j%C)
    return i&1
 _=B[c];B[c]=0;i=_&(r==R)
 if _:
    if c>0:i|=f(A,r,c-1)
    if r<R:i|=f(A,r+1,c)
    if c<C-1:i|=f(A,r,c+1)
 B[c]=_;return i

Perhatikan bahwa indentasi tingkat kedua dan ketiga dibentuk dengan tab pada jumlah byte.

Cobalah online

Chuck Morris
sumber

1

Wolfram - 254

Luangkan waktu untuk membuat pekerjaan ini, jadi saya akan meninggalkannya di sini:

f[s_]:=(
v=Characters@StringSplit@s;
{h,w}=Dimensions@v;
g=GridGraph@{w,h};
r=First/@Position[Flatten@v,"0"];
g=VertexDelete[Graph[VertexList@g,
EdgeList@g/.x_y_/;Abs[x-y]>1yx],r];
v=VertexList@g;
v≠{}∧v~Complement~VertexOutComponent[g,Select[v,#>w h-w&]]{}
)

Pada dasarnya saya membuat grafik grid dengan ujung terarah mengarah ke atas, menghapus simpul yang sesuai dengan 0s, memeriksa apakah komponen simpul bawah mengandung semua simpul. Konyol, saya tahu ...

desir
sumber

2

Mengapa ini tidak bersaing?

Downgoat

1

Saat ini kami akan menganggap ini "bukan jawaban" karena tidak golf. Jika Anda cukup menghapus spasi kosong yang tidak perlu dan menambahkan jumlah byte, saya tidak melihat alasan mengapa ini tidak bersaing.

Alex A.

0

Python + NumPy 204 202 195 Bytes

from numpy import*
def f(A):
 r,c=A.shape
 z,s=zeros((r,1)),array([0,2,c+3])
 B=hstack((z,A,z)).flat
 for i in range(1,(r-1)*(c+2)):
    if B[i]and not any(B[s]):return 1<0
    s+=1
 return any(B[i:])

Diharapkan Amenjadi array numpy 2D.

Membawa matriks, bantalan nol kolom kiri dan kanan dan ratakan matriks. sadalah stensil yang menunjuk ke elemen kiri, kanan dan bawah. Loop memeriksa setiap elemen kecuali baris terakhir jika itu 1dan setidaknya salah satu stensilnya adalah 1, mengembalikan Falsesebaliknya. Setelah itu, periksa apakah baris terakhir berisi 1.

Dua testcases untuk Anda:

I1 = '001001\n011001\n010111\n110101\n011101\n001011'
A1 = array([int(c) for c in I1.replace('\n','')]).reshape(6,6)
print f(A1) #True

I2 = '001100\n111111\n110101\n010011\n111011'
A2 = array([int(c) for c in I2.replace('\n','')]).reshape(5,6)
print f(A2) #False

Sunting1: 1<0lebih pendek dariFalse

Sunting2: flatadalah alternatif yang baik untuk flatten()dan menggunakan tabulator untuk maksud kedua dalam loop

Karl Napf
sumber

Kenali anggur