Repository: keon/algorithms (python)

Issue:
Consider using black as an automatic code formatter
[Black](https://github.com/ambv/black) is a Python code-formatter that advertises itself as being "uncompromising". Containing few configuration options, it deals with the hassle of different developers having different styles of their code.

I recommend asking new contributors to run black on their source code so that a consistent style is maintained throughout the codebase. To enforce this, a job could be added in Travis CI that checks this.

Thoughts?

PS: I'm not associated with black in any way. I've just used it in my own projects and would recommend it for the sake of consistency.

I'd also be happy to send you a PR with the code formatted.

Pull request:
Black in travis ci
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [X] Fixes #479 if related to any issue

- [ ] **other**

This fixes issue #479 if you would like to add black in the CI.

It will not make every build (from this PR) fail in the CI but log all files that would be reformatted. In order to install black during CI, it was necessary to drop python 3.5 as black needs python 3.6.0+ 

Patch:
diff --git a/.travis.yml b/.travis.yml
index 37013bd..94607d4 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -6,8 +6,6 @@ cache:
     - $HOME/.cache/pip
 matrix:
     include:
-        - python: 3.5
-          env: TOX_ENV=py35
         - python: 3.6
           env: TOX_ENV=py36
         - python: 3.7
@@ -15,6 +13,8 @@ matrix:
 install:
     - pip install -r test_requirements.txt
 before_script:
+    # run black to check if some files would need reformatting
+    - black --check . || true
     # stop the build if there are Python syntax errors or undefined names
     - flake8 . --count --select=E9,F63,F7,F82 --show-source --statistics
     # exit-zero treats all errors as warnings.  The GitHub editor is 127 chars wide
diff --git a/README.md b/README.md
index f30d452..4b67fe5 100644
--- a/README.md
+++ b/README.md
@@ -223,6 +223,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [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)
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
diff --git a/algorithms/arrays/flatten.py b/algorithms/arrays/flatten.py
index 4133c34..f19156a 100644
--- a/algorithms/arrays/flatten.py
+++ b/algorithms/arrays/flatten.py
@@ -3,7 +3,7 @@ Implement Flatten Arrays.
 Given an array that may contain nested arrays,
 produce a single resultant array.
 """
-from collections import Iterable
+from collections.abc import Iterable
 
 
 # return list
diff --git a/algorithms/bfs/maze_search.py b/algorithms/bfs/maze_search.py
index 436b3ef..f7410d4 100644
--- a/algorithms/bfs/maze_search.py
+++ b/algorithms/bfs/maze_search.py
@@ -1,6 +1,8 @@
+from collections import deque
+
 '''
-BFS time complexity : O(|E|)
-BFS space complexity : O(|V|)
+BFS time complexity : O(|E| + |V|)
+BFS space complexity : O(|E| + |V|)
 
 do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
 
@@ -24,25 +26,42 @@ If grid is
 the answer is: -1
 '''
 
-def maze_search(grid):
-    dx = [0,0,-1,1]
-    dy = [-1,1,0,0]
-    n = len(grid)
-    m = len(grid[0])
-    q = [(0,0,0)]
-    visit = [[0]*m for _ in range(n)]
-    if grid[0][0] == 0:
+def maze_search(maze):
+    BLOCKED, ALLOWED = 0, 1
+    UNVISITED, VISITED = 0, 1
+
+    initial_x, initial_y = 0, 0
+
+    if maze[initial_x][initial_y] == BLOCKED:
         return -1
-    visit[0][0] = 1
-    while q:
-        i, j, step = q.pop(0)
-        if i == n-1 and j == m-1:
-            return step
-        for k in range(4):
-            x = i + dx[k]
-            y = j + dy[k]
-            if x>=0 and x<n and y>=0 and y<m:
-                if grid[x][y] ==1 and visit[x][y] == 0:
-                    visit[x][y] = 1
-                    q.append((x,y,step+1))
-    return -1
+    
+    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
+
+    height, width = len(maze), len(maze[0])
+
+    target_x, target_y = height - 1, width - 1
+
+    queue = deque([(initial_x, initial_y, 0)])
+
+    is_visited = [[UNVISITED for w in range(width)] for h in range(height)]
+    is_visited[initial_x][initial_y] = VISITED
+
+    while queue:
+        x, y, steps = queue.popleft()
+
+        if x == target_x and y == target_y:
+            return steps
+
+        for dx, dy in directions:
+            new_x = x + dx
+            new_y = y + dy
+
+            if not (0 <= new_x < height and 0 <= new_y < width):
+                continue
+
+            if maze[new_x][new_y] == ALLOWED and is_visited[new_x][new_y] == UNVISITED:
+                queue.append((new_x, new_y, steps + 1))
+                is_visited[new_x][new_y] = VISITED
+
+    return -1 
+
diff --git a/algorithms/graph/find_path.py b/algorithms/graph/find_path.py
index d1716c0..a188005 100644
--- a/algorithms/graph/find_path.py
+++ b/algorithms/graph/find_path.py
@@ -21,7 +21,6 @@ def find_path(graph, start, end, path=[]):
 # find all path
 def find_all_path(graph, start, end, path=[]):
     path = path + [start]
-    print(path)
     if (start == end):
         return [path]
     if not start in graph:
diff --git a/algorithms/matrix/cholesky_matrix_decomposition.py b/algorithms/matrix/cholesky_matrix_decomposition.py
new file mode 100644
index 0000000..4b5e24e
--- /dev/null
+++ b/algorithms/matrix/cholesky_matrix_decomposition.py
@@ -0,0 +1,48 @@
+"""
+Cholesky matrix decomposition is used to find the decomposition of a Hermitian positive-definite matrix A
+into matrix V, so that V * V* = A, where V* denotes the conjugate transpose of L.
+The dimensions of the matrix A must match.
+
+This method is mainly used for numeric solution of linear equations Ax = b.
+
+example:
+Input matrix A:
+[[  4,  12, -16],
+ [ 12,  37, -43],
+ [-16, -43,  98]]
+
+Result:
+[[2.0, 0.0, 0.0],
+[6.0, 1.0, 0.0],
+[-8.0, 5.0, 3.0]]
+
+Time complexity of this algorithm is O(n^3), specifically about (n^3)/3
+
+"""
+import math
+
+
+def cholesky_decomposition(A):
+    """
+    :param A: Hermitian positive-definite matrix of type List[List[float]]
+    :return: matrix of type List[List[float]] if A can be decomposed, otherwise None
+    """
+    n = len(A)
+    for ai in A:
+        if len(ai) != n:
+            return None
+    V = [[0.0] * n for _ in range(n)]
+    for j in range(n):
+        sum_diagonal_element = 0
+        for k in range(j):
+            sum_diagonal_element = sum_diagonal_element + math.pow(V[j][k], 2)
+        sum_diagonal_element = A[j][j] - sum_diagonal_element
+        if sum_diagonal_element <= 0:
+            return None
+        V[j][j] = math.pow(sum_diagonal_element, 0.5)
+        for i in range(j+1, n):
+            sum_other_element = 0
+            for k in range(j):
+                sum_other_element += V[i][k]*V[j][k]
+            V[i][j] = (A[i][j] - sum_other_element)/V[j][j]
+    return V


Test patch:
diff --git a/test_requirements.txt b/test_requirements.txt
index 7a3e47c..f0afad0 100644
--- a/test_requirements.txt
+++ b/test_requirements.txt
@@ -4,3 +4,4 @@ coverage
 nose
 pytest
 tox
+black
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
index 4d7e129..3522d7d 100644
--- a/tests/test_matrix.py
+++ b/tests/test_matrix.py
@@ -2,6 +2,7 @@ from algorithms.matrix import (
     bomb_enemy,
     copy_transform,
     crout_matrix_decomposition,
+    cholesky_matrix_decomposition,
     multiply,
     rotate_image,
     sparse_dot_vector,
@@ -93,6 +94,39 @@ class TestCroutMatrixDecomposition(unittest.TestCase):
                              [[2, 1, 3, 1], [4, 1, 4, 1], [6, 1, 7, 1], [8, 1, 9, 1]]))
 
 
+class TestCholeskyMatrixDecomposition(unittest.TestCase):
+    """[summary]
+    Test for the file cholesky_matrix_decomposition.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_cholesky_matrix_decomposition(self):
+        self.assertEqual([[2.0, 0.0, 0.0],
+                          [6.0, 1.0, 0.0],
+                          [-8.0, 5.0, 3.0]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98]]))
+
+        self.assertEqual( None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -8], [12, 4, -43], [-16, -1, 32]]))
+
+        self.assertEqual(None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98], [1, 2, 3]]))
+
+        # example taken from https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/cholesky/
+        self.assertEqual([[2.23606797749979, 0.0, 0.0, 0.0],
+                          [0.5366563145999494, 2.389979079406345, 0.0, 0.0],
+                          [0.13416407864998736, -0.19749126846635062, 2.818332343581848, 0.0],
+                          [-0.2683281572999747, 0.43682390737048743, 0.64657701271919, 3.052723872310221]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[5, 1.2, 0.3, -0.6], [1.2, 6, -0.4, 0.9],
+                              [0.3, -0.4, 8, 1.7], [-0.6, 0.9, 1.7, 10]]))
+
+
 class TestMultiply(unittest.TestCase):
     """[summary]
     Test for the file multiply.py