Repository: keon/algorithms
Pull request #540 (2019-10-05 18:05:55)

Added Longest Common Subsequence Algorithm under DP section
(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 :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**



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/dp/longest_common_subsequence.py b/algorithms/dp/longest_common_subsequence.py
new file mode 100644
index 0000000..cdbba95
--- /dev/null
+++ b/algorithms/dp/longest_common_subsequence.py
@@ -0,0 +1,48 @@
+"""
+A subsequence is a sequence that can be derived from another
+sequence by deleting some or no elements without changing the
+order of the remaining elements.
+
+For example, 'abd' is a subsequence of 'abcd' whereas 'adc' is not
+
+Given 2 strings containing lowercase english alphabets, find the length
+of the Longest Common Subsequence (L.C.S.).
+
+Example:
+    Input:  'abcdgh'
+            'aedfhr'
+    Output: 3
+
+    Explanation: The longest subsequence common to both the string is "adh"
+
+Time Complexity : O(M*N)
+Space Complexity : O(M*N), where M and N are the lengths of the 1st and 2nd string
+respectively.
+
+"""
+
+
+def longest_common_subsequence(s1, s2):
+    """
+    :param s1: string
+    :param s2: string
+    :return: int
+    """
+    m = len(s1)
+    n = len(s2)
+
+    dp = [[0] * (n + 1) for i in range(m + 1)]
+    """
+    dp[i][j] : contains length of LCS of s1[0..i-1] and s2[0..j-1]
+    """
+
+    for i in range(m + 1):
+        for j in range(n + 1):
+            if i == 0 or j == 0:
+                dp[i][j] = 0
+            elif s1[i - 1] == s2[j - 1]:
+                dp[i][j] = dp[i - 1][j - 1] + 1
+            else:
+                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
+
+    return dp[m][n]
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