Matlab 171 bytes
The input should be a 2d matrix, so you would call it like c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1])
(semicolons start a new row). This function just bruteforces all possible moves, so we get a runtime of O(2^(n^2))
.
How it is done
This is done by choosing all possible ways to fill another matrix of the same size with ones and zero, this is basically counting in binary wich where each entry of the matrix represents a certain power of 2.
Then we perform the moves on those cells that are 1, this is done by the sum (mod 2) of two two dimensional convolution with an vector of ones of size 1xn and nx1.
Finally we decide if those moves actually produced the desired result, by computing the standard deviation over all entries. The standard deviation is only zeros if all entries are the same. And whenever we actually found the desired result we compare it with the number of moves of previous solutions. The function will return inf
if the given problem is not solvable.
Math?
It is actually worth noting that all those moves together generate an abelian group! If anyone actually manages to calssify those groups please let me know.
Golfed version:
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
Full version (with the output of the actual moves.)
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
3What to do in case the puzzle is unsolvable? E.g.
1000
(rearranged as a square, doesn't matter how). – orlp – 2015-12-04T15:08:35.6372Related. – Martin Ender – 2015-12-04T15:42:11.533
@orlp Any output that is not a number will do. – ghosts_in_the_code – 2015-12-04T15:43:10.603
Do we need to parse the input or can it be any already filled array datatype? – coredump – 2015-12-04T16:11:34.583
@coredump Input can be given in any format. – ghosts_in_the_code – 2015-12-04T16:34:14.030
1What is the solution to the first test case? I'm getting no solutions for it. – cardboard_box – 2015-12-04T23:09:06.823
@cardboard_box Top-right corner, centre, bottom-right corner. – ghosts_in_the_code – 2015-12-05T07:50:18.373
@ghosts_in_the_code That definitely doesn't work. None of those three invert the center, for instance. – isaacg – 2015-12-05T08:51:33.650
Maybe you should just update the first example to not-solvable, and have a new one that really does take 3 turns. Having one whose lowest is 3 is a non-trivial example. – Dale Johnson – 2015-12-05T10:05:55.767
@DaleJohnson Can you prove it is unsolvable? – ghosts_in_the_code – 2015-12-05T12:10:17.460
@ghosts_in_the_code I have proven it to be unsolvable in the chat. It's possible to do so by constructing a system of linear equations in GF(2) that corresponds to flipping a cell for every location. Then you can see that it has no solutions for
[1, 0, 0, 0, 0, 0, 0, 0, 0]
. I'm not aware of an elegant simple proof though. – orlp – 2015-12-05T17:59:36.103There are 512 distinct boards in the 3 x 3 configuration. I have examined them all, starting from all zeros, and none of them end up as 1,0,0 0,0,0 0,0,0. Each of the 512 boards correspond to a series of 9 boolean choices (hence 2^9) and actions can be made in any order. – Dale Johnson – 2015-12-05T19:36:44.477