^{Tantangan ini benar - benar sangat terinspirasi oleh All Light , yang dikembangkan oleh Soulgit Games.}

Tantangan

Anda seorang tukang listrik, dan tugas Anda adalah untuk menghubungkan semua lampu ke baterai.

• Lampu dan baterai diletakkan dalam kisi-kisi.
• Anda dapat menghubungkan lampu atau baterai ke lampu terdekat atau baterai ke utara, selatan, timur, dan barat.
• Baterai dapat memiliki sejumlah koneksi.
• Setiap lampu menentukan berapa banyak koneksi yang dibutuhkan. Anda harus membuatnya dengan tepat bahwa banyak koneksi ke cahaya itu.
• Anda dapat membuat koneksi tunggal atau koneksi ganda antara dua lampu (atau lampu dan baterai).
• Kabel tidak bisa menyeberang.
• Harus ada jalur dari setiap lampu ke baterai.
• Setidaknya satu solusi yang valid dijamin ada.

Mengingat posisi baterai dan setiap cahaya, dan jumlah koneksi yang dibutuhkan masing-masing cahaya, output koneksi di antara mereka yang mengakui sifat-sifat ini.

Kondisi menang

Ini adalah kode-golf , sehingga kode terpendek dalam setiap bahasa menang.

Uji Kasus

I / O fleksibel seperti biasa.

Untuk input saya akan menggunakan array 2d ukuran grid yang menyimpan bilangan bulat positif untuk lampu, nol untuk ruang kosong, dan -1 untuk baterai. Pilihan lain yang baik mungkin daftar lampu, di mana cahaya adalah tuple yang berisi posisi cahaya dan jumlah koneksi yang diperlukan.

Untuk output saya akan menggunakan daftar koneksi, di mana koneksi adalah tuple yang berisi posisi awal dan posisi akhir. Jika koneksi dua kali lipat maka saya akan memiliki 2 dari mereka dalam daftar (opsi lain adalah memasukkan parameter ini dalam tuple). Pilihan bagus lainnya bisa berupa tata letak kotak.

Jika Anda menggunakan sistem koordinat Anda dapat menentukan indeks awal dan dari mana Anda indeks. Contoh saya akan diindeks 0 dan menggunakan (0, 0) sebagai sudut kiri atas (baris, kolom). (Saya menggunakan {} hanya untuk memperkenalkan pembatas jenis lain sehingga lebih mudah dibaca, bukan karena mereka set.)

Berikut ini adalah tampilan grafis dari kasus uji: Tes 1-12

Tes 1:

[-1 | 0 | 1 ] => [{(0, 0), (0, 2)}]

Tes 2:

[-1 | 0 | 2 ] => [{(0, 0), (0, 2)}, {(0, 0), (0, 2)}]

Tes 3:

[-1 ] [ 0 ] => [{(0, 0), (2, 0)), ((0, 0), (2, 0)}] [ 2 ]

Tes 4:

[ 1 | 0 |-1 | 0 | 2 ] => [{(0, 0), (0, 2)}, {(0, 2), (0, 4)}, {(0, 2), (0, 4)}]

Tes 5:

[ 2 ] [ 0 ] [-1 ] => [{(0, 0), (2, 0)}, {(0, 0), (2, 0)}, {(2, 0), (4, 0)}] [ 0 ] [ 1 ]

Tes 6:

[ 1 | 0 | 0 ] [ 0 | 0 | 0 ] => [{(0, 0), (2, 0)}, {(2, 0), (2, 2)}] [ 2 | 0 |-1 ]

Tes 7:

[ 4 | 0 | 0 |-1 ] [ 0 | 0 | 0 | 0 ] => [{(0, 0), (0, 3)}, {(0, 0), (0, 3)}, [ 2 | 0 | 0 | 0 ] {(0, 0), (3, 0)}, {(0, 0), (3, 0)}]

Tes 8:

