Inspiriert von /puzzling/24334/to-catch-a-thief

Sie sind eine gegeben ndurch n( nselbst ist optional Eingang) Gitter gefüllt mit 0s und 1s (oder jedem anderen Zeichen Ihrer Wahl). Ihr Ziel ist es, jede Zelle gleich zu machen (entweder 0oder 1). Sie können eine Reihe von Zügen ausführen, wie unten definiert (beachten Sie die Unähnlichkeit mit dem Puzzling SE-Link):

• Wählen Sie eine Zelle aus.
• Jede Zelle in derselben Zeile und Spalte (mit Ausnahme der Zelle selbst) wird in das Gegenteil geändert. 0zu 1und 1zu 0.

Geben Sie die Mindestanzahl von Zügen aus, die zum Ausführen der Aufgabe erforderlich sind. Wenn nicht lösbar, geben Sie etwas anderes als eine nicht negative Ganzzahl aus. Der kürzeste Code gewinnt.

Beispieldaten

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 Bytes

Die Eingabe sollte eine 2D-Matrix sein, also würden Sie es so nennen c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])(Semikolons beginnen eine neue Zeile). Diese Funktion erzwingt nur alle möglichen Bewegungen, sodass wir eine Laufzeit von erhalten O(2^(n^2)).

Wie es gemacht wird

Dies geschieht durch Auswahl aller möglichen Möglichkeiten, um eine andere Matrix derselben Größe mit Einsen und Null zu füllen. Dies zählt im Grunde genommen in Binärform, wobei jeder Eintrag der Matrix eine bestimmte Potenz von 2 darstellt.

Dann führen wir die Bewegungen an den Zellen durch, die 1 sind. Dies geschieht durch die Summe (mod 2) zweier zweidimensionaler Faltungen mit einem Vektor der Größe 1xn und nx1.

Schließlich entscheiden wir, ob diese Bewegungen tatsächlich das gewünschte Ergebnis liefern, indem wir die Standardabweichung über alle Einträge berechnen. Die Standardabweichung ist nur Null, wenn alle Einträge gleich sind. Und wann immer wir tatsächlich das gewünschte Ergebnis gefunden haben, vergleichen wir es mit der Anzahl der Züge früherer Lösungen. Die Funktion wird zurückgegeben, infwenn das angegebene Problem nicht lösbar ist.

Mathematik?

Es ist tatsächlich erwähnenswert, dass all diese Bewegungen zusammen eine abelsche Gruppe bilden! Wenn es jemandem tatsächlich gelingt, diese Gruppen zu verkalken, lassen Sie es mich bitte wissen.

Golfversion:

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

Vollversion (mit der Ausgabe der tatsächlichen Züge.)

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 Bytes

Dies akzeptiert 'n' und das gewünschte Ergebnis und gibt die Anzahl aus, oder 'X', wenn keine vorhanden ist.

Zum Beispiel:

perl ./crack.golf.pl 3 000111111

gibt 2. Es wird nur funktionieren, wenn n ^ 2 <= 64, also n <= 8. Obwohl es selbst mit n so niedrig wie 5 ziemlich langsam ist. Es baut ein ^ 3-Bit-Array auf und sortiert vorher ein 2 ^ (n ^ 2) -Array, denn warum nicht ?

Ich habe hier ein paar Zeilenvorschübe für die Lesbarkeit verschwendet :

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