from functools import wraps
import random
from time import time
import unittest
import math
curr_ms = lambda: int(round(time() * 1000))
def timed(f):
@wraps(f)
def wrapper(*args, **kwds):
start = curr_ms()
result = f(*args, **kwds)
elapsed = curr_ms() - start
print("{} took {}ms to finish".format(f.__name__, elapsed))
return result
return wrapper
@timed
def answer(matrix):
toggle = generateToggleMatrix(len(matrix))
puzzle = linearilizePuzzle(matrix)
try:
solution = solvePuzzle(toggle, puzzle)
printMatrix(solutionVectorToPairs(solution))
c = solution.count(1)
except RuntimeError:
return -1
return c
def rowMajorIndex(n, i, j):
return i * n + j
@timed
def generateToggleMatrix(n):
result = []
for i in xrange(n * n):
row = [0] * n * n
result.append(row)
for i in xrange(n):
for j in xrange(n):
col = n * i + j
result[col][col] = 1
for k in xrange(n):
result[col][n * i + k] = 1
result[col][n * k + j] = 1
return result
def linearilizePuzzle(puzzle):
return [item for sublist in puzzle for item in sublist]
def findPivot(m, start, col):
for row in xrange(start, len(m)):
if m[row][col]:
return row
return None
def swap(toggle, nextFreeRow, pivotRow):
toggle[pivotRow], toggle[nextFreeRow] = toggle[nextFreeRow], toggle[pivotRow]
@timed
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
def backSubstitute(toggle, puzzle):
result = [0] * len(puzzle)
pivot = -1
for row in xrange(len(puzzle) - 1, -1, -1):
for col in xrange(len(puzzle)):
if toggle[row][col]:
pivot = col
break
if pivot == -1:
if puzzle[row]:
raise RuntimeError("Puzzle has no solution")
else:
result[row] = puzzle[row]
for col in xrange(pivot + 1, len(puzzle)):
result[row] = 1 if (result[row] != (toggle[row][col] and result[col])) else 0
return result
def solutionVectorToPairs(solution):
result = []
n = int(math.sqrt(len(solution)))
for _ in xrange(n):
result.append(solution[:n])
solution = solution[n:]
return result
def solvePuzzle(toggle, puzzle):
toggle, puzzle = performGaussianElimination(toggle, puzzle)
return backSubstitute(toggle, puzzle)
def printMatrix(m):
for x in m:
for y in x:
print y,
print
if __name__ == "__main__":
size = 15
puzzle = []
for i in xrange(size + 1):
row = []
for j in xrange(size + 1):
row += [random.randint(0, 1)]
puzzle.append(row)
print answer(puzzle)