Diagonisasi blok biaya minimum

10

Pertimbangkan matriks diagonal blok biner yang memiliki blok kuadrat 1s pada diagonal utama, dan bernilai 0 di tempat lain. Sebut saja matriks seperti itu "valid".

Sebagai contoh, berikut adalah beberapa matriks 4x4 yang valid:

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

Perhatikan bahwa cara alternatif untuk menggambarkan matriks seperti itu adalah bahwa ada rantai blok persegi 1 dari kiri atas ke kanan bawah, menyentuh sudut ke sudut, dan di mana pun yang lain adalah 0.

Sebagai kontras, berikut adalah beberapa matriks 4x4 yang tidak valid:

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

Anda akan diberikan noleh nmatriks biner sebagai input - berapakah jumlah minimum 0bit yang perlu Anda atur 1untuk mendapatkan matriks yang valid?

Anda dapat menulis fungsi atau mengambil program string nyaman, daftar atau matriks Format mewakili noleh nmatriks 0 dan 1 (asalkan tidak preprocessed). Baris harus dipisahkan dengan jelas dalam beberapa cara, jadi format seperti array bit 1D tidak diperbolehkan.

Ini adalah kode-golf , jadi tujuannya adalah untuk meminimalkan jumlah byte dalam program Anda.

Contohnya

Misalnya, jika inputnya adalah

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

maka jawabannya adalah 5, karena Anda dapat mengatur lima 0bit 1untuk mendapatkan:

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

dan ini adalah angka minimum yang diperlukan. Namun, jika input tadi

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

maka jawabannya adalah 24, karena satu-satunya matriks 5x5 yang valid di mana kanan-atas 1adalah matriks semua 1s.

Uji kasus

Tes diwakili di sini sebagai array 2D bilangan bulat.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Catatan

code-golf array-manipulation Sp3000
sumber

Jawaban:

3

MATL , 46 43 byte

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Input adalah array 2D dengan titik koma sebagai pemisah baris. Misalnya, input untuk kasus uji terakhir adalah

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Cobalah online! Atau verifikasi semua kasus uji (kode sedikit dimodifikasi untuk mengambil semua input; hasilnya muncul setelah beberapa detik)

Penjelasan

Biarkan input menjadi N × N matriks. Kode pertama menghitung semua ( N +1) -jenis ukuran blok yang menghasilkan ukuran matriks yang sesuai. Sebagai contoh, untuk N = 4 tuple yang 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. Untuk setiap tuple itu membangun matriks blok-diagonal dengan ukuran blok itu. Kemudian memeriksa apakah matriks mencakup semua 1entri dalam input, dan jika demikian perhatikan jumlah 1entri yang tidak ada dalam input. Hasil akhir adalah minimum dari semua angka yang diperoleh.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display
Luis Mendo
sumber
3

Python dengan numpy, 102

from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

Algoritma yang efisien. Temukan "titik leher" pada diagonal yang dapat memisahkan blok. Ini memiliki semua 0 di atas dan kanan, serta di bawah dan kiri. Blok minimal adalah di antara titik leher.

??000
??000
00???
00???
00???

Panjang blok adalah perbedaan antara titik-titik leher berurutan, jadi total area mereka dari jumlah kuadrat ini. Mengurangkan jumlah dari matriks asli kemudian memberikan jumlah flips yang dibutuhkan dari 0 hingga 1.

Tidak
sumber
2

Pyth, 45 byte

[email protected]^+LsYN2d+0._ds.pM./lQss

Tugas yang sulit, jadi itu cukup lama.

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

s.pM./lQmenghitung semua partisi integer dari len(matrix). ms.b^+LsYN2d+0._dmengubahnya menjadi pasangan koordinat. Misalnya partisi [1, 2, 2]dari 5mendapat dikonversi ke dalam [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

[email protected]kemudian memfilter untuk partisi, yang benar-benar tumpang tindih dengan matriks ( .DRlQx1sQmenghitung semua pasangan koordinat sel aktif dalam matriks).

-hSlM...ss menghitung sel dari setiap partisi yang tersisa, memilih satu dengan sel yang paling sedikit, dan mengurangi sel yang sudah aktif.

Jakube
sumber
0

Matricks , 180 byte (tidak bersaing)

Matricks adalah esolang baru yang saya buat baru-baru ini untuk menangani masalah matriks (seperti yang ini), dengan hanya memiliki 2 tipe data: float dan matricies. Ini belum berfitur lengkap, dan masih memiliki banyak operasi yang hilang (saya harus menambahkan beberapa fungsi untuk tantangan ini). Bagaimanapun, ini kodenya:

il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

Penjelasan

Bagian pertama, il=1:j3;:...;memeriksa apakah array berukuran 1. Jika itu, ia melompat ke baris terakhir kg:;*-1+1;,, yang merupakan 0 <-> 1fungsi sederhana .

Jika tidak, ia melanjutkan dengan sisa kode. bdx;;;setel sel 0,0ke jumlah saat ini, dan s1::L;j1;membuat penghitung di sel pada baris di bawah ini.

Baris berikutnya sedikit lebih rumit. Ini adalah loop yang berjalan nkali, nmenjadi ukuran matriks. Saya akan menggunakan test case ke-3 sebagai contoh. Ketika kita pertama kali sampai ke baris kedua, matriksnya terlihat seperti ini:

1 0 1
2 0 0

Pertama, kita masuk ke pemahaman matriks {q:1;m...;}. Ini membuat diagonal, dan mencoba yang terbaik untuk membersihkan 0 yang perlu diisi. Semua ini dilakukan dengan menggunakan operator boolean sederhana. Kemudian, kami menambahkannya ke matriks saat ini, memberikan ini:

    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

Kemudian, kita memotong matriks lama menggunakan z:(l-1)/2;, dan memutar seluruh matriks ke kiri menggunakan B1;. Itu memberi kita sebuah matriks yang siap untuk iterasi berikutnya, terlihat seperti:

1 1 1
2 1 1

Akhirnya, kami mengurangi penghitung, memeriksanya, dan melanjutkan ig1:;=0:j2;:j1;;

Setelah loop keluar, kami menemukan jumlah baru dan mengatur tempat lama penghitung s1::d{q:1;};;. Akhirnya, kami mengambil perbedaan dan kembali kg1:;-g:;;. kmenyetel array saat ini ke suatu nilai, dan pencetakan tersirat.

...

Seperti yang bisa Anda lihat, Matricks cukup verbose, dan bukan bahasa golf yang sangat baik. Namun, saya ingin memamerkannya.

Biru
sumber