Terinspirasi oleh /puzzling/24334/to-catch-a-thief

Anda diberi kotak ndengan n( nitu sendiri adalah input opsional) yang diisi dengan 0s dan 1s (atau karakter lain pilihan Anda). Anda bertujuan untuk membuat setiap sel sama (baik 0atau 1). Anda dapat melakukan serangkaian gerakan seperti yang didefinisikan di bawah ini (perhatikan perbedaannya dengan tautan SE yang membingungkan):

• Pilih sel.
• Setiap sel di baris dan kolom yang sama (kecuali sel itu sendiri) diubah menjadi kebalikannya. 0ke 1dan 1ke 0.

Keluarkan jumlah minimum gerakan yang diperlukan untuk menyelesaikan tugas. Jika tidak dapat dipecahkan, output apa pun kecuali integer non-negatif. Kode terpendek menang.

Contoh data

1 0 0
0 0 0
0 0 0

-1

1 1 1
1 1 1
1 1 1

0

1 0 1
0 1 0
1 0 1

1

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

2

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

2

Matlab 171 byte

Input harus berupa matriks 2d, jadi Anda akan menyebutnya seperti c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])(titik koma memulai baris baru). Fungsi ini hanya bruteforces semua gerakan yang mungkin, jadi kami mendapatkan runtime dari O(2^(n^2)).

Bagaimana itu dilakukan

Ini dilakukan dengan memilih semua cara yang mungkin untuk mengisi matriks lain dengan ukuran yang sama dengan yang satu dan nol, ini pada dasarnya menghitung dalam biner yang mana setiap entri matriks mewakili kekuatan tertentu 2.

Kemudian kami melakukan gerakan pada sel-sel yang 1, ini dilakukan dengan jumlah (mod 2) dari dua lilitan dua dimensi dengan vektor yang berukuran 1xn dan nx1.

Akhirnya kami memutuskan apakah gerakan itu benar-benar menghasilkan hasil yang diinginkan, dengan menghitung simpangan baku atas semua entri. Standar deviasi hanya nol jika semua entri sama. Dan setiap kali kami benar-benar menemukan hasil yang diinginkan, kami membandingkannya dengan jumlah gerakan solusi sebelumnya. Fungsi akan kembali infjika masalah yang diberikan tidak dapat dipecahkan.

Matematika?

Sebenarnya perlu dicatat bahwa semua gerakan itu bersama-sama menghasilkan kelompok abelian! Jika ada yang benar-benar berhasil mengkalsifikasi kelompok-kelompok itu, beri tahu saya.

Versi golf:

function M=c(a);n=numel(a);p=a;M=inf;o=ones(1,n);for k=0:2^n-1;p(:)=dec2bin(k,n)-'0';b=mod(conv2(p,o,'s')+conv2(p,o','s'),2);m=sum(p(:));if ~std(b(:)-a(:))&m<M;M=m;end;end

Versi lengkap (dengan output dari gerakan aktual.)

function M = c(a)
n=numel(a);
p=a;
M=inf;                                               %current minimum of number of moves
o=ones(1,n);
for k=0:2^n-1;
    p(:) = dec2bin(k,n)-'0';                         %logical array with 1 where we perform moves
    b=mod(conv2(p,o,'same')+conv2(p,o','same'),2);   %perform the actual moves
    m=sum(p(:));                                     %number of moves;
    if ~std(b(:)-a(:))&m<M                           %check if the result of the moves is valid, and better
        M=m;
        disp('found new minimum:')
        disp(M)                                      %display number of moves of the new best solution (not in the golfed version)
        disp(p)                                      %display the moves of the new best solution                               (not in the golfed version)
    end
end

Perl 5, 498 byte

Ini menerima 'n' dan hasil yang diinginkan, dan mengeluarkan hitungan, atau 'X' jika tidak ada.

Sebagai contoh:

perl ./crack.golf.pl 3 000111111

memberi 2. Ini hanya akan berfungsi ketika n ^ 2 <= 64, jadi n <= 8. Meskipun cukup lambat bahkan dengan n serendah 5. Ini membangun array ^ 3 bit, dan mengurutkan array 2 ^ (n ^ 2) sebelumnya, karena mengapa tidak ?

Saya telah menyia-nyiakan beberapa umpan baris di sini untuk dibaca :

$n=shift;$y=shift;$p=$n*$n;@m=(0..$n-1);@q=(0..$p-1);@v=(0..2**$p-1);@d=map{0}(@q);@b=map{$r=$_;map{$c=$_;$d[$r*$n+$_]^=1 for(@m);$d[$_*$n+$c]^=1 for(@m);$j=0;$k=1;
map{$j|=$k*$d[$_];$k<<=1;}@q;@d=map{0}(@q);$j;}@m}@m;for$k(sort{$a->[0]<=>$b->[0]}map{$z=0;map{$z+=$_}split(//,sprintf"%b",$_);[$z,$_]}@v){$l=sprintf"%0${p}b",$k->[1];
@m=map{$_}split(//,$l);$s=0;for(@q){$s^=$b[$_]if$m[$_];}$z=0;map{$z+=$_}split(//,sprintf"%b",$_);if($y eq sprintf"%0${p}b",$s){print"$k->[0]\n";exit 0;}}print"X\n";