Add sum of sub squares of a given nxn matrix (keon#631)

siderism · web-flow · commit ebc8de44dbc1 · 2020-02-12T21:25:56.000-08:00
* Added function to calculate sum of all sub-squares in a square matrix

* Added test for sum_sub_squares function

* Updated README
diff --git a/README.md b/README.md
@@ -236,6 +236,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
 	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py)
 	- [cholesky_matrix_decomposition](algorithms/matrix/cholesky_matrix_decomposition.py)
+    - [sum_sub_squares](algorithms/matrix/sum_sub_squares.py)
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
diff --git a/algorithms/matrix/sum_sub_squares.py b/algorithms/matrix/sum_sub_squares.py
@@ -0,0 +1,24 @@
+# Function to find sum of all  
+# sub-squares of size k x k in a given 
+# square matrix of size n x n 
+def sum_sub_squares(matrix, k):
+    n = len(matrix)
+    result = [[0 for i in range(k)] for j in range(k)]
+
+    if k > n:
+        return
+    for i in range(n - k + 1):
+        l = 0 
+        for j in range(n - k + 1):
+            sum = 0
+            
+            # Calculate and print sum of current sub-square 
+            for p in range(i, k + i):
+                for q in range(j, k + j):
+                    sum += matrix[p][q]
+            
+            result[i][l] = sum
+            l += 1 
+         
+    return result
+
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
@@ -7,7 +7,8 @@
     rotate_image,
     sparse_dot_vector,
     spiral_traversal,
-    sudoku_validator
+    sudoku_validator,
+    sum_sub_squares
 )
 import unittest
 
@@ -272,6 +273,21 @@ def test_sudoku_validator(self):
                     [3, 0, 0, 4, 8, 1, 1, 7, 9]
                 ]))
 
+class TestSumSubSquares(unittest.TestCase):
+    """[summary]
+    Test for the file sum_sub_squares.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_sum_sub_squares(self):
+        mat = [[1, 1, 1, 1, 1], 
+           [2, 2, 2, 2, 2], 
+           [3, 3, 3, 3, 3], 
+           [4, 4, 4, 4, 4], 
+           [5, 5, 5, 5, 5]]
+        self.assertEqual(sum_sub_squares.sum_sub_squares(mat, 3),
+                         [[18, 18, 18], [27, 27, 27], [36, 36, 36]])
 
 if __name__ == "__main__":
     unittest.main()