[ 2 | 0 |-1 | 0 | 2 ] [{(0, 0), (0, 2)}, {(0, 0), (0, 2)}, [ 0 | 0 | 0 | 0 | 0 ] => {(0, 2), (0, 4)}, {(0, 2), (0, 4)}, [ 0 | 0 | 1 | 0 | 0 ] {(0, 2), (2, 2)}]

Tes 9:

[ 0 | 0 | 2 | 0 | 0 ] [ 0 | 0 | 0 | 0 | 0 ] [ 1 | 0 |-1 | 0 | 1 ] => [{(0, 2), (2, 2)}, {(0, 2), (2, 2)}, {(2, 0), (2, 2)}, [ 0 | 0 | 0 | 0 | 0 ] {(4, 2), (2, 2)}, {(2, 4), (2, 2)}, {(2, 4), (2, 2)}] [ 0 | 0 | 2 | 0 | 0 ]

Tes 10:

[-1 | 2 | 3 | 2 ] => [{(0, 0), (0, 3)}, {(0, 0), (0, 3)}, {(0, 0), (0, 3)}, {(0, 0), (0, 3)}]

Tes 11:

[-1 | 0 | 0 | 0 ] [ 3 | 0 | 0 | 0 ] [ 3 | 0 | 0 | 3 ] => [{(0, 0), (1, 0)}, {(1, 0), (2, 0)}, {(1, 0), (2, 0)}, [ 0 | 0 | 0 | 0 ] {(2, 0), (2, 3)}, {(2, 3), (4, 3)}, {(2, 3), (4, 3)}] [ 0 | 0 | 0 | 2 ]

Tes 1 2:

[ 2 | 0 | 0 ] [{(0, 0), (1, 0)}, {(0, 0), (1, 0)}, {(1, 0), (1, 1)}, [ 3 |-1 | 0 ] => {(1, 1), (2, 1)}, {(1, 1), (2, 1)}, {(2, 0), (2, 1)}, [ 2 | 5 | 1 ] {(2, 0), (2, 1)}, {(2, 1), (2, 2)}]

JavaScript (Node.js) , 393 391 378 byte

a=>(R=[],f=(a,[x,...y],z,Y)=>x?f(a.map(t=>[...t]),y,z,Y)||f(a,y,[...z,x],Y.map(p=>p.map(q=>q-Y[x[0]][x[1]]?q:Y[x[2]][x[3]])),--a[x[0]][x[1]],--a[x[2]][x[3]]):/[1-9]/.test(a)|Y.some(t=>t.some(u=>u-Y[I][J]&&u))?0:z)(a=a.map(A=(b,i)=>b.map((x,j)=>x&&(A[i]+1&&R.push([i,A[i],i,j]),f[j]+1&&R.push([f[j],j,i,j]),A[I=i]=j,f[J=j]=i,x/=x>0))),[...R,...R],C=[],a.map(p=>p.map(q=>q&&++C)))

Cobalah online!

a=>(
    a=a.map(
        A=(b,i)=>
            b.map(
                (x,j)=>
                    x&&(                                  // A[i]+1 <==> A[i] is NOT NaN
                        A[i]+1&&R.push([i,A[i],i,j]),     // Use A and f to store last
                        f[j]+1&&R.push([f[j],j,i,j]),     // existance of row and column
                        A[I=i]=j,f[J=j]=i,x/=x>0          // -1 => -Inf, +n => n
                    )
            ),
            R=[],
            f=([x,...y],z,Y)=>
                x?
                    f(
                        y,[...z,x],
                        Y.map(p=>p.map(q=>q-Y[x[0]][x[1]]?q:Y[x[2]][x[3]])), // merge
                        --a[x[0]][x[1]],--a[x[2]][x[3]]
                    )||
                    f(y,z,Y,++a[x[0]][x[1]],++a[x[2]][x[3]])
                :
                    /[1-9]/.test(a)|
                    Y.some(t=>t.some(u=>u-Y[I][J]&&u)) // not totally merged
                    ?0:z
    ),f)([...R,...R],[],a.map(p=>p.map(q=>q&&++C),C=0)
)