Speed up lights-out variant solver in pure Python

Question

I'm doing some challenges to learn new and interesting concepts, this one is about a Lights out variant, instead of toggling only the adjacent tiles, it toggles the whole row and col.

It must be solved in pure python, so no numpy or other libraries that might help are allowed here.

I adapted the algorithm of this excellent ressource. Using a n²*n² toggle matrix and a flattened puzzle P we can use a linear algebra to calculate T*x = P mod 2, where x is the matrix of buttons we need to push to solve the puzzle.

Since 1 < n < 16, this algorithm may need to solve matrices up to 225x225, which takes ~420ms on my machine. The exact time constraints aren't given, but I get a timeout error after submitting.

I pasted a running example here, this generates a random 15x15 puzzle and prints out a few timings and the solution to that particular puzzle.

The method performGaussianElimination(toggle, puzzle) takes by far the longest and seems to be the only bottleneck, but I don't see a place where I could use memoization or other shortcuts to save time. I've looked for other pure python linear algebra solvers, but there are only a few (numpy is so much easier) and don't seem to be a lot different.

def performGaussianElimination(toggle, puzzle):
    nextFreeRow = 0
    n = len(puzzle)
    for col in xrange(n):
        pivotRow = findPivot(toggle, nextFreeRow, col)
        if pivotRow is None:
            continue

        swap(toggle, nextFreeRow, pivotRow)
        swap(puzzle, nextFreeRow, pivotRow)

        for row in xrange(pivotRow + 1, n):
            if toggle[row][col]:
                for i in xrange(len(toggle[row])):
                    toggle[row][i] ^= toggle[nextFreeRow][i]
                puzzle[row] ^= puzzle[nextFreeRow]

        nextFreeRow += 1

    return toggle, puzzle

Can I speed this up? Might this traditionally fast algorithm not be the fastest for this variant?

Answer 1

You have a matrix of bits. You could represent each row by a single integer. (Remember that in Python the size of int is unlimited, so working with 255 bits is not a problem.) Then you would be able to avoid the inner loop here

for row in xrange(pivotRow + 1, n):
    if toggle[row][col]:
        for i in xrange(len(toggle[row])):
            toggle[row][i] ^= toggle[nextFreeRow][i]

and do this instead

col_mask = 1 << col
for row in xrange(pivotRow + 1, n):
    if toggle[row] & col_mask:
        toggle[row] ^= toggle[nextFreeRow]