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 n2*n2
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.
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?