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

Você recebe uma grade npor n( nela própria é uma entrada opcional) preenchida com 0s e 1s (ou qualquer outro caractere de sua escolha). Seu objetivo é tornar todas as células iguais ( 0ou 1). Você pode fazer uma série de movimentos, conforme definido abaixo (observe a diferença no link Puzzling SE):

• Selecione uma célula.
• Cada célula na mesma linha e coluna (exceto a própria célula) é alterada para o seu oposto. 0para 1e 1para 0.

Emita o número mínimo de movimentos necessários para concluir a tarefa. Se insolúvel, imprima qualquer coisa, exceto um número inteiro não negativo. O menor código vence.

Dados de amostra

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

A entrada deve ser uma matriz 2D, então você chamaria assim c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])(ponto-e-vírgula inicia uma nova linha). Esta função apenas força todos os movimentos possíveis, então obtemos um tempo de execução de O(2^(n^2)).

Como é feito

Isso é feito escolhendo-se todas as formas possíveis de preencher outra matriz do mesmo tamanho com um e zero, basicamente contando em binário, em que cada entrada da matriz representa uma certa potência de 2.

Depois realizamos os movimentos nessas células que são 1, isso é feito pela soma (mod 2) de uma convolução bidimensional com um vetor de tamanho 1xn e nx1.

Finalmente, decidimos se esses movimentos realmente produziram o resultado desejado, calculando o desvio padrão em todas as entradas. O desvio padrão é apenas zeros se todas as entradas forem iguais. E sempre que encontramos o resultado desejado, comparamos com o número de movimentos das soluções anteriores. A função retornaráinf se o problema especificado não for solucionável.

Matemática?

Na verdade, vale a pena notar que todos esses movimentos juntos geram um grupo abeliano! Se alguém realmente conseguir classificar esses grupos, informe-me.

Versão Golfed:

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

Versão completa (com a saída dos movimentos reais.)

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

Isso aceita 'n' e o resultado desejado e gera a contagem, ou 'X' se não houver.

Por exemplo:

perl ./crack.golf.pl 3 000111111

dá 2. Só funcionará quando n ^ 2 <= 64, então n <= 8. Embora seja bem lento, mesmo com n tão baixo quanto 5. Ele cria uma matriz de ^ 3 bits e classifica uma matriz de 2 ^ (n ^ 2) de antemão, porque por que não ?

Eu desperdicei alguns feeds de linha aqui para facilitar a leitura :

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