How can I further optimize this solver of a variant of "Lights Out"?

Question

I'm still solving this problem, taken from the current "Google Foobar" challenge. It's a variation of the "Lights Out" game, in which pressing a light will flip the state of every light on the same row and the same column.

I previously tried using a BFS, which turned out to be too slow for n > 6, while I need to handle 2 < n < 16. I currently have a program that can handle all even n and all odd numbers except 13 and 15. Here's what it does:

I use the strategy outlined by @Aryabhata to find a special solution x' of some system Ax = b that can be associated with an instance of this problem (see here for details).
Having found a base of the null space of A, I compute all sums of x' plus a linear combination of the vectors of the base.
The set of those sums is the set of all solutions of the original problem, therefore I can find by brute-force the solution that achieves the minimum.
It should be noted that, for n even, the null space is empty (A is invertible), therefore x' achieves the minimum because it's the only solution. If n is odd the number of vectors in a base of the null space is 2n - 2, therefore the search space has size 2^(2n - 2), which is 2^28 in the worst case (n = 15).

Here's my program:

from itertools import product


MEMO = {}


def bits(iterable):
    bit = 1
    res = 0
    for elem in iterable:
        if elem:
            res |= bit
        bit <<= 1
    return res


def mask(current, n):
    if (current, n) in MEMO:
        return MEMO[(current, n)]

    result = 0
    if current < n:
        for j in xrange(n):
            result += (2 ** ((current - 1)*n + j) + 2 ** (current*n + j))
    else:
        for i in xrange(n):
            result += (2 ** (i*n + current - n) + 2 ** (i*n + current - n + 1))

    MEMO[(current, n)] = result

    return result


# See: https://math.stackexchange.com/a/441697/4471
def check(matrix, n):
    parities = [sum(row) % 2 for row in matrix]
    for i in xrange(n):
        parities.append(sum([row[i] for row in matrix]) % 2)

    return len(set(parities)) == 1


def minimize(matrix, current, n):
    if current == 0:
        # See: https://stackoverflow.com/a/9831671/374865
        return bin(matrix).count("1")
    else:
        return min(minimize(matrix ^ mask(current, n), current - 1, n),
                   minimize(matrix, current - 1, n))


def solve(matrix, n):
    result = [0 for i in xrange(n) for j in xrange(n)]

    for i, j in product(xrange(n), repeat=2):
        if matrix[i][j]:
            for k in xrange(n):
                result[i*n + k] ^= 1
                result[k*n + j] ^= 1
            result[i*n + j] ^= 1

    if n % 2 == 0:
        return sum(result)
    else:
        return minimize(bits(result), 2*n - 2, n)


def answer(matrix):
    n = len(matrix)

    if n % 2 == 0:
        return solve(matrix, n)
    else:
        if check(matrix, n):
            return solve(matrix, n)
        else:
            return -1

I've already tried optimizing it: for instance, matrices are encoded as binary numbers by the function bits, while the function mask creates binary masks that are used to add a single element of the base to x'. Those masks are also memoized because they are frequently used, so that they are calculated only once.

The number of ones is then counted using the idiom bin(n).count('1'), which should be the fastest implementation (I checked it against the classical one by Kernighan).

So, what else can I do to squeeze more performance out of my program? Here are a few test cases:

print answer([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]), 1

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
]), 14

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
]), 15

print answer([
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]), 14

print answer([
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]), 15

EDIT: I passed this round. This implementation solves correctly 4 out of 5 test cases, then I brute-forced the fifth. I'm still interested in further optimizations or different algorithms!

EDIT 2: This answer, and in particular this paper give a proof that this particular problem is NP-hard (Section 3), which hints that we shouldn't be looking for a polynomial algorithm. So the question becomes: "What is the best exponent we can get?".

