Inspirado en /puzzling/24334/to-catch-a-thief

Se le proporciona una cuadrícula nby n(en nsí misma es entrada opcional) llena de 0sy 1s (o cualquier otro carácter de su elección). Su objetivo es hacer que cada celda sea igual ( 0o bien 1). Puede realizar una serie de movimientos como se define a continuación (observe la diferencia con el enlace Puzzling SE):

• Selecciona una celda.
• Cada celda en la misma fila y columna (excepto la celda misma) se cambia a su opuesto. 0a 1y 1a 0.

Produzca la cantidad mínima de movimientos necesarios para completar la tarea. Si no se puede resolver, envíe cualquier cosa excepto un número entero no negativo. El código más corto gana.

Data de muestra

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

La entrada debe ser una matriz 2d, por lo que la llamaría así c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])(los puntos y comas comienzan una nueva fila). Esta función simplemente fuerza bruta todos los movimientos posibles, por lo que tenemos un tiempo de ejecución de O(2^(n^2)).

Como esta hecho

Esto se hace eligiendo todas las formas posibles para llenar otra matriz del mismo tamaño con unos y cero, esto es básicamente contar en binario, donde cada entrada de la matriz representa una cierta potencia de 2.

Luego realizamos los movimientos en esas celdas que son 1, esto se hace mediante la suma (mod 2) de dos convoluciones bidimensionales con un vector de unos de tamaño 1xn y nx1.

Finalmente, decidimos si esos movimientos realmente produjeron el resultado deseado, calculando la desviación estándar de todas las entradas. La desviación estándar es solo ceros si todas las entradas son iguales. Y cada vez que encontramos el resultado deseado, lo comparamos con el número de movimientos de soluciones anteriores. La función volverá infsi el problema dado no se puede resolver.

¿Matemáticas?

¡Realmente vale la pena señalar que todos esos movimientos juntos generan un grupo abeliano! Si alguien realmente logra calificar esos grupos, hágamelo saber.

Versión de 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ón completa (con la salida de los movimientos reales).

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

Esto acepta 'n' y el resultado deseado, y genera el recuento, o 'X' si no hay ninguno.

Por ejemplo:

perl ./crack.golf.pl 3 000111111

da 2. Solo funcionará cuando n ^ 2 <= 64, entonces n <= 8. Aunque es bastante lento incluso con n tan bajo como 5. Construye una matriz ^ 3 bit, y ordena una matriz 2 ^ (n ^ 2) de antemano, porque ¿ por qué no ?

He desperdiciado un par de avances de línea aquí para facilitar la lectura :

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