Inspirowane /puzzling/24334/to-catch-a-thief

Jesteś podawany był nprzez n( nsama jest opcjonalne wejście) siatka wypełniona 0s oraz 1s (lub dowolny inny znak wyboru). Twoim celem jest, aby każda komórka była taka sama (albo 0albo 1). Możesz wykonać serię ruchów, jak zdefiniowano poniżej (zauważ różnicę w łączu Puzzling SE):

• Wybierz komórkę.
• Każda komórka w tym samym wierszu i kolumnie (oprócz samej komórki) zostaje zamieniona na swoją stronę przeciwną. 0do 1i 1do 0.

Podaj minimalną liczbę ruchów wymaganych do wykonania zadania. Jeśli nierozwiązywalne, wypisz cokolwiek oprócz nieujemnej liczby całkowitej. Najkrótszy kod wygrywa.

Przykładowe dane

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 bajtów

Dane wejściowe powinny być macierzą 2D, więc nazwijmy to tak c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])(średniki rozpoczynają nowy wiersz). Ta funkcja po prostu brutalizuje wszystkie możliwe ruchy, więc otrzymujemy czas działania O(2^(n^2)).

Jak to jest zrobione

Odbywa się to poprzez wybranie wszystkich możliwych sposobów wypełnienia innej macierzy tego samego rozmiaru jednymi i zerami, co w zasadzie liczy się w postaci binarnej, w której każde wejście macierzy reprezentuje pewną potęgę 2.

Następnie wykonujemy ruchy na komórkach, które są 1, odbywa się to poprzez sumę (mod 2) dwuwymiarowego splotu z wektorem o wielkości 1xn i nx1.

Wreszcie decydujemy, czy te ruchy rzeczywiście przyniosły pożądany wynik, obliczając odchylenie standardowe dla wszystkich pozycji. Odchylenie standardowe wynosi tylko zero, jeśli wszystkie wpisy są takie same. I za każdym razem, gdy rzeczywiście znajdujemy pożądany wynik, porównujemy go z liczbą ruchów poprzednich rozwiązań. Funkcja powróciinf jeśli danego problemu nie da się rozwiązać.

Matematyka?

Warto zauważyć, że wszystkie te ruchy razem tworzą grupę abelową! Jeśli komuś uda się skorygować te grupy, proszę dać mi znać.

Wersja golfowa:

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

Pełna wersja (z danymi wyjściowymi rzeczywistych ruchów.)

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 bajtów

Akceptuje to „n” i pożądany wynik i wyświetla liczbę lub „X”, jeśli nie ma.

Na przykład:

perl ./crack.golf.pl 3 000111111

daje 2. Będzie działać tylko, gdy n ^ 2 <= 64, więc n <= 8. Chociaż jest dość powolny, nawet przy n tak niskim jak 5. Buduje tablicę ^ 3-bitową i wcześniej sortuje tablicę 2 ^ (n ^ 2), ponieważ dlaczego nie ?

Zmarnowałem tutaj kilka kanałów dla czytelności :

$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";