That's not really an option; this code needs to run on Google Foobar's interpreter, which is unknown and unaccessible to me. — Jacopo Notarstefano, Dec 12 '14 at 12:23
Pinging @Sven because I think he is/was working on the same problem. — Jacopo Notarstefano, Dec 12 '14 at 14:33
I didn't. Having an implementation that solves correctly 4 out of 5 test cases and a solution space of only 225 integers, I brute-forced it in the sense that I tried all possible solutions. — Jacopo Notarstefano, Dec 21 '14 at 18:43
@JacopoNotarstefano, sorry for getting that late to you, I just googled the problem again and found you've had the same problem. After my time ran out I didn't work any more on my problem. My math experience wasn't enough to [find the nullspace](http://stackoverflow.com/questions/27379340/find-all-solutions-of-row-reduced-echelon-matrix-in-pure-python). How much did you proceed further? — Sven, Jan 30 '15 at 00:00
@JacopoNotarstefano are you sure this is fast enough? It takes quite awhile to run for me. — mattgabor, Oct 29 '15 at 07:25
Are you running this on inputs with n an odd number bigger than 11? Because in all other cases I remember this being fast enough. — Jacopo Notarstefano, Oct 29 '15 at 10:30

score 4 · Answer 1 · answered Jan 07 '15 at 03:02

I tried everything about linear algebra, and since it is GF2, I do not think I could find the polynomial solution. Since the maximum number is 15, I further optimised it to approximately 2^15.

For even number

So, for n is even, there is a quicker way than standard linear algebra. If you have for example something like this, 0000 0100 0000 0000 The one solution should be (flip the row and column of the point exactly n times) 0100 1111 0100 0100 If you think about it, if you have a point which you want to flip, you can flip every point of the row and column once. (If that make sense), so it is easy to find one particular solution.

If I have something like this 0100 0010 0010 0000 one solution could be 1131 1221 1221 0120 and since flipping twice makes no difference, the solution can be reduced to 1111 1001 1001 0100

Then odd number

If n is odd, I can think of nothing but search. However, we can expand the n -> n+1 such that the solution to the problem should not contain flipping points of last row and last column.

If you have something 3x3 like: 010 001 001 you can always try expand solution to something like: 010x 001x 001x xxxx First, you will determine all the points in 3 by 3, 1111 1001 + ? 1001 0100 where ? should be solution to 000x 000x 000x xxxx As you can see, no matter how to flip, there is no way you can satisfy unless the xxx are the same bits. And you can try all the combination of the bottom to flip, and then you can determine the right hand side flipping or not by determine whether flipping results minimum number of 1 of the row.

I am really bad at explaining things, hope it will be clear enough.

I think I understood the gist of it, but I can't see how this reduces the problem to a search in a space of size n: the number of xs is actually 2n + 1, which is slightly worse than 2n - 2. — Jacopo Notarstefano, Jan 07 '15 at 04:08
I am afraid I am not good at my English. I explain more clearly. If you already flipped the bottom line, you do not have to try one after another for the right hand side because each line is indepenent. If you have a line like this `11101` you will definitely flip it because in the end you only have to flip 1 instead of 4. And on the contrary, if you have something like this `00110` you do not have to flip it. Is that clear enough? (BTW, it is the only problem I have to use Java instead of python for foobar challenge, it runs pretty fast on my computer, but it always tells me time exceeds) — darwinsenior, Jan 10 '15 at 05:55
I can confirm that the solution described by @darwinsenior works, leads to a very compact answer, and is fast enough to pass the challenge. More precisely, using a list of lists for the toggles matrix (called "result" in your code) is too slow, but changing it into a list of ints works. — Eugene Toder, Aug 04 '15 at 16:48

score 2 · Answer 2 · answered Mar 15 '16 at 21:36

I want to echo that darwinsenior's answer is very helpful! However, it took me a very long time to figure it out, even after reading that answer several times.

So, if you're late to foobar, like me, but want to get through this one without resorting to Java, here's a hint that might help.

The following light pattern isn't solvable, which I think is what confused me.

010
001
001

Here's a non-trivial example to demonstrate darwinsenior's idea: Say you want to solve this (N=5)

We know this is solvable because the parity of all sums and columns is odd.

And if N were even, it would be easier to find the answer. So, expand to N=6 as follows:

Like darwinsenior said, we want a solution to this that doesn't touch any lights in the bottom row or right-most column. Then we could take that solution, ignore the bottom row and right column and we'd have a solution to the original N=5 problem. So, we want to plug in values (not just zeros) but not have any button pushes in those columns in your answer.

