fork(8) download
copy 
  1. from functools import wraps
  2. import random
  3. from time import time
  4. import unittest
  5. import math
  6.  
  7. curr_ms = lambda: int(round(time() * 1000))
  8.  
  9.  
  10. def timed(f):
  11.     @wraps(f)
  12.     def wrapper(*args, **kwds):
  13.         start = curr_ms()
  14.         result = f(*args, **kwds)
  15.         elapsed = curr_ms() - start
  16.         print("{} took {}ms to finish".format(f.__name__, elapsed))
  17.         return result
  18.  
  19.     return wrapper
  20.  
  21.  
  22. @timed
  23. def answer(matrix):
  24.     toggle = generateToggleMatrix(len(matrix))
  25.     puzzle = linearilizePuzzle(matrix)
  26.     try:
  27.         solution = solvePuzzle(toggle, puzzle)
  28.         printMatrix(solutionVectorToPairs(solution))
  29.         c = solution.count(1)
  30.     except RuntimeError:
  31.         return -1
  32.     return c
  33.  
  34.  
  35. def rowMajorIndex(n, i, j):
  36.     return i * n + j
  37.  
  38.  
  39. @timed
  40. def generateToggleMatrix(n):
  41.     result = []
  42.  
  43.     for i in xrange(n * n):
  44.         row = [0] * n * n
  45.         result.append(row)
  46.  
  47.     for i in xrange(n):
  48.         for j in xrange(n):
  49.             col = n * i + j
  50.             result[col][col] = 1
  51.  
  52.             for k in xrange(n):
  53.                 result[col][n * i + k] = 1
  54.                 result[col][n * k + j] = 1
  55.     return result
  56.  
  57.  
  58. def linearilizePuzzle(puzzle):
  59.     return [item for sublist in puzzle for item in sublist]
  60.  
  61.  
  62. def findPivot(m, start, col):
  63.     for row in xrange(start, len(m)):
  64.         if m[row][col]:
  65.             return row
  66.     return None
  67.  
  68.  
  69. def swap(toggle, nextFreeRow, pivotRow):
  70.     toggle[pivotRow], toggle[nextFreeRow] = toggle[nextFreeRow], toggle[pivotRow]
  71.  
  72.  
  73. @timed
  74. def performGaussianElimination(toggle, puzzle):
  75.     nextFreeRow = 0
  76.     n = len(puzzle)
  77.     for col in xrange(n):
  78.         pivotRow = findPivot(toggle, nextFreeRow, col)
  79.         if pivotRow is None:
  80.             continue
  81.  
  82.         swap(toggle, nextFreeRow, pivotRow)
  83.         swap(puzzle, nextFreeRow, pivotRow)
  84.  
  85.         for row in xrange(pivotRow + 1, n):
  86.             if toggle[row][col]:
  87.                 for i in xrange(len(toggle[row])):
  88.                     toggle[row][i] ^= toggle[nextFreeRow][i]
  89.                 puzzle[row] ^= puzzle[nextFreeRow]
  90.  
  91.         nextFreeRow += 1
  92.  
  93.     return toggle, puzzle
  94.  
  95.  
  96. def backSubstitute(toggle, puzzle):
  97.     result = [0] * len(puzzle)
  98.     pivot = -1
  99.     for row in xrange(len(puzzle) - 1, -1, -1):
  100.         for col in xrange(len(puzzle)):
  101.             if toggle[row][col]:
  102.                 pivot = col
  103.                 break
  104.         if pivot == -1:
  105.             if puzzle[row]:
  106.                 raise RuntimeError("Puzzle has no solution")
  107.         else:
  108.             result[row] = puzzle[row]
  109.             for col in xrange(pivot + 1, len(puzzle)):
  110.                 result[row] = 1 if (result[row] != (toggle[row][col] and result[col])) else 0
  111.  
  112.     return result
  113.  
  114.  
  115. def solutionVectorToPairs(solution):
  116.     result = []
  117.     n = int(math.sqrt(len(solution)))
  118.     for _ in xrange(n):
  119.         result.append(solution[:n])
  120.         solution = solution[n:]
  121.     return result
  122.  
  123.  
  124. def solvePuzzle(toggle, puzzle):
  125.     toggle, puzzle = performGaussianElimination(toggle, puzzle)
  126.     return backSubstitute(toggle, puzzle)
  127.  
  128.  
  129. def printMatrix(m):
  130.     for x in m:
  131.         for y in x:
  132.             print y,
  133.         print
  134.  
  135. if __name__ == "__main__":
  136. 	size = 15
  137. 	puzzle = []
  138. 	for i in xrange(size + 1):
  139. 	    row = []
  140. 	    for j in xrange(size + 1):
  141. 	        row += [random.randint(0, 1)]
  142. 	    puzzle.append(row)
  143. 	print answer(puzzle)
Success #stdin #stdout 0.71s 10552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
generateToggleMatrix took 2ms to finish
performGaussianElimination took 691ms to finish
0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0
1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1
0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0
0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1
1 1 0 1 1 1 1 0 1 1 1 0 0 0 1 0
0 0 1 0 0 1 1 0 1 1 0 1 0 0 0 1
0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0
0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0
0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0
1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0
1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1
0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0
0 1 1 0 1 0 0 1 1 1 0 0 0 0 1 0
0 0 0 1 0 0 1 1 1 0 1 0 0 0 0 1
0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1
0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0
answer took 703ms to finish
127
https://ideone.com/SNXU7U
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!