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)