This means you can't put a 1 in the bottom right. A light in the bottom right would mean at least 1 button pushed in the bottom row or right-most column. So that's one "degree of freedom" gone. Next, for the bottom row to have no button pushes, all those lights must have an even parity. Look to the answer to even N case to see why. So in the case above the parity is odd. We can fill the bottom row, but we must use an odd number of 1's. This removes another "degree of freedom". If we plug in 4 values (either 1s or 0s) then the 5th value is determined by this parity requirement. So, N-1 degrees of freedom here.

This is where the brute force part comes in. I had to try all possible values here (in this case all sets of 5 bits with odd parity) One example is to plug in 10101

Now we can use the rule for even N and get a solution. I'll write down the actual sum of row and column for each point, even though just the parity is needed in order to make it clearer what I did.

65555o      01111o
53343o      11101o
65465o   -> 01001o
66554o      00110o
54333o      10111o
66464_      00000_

I put little o's on the far right to say that the parity is odd, and because we haven't done anything with those yet. Because the parity is odd, this is no good, we would have a solution with all these being touched. But they all have odd parity, so we just need to plug in values such that the parity of the right-most column is odd, so the parity at each point is even (if that makes sense)

This is what darwinsenior said in this comment above (but I had a tough time following) The only requirement is that the parity of the column is odd and therefore no buttons on far right need to be pushed in the solution. We don't need to brute force this, we can use some logic to figure out which buttons to push while maintaining the parity requirement. By the way, we have N-1 free variables here, so 2*(N-1) free variables, just as in other solutions mentioned. Just that here we can see the effect of our choices on the button push count. I'll choose these values for the column: 11001 Now the example is:

110101                                    X00000 
010001                                    000X00 
111000   -- again use even N solution ->  0X00X0 
100110                                    00XX00 
000101                                    0X0000 
10101_                                    000000

So, I think that gives us an answer to the original N=5 case (just remove the zeros at bottom and at right). It has 7 button pushes, which I think is the best we can do with this one, but I'm not sure.

One more thing- even with this big reduction in the number of cases that need to be brute forced, I still had to do what Eugene said and use a list of ints, not a list of list of ints. Look to Jacopo's code and the "bits" function for that. Fun stuff.

score 0 · Answer 3 · answered Dec 15 '14 at 06:05

0

So I think you shouldn't need to brute force the odd case at all. My linear isn't too strong, but in R^n, if you want to find the shortest x satisfying Ax=b (which is essentially what we're doing), after finding some special solution x' you can project onto the nullspace of A and subtract the projection from x'. I believe this method should work even in F_2, though I'm not sure; please correct me if I'm wrong.

answered Dec 15 '14 at 06:05

fellowFoobarian

1
1

This is an interesting idea, but I don't understand a detail: the dot product of a basis vector with itself appears to be 0 in F_2, which makes the formula for the projection nonsensical. – Jacopo Notarstefano Dec 15 '14 at 09:49
Why is the dot product of a basis vector with itself 0? – fellowFoobarian Dec 15 '14 at 09:58
Maybe I'm misunderstanding something, but isn't the following true? http://mathb.in/25103 – Jacopo Notarstefano Dec 15 '14 at 10:26
@JacopoNotarstefano I think the problem you'll run into is that the solution vectors are orthogonal to vectors in the nullspace, so your projection has a length of zero. – Scott Harris Dec 15 '14 at 22:22
That might also happen. I remember that, while I was studying linear algebra, every theorem was prefixed by something like "Let F be a field of characteristic not 2..." : ) – Jacopo Notarstefano Dec 15 '14 at 22:45

score 0 · Answer 4 · edited May 18 '16 at 22:20

I like how @rustonian clarified the top answer on here, but there is one assumption that he took that I believe to be wrong, and that assumption is that the bottom right most bit of the added column and row can not be 1. It in fact can be 1 so that it may change all of the other added bits to 0. Here is an example of what I mean:

011    0110    4434    0010
110 -> 1100 -> 3444 -> 1000
101    1011    4644    0000
       0101    4443    0001

So it seems that the bottom right bit can be 1 iff it used to turn off all other added bits. This will not take away from the 3x3 solution since the toggling the bottom right added bit does not effect the original 3x3 space.

How can I further optimize this solver of a variant of "Lights Out"?

4 Answers4

For even number

Then odd number