fork download
copy 
  1. #!/usr/bin/python
  2. # -*- coding: utf-8 -*-
  3.  
  4. # this implementation of the Strassen algorithm is from
  5. # https://g...content-available-to-author-only...b.com/MartinThoma/matrix-multiplication
  6.  
  7. from math import ceil, log
  8.  
  9. def ikjMatrixProduct(A, B):
  10.     n = len(A)
  11.     C = [[0 for i in xrange(n)] for j in xrange(n)]
  12.     for i in xrange(n):
  13.         for k in xrange(n):
  14.             for j in xrange(n):
  15.                 C[i][j] += A[i][k] * B[k][j]
  16.     return C
  17.  
  18. def add(A, B):
  19.     n = len(A)
  20.     C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
  21.     for i in xrange(0, n):
  22.         for j in xrange(0, n):
  23.             C[i][j] = A[i][j] + B[i][j]
  24.     return C
  25.  
  26. def subtract(A, B):
  27.     n = len(A)
  28.     C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
  29.     for i in xrange(0, n):
  30.         for j in xrange(0, n):
  31.             C[i][j] = A[i][j] - B[i][j]
  32.     return C
  33.  
  34. def strassenR(A, B):
  35.     """ Implementation of the strassen algorithm, similar to 
  36.         http://e...content-available-to-author-only...a.org/w/index.php?title=Strassen_algorithm&oldid=498910018#Source_code_of_the_Strassen_algorithm_in_C_language
  37.     """
  38.     n = len(A)
  39.  
  40.     if n <= LEAF_SIZE:
  41.         return ikjMatrixProduct(A, B)
  42.     else:
  43.         # initializing the new sub-matrices
  44.         newSize = n/2
  45.         a11 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  46.         a12 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  47.         a21 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  48.         a22 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  49.  
  50.         b11 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  51.         b12 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  52.         b21 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  53.         b22 = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  54.  
  55.         aResult = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  56.         bResult = [[0 for j in xrange(0, newSize)] for i in xrange(0, newSize)]
  57.  
  58.         # dividing the matrices in 4 sub-matrices:
  59.         for i in xrange(0, newSize):
  60.             for j in xrange(0, newSize):
  61.                 a11[i][j] = A[i][j]            # top left
  62.                 a12[i][j] = A[i][j + newSize]    # top right
  63.                 a21[i][j] = A[i + newSize][j]    # bottom left
  64.                 a22[i][j] = A[i + newSize][j + newSize] # bottom right
  65.  
  66.                 b11[i][j] = B[i][j]            # top left
  67.                 b12[i][j] = B[i][j + newSize]    # top right
  68.                 b21[i][j] = B[i + newSize][j]    # bottom left
  69.                 b22[i][j] = B[i + newSize][j + newSize] # bottom right
  70.  
  71.         # Calculating p1 to p7:
  72.         aResult = add(a11, a22)
  73.         bResult = add(b11, b22)
  74.         p1 = strassenR(aResult, bResult) # p1 = (a11+a22) * (b11+b22)
  75.  
  76.         aResult = add(a21, a22)      # a21 + a22
  77.         p2 = strassenR(aResult, b11)  # p2 = (a21+a22) * (b11)
  78.  
  79.         bResult = subtract(b12, b22) # b12 - b22
  80.         p3 = strassenR(a11, bResult)  # p3 = (a11) * (b12 - b22)
  81.  
  82.         bResult = subtract(b21, b11) # b21 - b11
  83.         p4 =strassenR(a22, bResult)   # p4 = (a22) * (b21 - b11)
  84.  
  85.         aResult = add(a11, a12)      # a11 + a12
  86.         p5 = strassenR(aResult, b22)  # p5 = (a11+a12) * (b22)   
  87.  
  88.         aResult = subtract(a21, a11) # a21 - a11
  89.         bResult = add(b11, b12)      # b11 + b12
  90.         p6 = strassenR(aResult, bResult) # p6 = (a21-a11) * (b11+b12)
  91.  
  92.         aResult = subtract(a12, a22) # a12 - a22
  93.         bResult = add(b21, b22)      # b21 + b22
  94.         p7 = strassenR(aResult, bResult) # p7 = (a12-a22) * (b21+b22)
  95.  
  96.         # calculating c21, c21, c11 e c22:
  97.         c12 = add(p3, p5) # c12 = p3 + p5
  98.         c21 = add(p2, p4)  # c21 = p2 + p4
  99.  
  100.         aResult = add(p1, p4) # p1 + p4
  101.         bResult = add(aResult, p7) # p1 + p4 + p7
  102.         c11 = subtract(bResult, p5) # c11 = p1 + p4 - p5 + p7
  103.  
  104.         aResult = add(p1, p3) # p1 + p3
  105.         bResult = add(aResult, p6) # p1 + p3 + p6
  106.         c22 = subtract(bResult, p2) # c22 = p1 + p3 - p2 + p6
  107.  
  108.         # Grouping the results obtained in a single matrix:
  109.         C = [[0 for j in xrange(0, n)] for i in xrange(0, n)]
  110.         for i in xrange(0, newSize):
  111.             for j in xrange(0, newSize):
  112.                 C[i][j] = c11[i][j]
  113.                 C[i][j + newSize] = c12[i][j]
  114.                 C[i + newSize][j] = c21[i][j]
  115.                 C[i + newSize][j + newSize] = c22[i][j]
  116.         return C
  117.  
  118. def strassen(A, B):
  119.     assert type(A) == list and type(B) == list
  120.     assert len(A) == len(A[0]) == len(B) == len(B[0])
  121.     # Make the matrices bigger so that you can apply the strassen
  122.     # algorithm recursively without having to deal with odd
  123.     # matrix sizes
  124.     nextPowerOfTwo = lambda n: 2**int(ceil(log(n,2)))
  125.     n = len(A)
  126.     m = nextPowerOfTwo(n)
  127.     APrep = [[0 for i in xrange(m)] for j in xrange(m)]
  128.     BPrep = [[0 for i in xrange(m)] for j in xrange(m)]
  129.     for i in xrange(n):
  130.         for j in xrange(n):
  131.             APrep[i][j] = A[i][j]
  132.             BPrep[i][j] = B[i][j]
  133.     CPrep = strassenR(APrep, BPrep)
  134.     C = [[0 for i in xrange(n)] for j in xrange(n)]
  135.     for i in xrange(n):
  136.         for j in xrange(n):
  137.             C[i][j] = CPrep[i][j]
  138.     return C
  139.  
  140. def printMatrix(matrix):
  141.     for line in matrix:
  142.         print "\t".join(map(str,line))
  143.  
  144. if __name__ == "__main__":
  145.     LEAF_SIZE = 128
  146.     N = int(raw_input())
  147.     A = [[0 for i in xrange(N)] for j in xrange(N)]
  148.     for i in range(N):
  149.         ins = raw_input()
  150.         ins = list(ins)
  151.         ins = map(int,ins)
  152.         A[i] = ins
  153.     C = strassen(A, A)
  154.     ans = 0
  155.     for i in xrange(0,N):
  156.         for j in xrange(0,N):
  157.             if C[i][j] != 0 and i != j and A[i][j] != 1:
  158.                 ans += 1
  159.     print ans
Success #stdin #stdout 0.01s 7900KB
comments (?)
stdin
copy 
6
010000
100000
000101
001000
000001
001010
stdout
copy 
4
https://ideone.com/dVGnoF
language:
Python (cpython 2.7.16)
created:
9 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!