Repository: keon/algorithms
Pull request #631 (2020-02-04 20:23:36)

Add sum of sub squares of a given nxn matrix
(Put an X inside the [ ] to denote check mark [X].)
Added a function to calculate the sums of sub squares in a given matrix.

- [X] If creating a new file :

     - [X] added links to it in the README files ?
     - [X] included tests with it ?
     - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?
- [ ] if done some changes :

     - [ ] wrote short description in the PR explaining what the changes do ?
     - [ ] Fixes #[issue number] if related to any issue
- [ ] other



Patch:
diff --git a/README.md b/README.md
index 53b8c69..61daf4e 100644
--- 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
new file mode 100644
index 0000000..45de7f1
--- /dev/null
+++ 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
+


Test patch:
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
index 3522d7d..ad49ddd 100644
--- a/tests/test_matrix.py
+++ b/tests/test_matrix.py
@@ -7,7 +7,8 @@ from algorithms.matrix import (
     rotate_image,
     sparse_dot_vector,
     spiral_traversal,
-    sudoku_validator
+    sudoku_validator,
+    sum_sub_squares
 )
 import unittest
 
@@ -272,6 +273,21 @@ class TestSudokuValidator(unittest.TestCase):
                     [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()